анализ Big Oh записи псевдокод

Question

У меня проблемы с анализом алгоритма. Кажется, я в порядке, идентифицируя линейные или квадратные алгоритмы, но полностью потерян с алгоритмами nlogn или logn, кажется, что они происходят в основном из циклов while? Вот пример, на который я смотрел:

Algorithm Calculate(A,n) 
Input: Array A of size n 
t←0 
for i←0 to n-1 do 
   if A[i] is an odd number then 
      Q.enqueue(A[i]) 
   else 
      while Q is not empty do 
         t←t+Q.dequeue() 
while Q is not empty do 
  t←t+Q.dequeue() 
return t 

Мое лучшее предположение, что цикл for выполняется n раз, его вложенный цикл while q раз равен NQ, а последний цикл while также Q раз, что приводит к O (NQ + Q), что является линейным?

Answer 1

Во-первых, давайте предположим, что Q изначально пуст.

Q будет расти только при той же скорости выполнения основного цикла. Например, если мы до сих пор повторяли более 3 раз, то Q имеет размер не более 3 элементов. Таким образом, когда внутренний цикл while выполняется, он может выполнять самое большее до текущего значения 'i'. Это означает, что внутренний цикл не является истинным случаем для n ^ 2 (что вы в любом случае не утверждали). Однако, поскольку Q может быть не более, чем «i», элементы большие, поэтому мы знаем, что O (вычисление) <= O (2N). А поскольку в обозначениях O мы действительно не заботимся о скалярах, то это O (N). </p>

Если я не прав:)