Besoin d'aide pour trouver Big Oh, c, and No

Question

Besoin d'aide avec ces deux exemples. Comme je comprends un peu Big Oh, mais pas vraiment les concepts c et No. Le premier semble assez simple. Je suis sûr que le Big Oh serait O (n^3) mais je ne suis pas sûr.

f (x) = 2n3 + 5n + 2

Le prochain est celui qui me fait vraiment sentir comme idk ce que je fais.

def analyze(alist): 
     1 exchanges = True 
     2 passnum = len(alist)-1 
     3 while passnum > 0 and exchanges: 
     4  exchanges = False 
     5  for i in range(passnum): 
     6    if alist[i]>alist[i+1]: 
     7    exchanges = True 
     8     alist[i],alist[i+1]=alist[i+1],alist[i] 
     9   passnum = passnum-1 

Il veut étiqueter chaque ligne au sujet de Big Oh (quoi?), Puis calculer le Big Oh, c, et n ° Toute aide/explication serait d'une grande aide, je me sens perdu . Je pensais que je l'avais, mais il est clair que je ne le fais pas. Merci

Answer 1

Chaque ligne représente une opération élémentaire ou une fonction.

Une opération élémentaire est souvent considérée comme prenant du temps O (1) (temps constant).

si j'avais ce code simple et je cherche le grand Oh par rapport à N, un nombre donné dans l'argument

a = 1 // O(1) assignement is constant 
b = a + 2 // O(1) addition is constant 
for (a=0 to N-1) // a will take value between [0..n-1], which is n different values 
    a = a + 1 // addition is O(1) 
//resume: i have => O(1) + O(1) + N * O(1) => O(N) 

Vous voyez que je ne l'étiquette de chaque ligne, et je peux conclure, ce code est O (N) parce que c'est le facteur dominant. Vous devez essayer de faire la même chose pour votre extrait de code.