analyse Big Oh notation pseudocode

Question

J'ai de la difficulté à analyser mon algorithme. J'ai l'impression d'être en train d'identifier des algorithmes linéaires ou carrés mais je suis totalement perdu avec les algorithmes nlogn ou logn, ceux-ci semblent provenir principalement des boucles while. Voici un exemple que je cherchais à:

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 

Ma meilleure estimation est la boucle est exécutée n fois, son emboîtés alors que les temps boucle q faire NQ et la finale en boucle aussi Q fois résultant en O (NQ + Q) qui est linéaire?

Answer 1

D'abord, supposons que Q est initialement vide.

Q ne se développera au maximum qu'au même rythme d'exécution de la boucle principale. Par exemple, si nous avons itéré plus de 3 fois jusqu'à présent, Q est au plus de 3 éléments de grande taille. Ainsi, lorsque la boucle while interne est exécutée, elle ne peut s'exécuter que jusqu'à la valeur actuelle de 'i'. Cela signifie que la boucle interne n'est pas un cas réel sur n^2 (ce qui n'est pas quelque chose que vous avez revendiqué de toute façon). Cependant, puisque Q ne peut être que des éléments 'i', nous savons donc que O (calcul) < = O (2N). Et puisque dans la notation O, nous ne nous soucions pas vraiment des scalaires, alors c'est O (N). Sauf si je me trompe :)