Big-O complexité du temps

J'ai fait un peu d'auto-apprentissage sur Big-O. Je comprends comment donner des exemples des notations suivantes aux algorithmes:Big-O complexité du temps

O (N):

for(int i = 0; i < n; i++) 
    sum++;

O (N^2):

for(int i = 0; i < n; i++) 
    for(int j = 0; j < n; j++) 
     sum++;

O (N^3):

for(int i = 0; i < n; i++) 
    for(int j = 0; j < n * n; j++) 
     sum++;

J'ai rencontré ces notations que je ne comprends pas très bien. Comment puis-je donner des exemples en termes d'algorithmes?

Peut-être que je devrais l'exprimer ainsi: écrire un algorithme qui prend du temps en cours d'exécution en proportion:

O ((n^3)/4)
log n^3
O ((log^2) n) + O (n)
4^n
n^3/2

Source

2010-10-25 user471646

Avez-vous PRIS? Voir http://stackoverflow.com/questions/107165/big-o-for-eight-year-olds et http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o et http : //stackoverflow.com/search?q = Big + O; –

La question est généralement de savoir comment trouver le Big O pour un algorithme spécifique, – medopal

Ce sont des exemples ** d'algorithmes O(). Il existe un nombre infini d'algorithmes adaptés à tous les grands liens de O. Check @ KMan. –

Je crains que vous comprenez mal n "Big-O" otation.

Une notation n'est pas "exprimée" en tant qu'algorithme. Au contraire, la notation Big-O décrit une propriété d'un algorithme. Donc, ce n'est pas "O (N) peut être exprimé comme XXX", mais plutôt "l'algorithme XXX a la complexité de O (N)". Cela dit, il est assez raisonnable de demander des exemples d'algorithmes avec une certaine complexité; vous en avez déjà une liste. Pour répondre à vos questions:

~~O (4^n) est le même que O (e^n), souvent écrit comme O (exp (n)) (essayez de comprendre pourquoi c'est pareil).~~ O (4^n) appartient à la classe des algorithmes avec "complexité exponentielle" (EXPTIME). Beaucoup de problèmes importants en math/CS ont une complexité exponentielle (ou une complexité presque exponentielle).

Un algorithme avec une complexité exponentielle serait par exemple une solution naïve au discrete logarithm problem.

Pour les autres complexités je ne peux pas donner un exemple, mais vous en trouverez probablement un en recherchant un peu.

Source

2010-10-25 08:35:28 sleske

Je n'achète pas votre O (a^n) = O (b^n) avec a, b> 1. S'il est vrai que la base n'est pas pertinente pour les logarithmes, elle ne l'est pas pour les fonctions exponentielles. Autrement toute la classe EXPTIME serait un ensemble de problèmes avec O (2^n) (ou plus commodément O ((1 + epsilon)^n)) algorithmes. – bitmask

@bitmask: En fait, c'est le cas. Wikipedia, par exemple définit EXPTIME comme "l'ensemble de tous les problèmes de décision résolus par une machine de Turing déterministe en O (2^p (n)) temps" (avec p (n) étant un polynôme en n). – sleske

BTW, mon énoncé original "O (4^n) est le même que O (e^n)" est bien sûr faux. Ce que j'avais à l'esprit (mais très faiblement) était qu'ils sont tous les deux dans EXPTIME. Merci de me le rappeler :-). – sleske

-1

Les algorithmes que vous avez donnés ne sont pas à proprement parler Big-O mais Theta. Big-O est une limite supérieure asymptotique signifiant que sur une entrée de cas pire, le temps de fonctionnement sera celui donné mais pas pour toutes les entrées, alors que Theta est une limite étroite signifiant que le temps courant sera toujours celui-là. Considérons par exemple un algorithme de tri qui reçoit une liste déjà triée en entrée, ou un algorithme de recherche où les choses à trouver sont le premier élément d'une liste (comment binarysearch se compare-t-il à la recherche linéaire dans ce cas).

Source

2010-10-25 08:45:09

Si nous allons être pointilleux. Tout algorithme qui est 'Theta (f (N))' est * aussi * 'O (f (N))'. Donc, l'OP est effectivement correct en disant qu'ils sont Big-O –

??? Ce sont tous les deux Big-O ** et ** Omega, impliquant Theta. "ce qui signifie que sur certains cas pire". Theta est juste plus spécifique, la borne inférieure a été trouvée/prouvée aussi. Ce n'est pas lié au pire des cas. "Le temps de course sera toujours celui" est strictement parlant pas correct, mieux serait "la croissance du taux est proportionnelle à Theta". – Ishtar

Big-O complexité du temps

Répondre

Questions connexes