La complexité linéaire O (20n) peut-elle dominer la complexité polynomiale O (n^2/3)?

Question

Graph un algorithme avec une complexité en O (n^2/3) (complexité polynomiale):

Graph un algorithme avec une complexité de O (20n) (complexité linéaire):

Ordre de Dominance pour différentes complexité:

O (1) < O (logn) < O (n) < O (nlogn) < O (n^2) < O (2^n) < O (n!)

Problème: Si je devais définir un ordre de dominance entre les deux algorithmes ci-dessus n^2/3 et 20n, je suis confus quant à celui qui viendra en premier.

Selon l'ordre de domination pour complexité différente, je vois que complexité polynomiale domine complexité linéaire.

Commander 1:

O (n^2/3) < O (20n)

Mais des graphiques, on peut voir que pour O(20n), le taux de croissance de le nombre d'opérations sur le nombre d'éléments est supérieur à O(n^2/3).

Classement 2:

O (20n) < O (n^2/3)

je besoin de précisions quant à quel ordre parmi Classement 1 ou Classement 2 est correct.

Answer 1

O(n^b) ⊆ O(n^a) if b <= a

O(20*n) = O(n) = O(n^1)

O(n^(2/3)) ⊆ O(n^1)

Quelques mots sur polynomial time complexité

Un algorithme est dit résoluble en temps polynomial si le nombre d'étapes nécessaires pour compléter la algorithme pour une entrée donnée est O(n^k) pour certains nonnegat ive nombre entier k, où n est la complexité de l'entrée.

Ainsi, les algorithmes avec O(20*n) et O(n^(2/3)) temps complexité ont tous deux la complexité polynomiale. La «complexité linéaire» n'est qu'un sous-ensemble d'un polynôme.