Questions sur les notations asymptotiques et l'analyse
Dans la plupart des classes d'introduction aux algorithmes, des notations telles que (Big O) et sont introduites, et un étudiant apprendra généralement à utiliser l'une de celles-ci pour rechercher la complexité temporelle.ΘOOOΘΘ\Theta Cependant, il existe d'autres notations, telles que , et ....
C'est peut-être une question ridicule, mais est-il possible d'avoir un problème qui devient réellement plus facile à mesure que les intrants grossissent? Je doute que des problèmes pratiques se présentent de la sorte, mais peut-être pourrions-nous inventer un problème dégénéré qui possède cette...
O(m+n)O(m+n)O(m+n)O(max(m,n))O(max(m,n))O(\max(m,n))O(min(m,n))O(min(m,n))O(\min(m,n))O(|V|+|E|)O(|V|+|E|)O(|V| +
Dans "Big O", les notations communes ont des noms communs (au lieu de dire "Oh comme facteur constant"): O (1) est "constante" O (log n) est "logarithmique" O (n) est "linéaire" O (n ^ 2) est "quadratique" O (n * log n) est ??? Est-ce juste "n log n" ou est-ce qu'il a un nom spécial comme...
Supposons que j'ai une liste de fonctions, par exemple nloglog(n),2n,n!,n3,nlnn,…nloglog(n),2n,n!,n3,nlnn,…\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots Comment puis-je les trier asymptotiquement, c'est-à-dire après la relation définie par f≤Og⟺f∈O(g)f≤Og⟺f∈O(g)\qquad f \leq_O g \iff f...
Il est bien connu que cet algorithme «naïf» pour mélanger un tableau en échangeant chaque élément avec un autre choisi au hasard ne fonctionne pas correctement: for (i=0..n-1) swap(A[i], A[random(n)]); Plus précisément, puisque à chacune des nnn itérations, l’une desnnn choix est fait (avec une...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
Pour un langage régulier , soit le nombre de mots dans de longueur . En utilisant la forme canonique de Jordan (appliquée à la matrice de transition non annotée de certains DFA pour ), on peut montrer que pour un assez grand , où sont des polynômes complexes et sont des "valeurs propres" complexes....
J'ai entendu plusieurs fois que pour des valeurs suffisamment petites de n, O (n) peut être pensé / traité comme si c'était O (1). Exemple : La motivation pour le faire est basée sur l'idée incorrecte que O (1) est toujours meilleure que O (lg n), est toujours meilleure que O (n). L'ordre...
Existe-t-il une structure de données pour gérer une liste ordonnée qui prend en charge les opérations suivantes en temps amorti ?O ( 1 )O(1)O(1) GetElement (k) : retourne le ème élément de la liste.kkk InsertAfter (x, y) : insérez le nouvel élément y dans la liste immédiatement après x. Supprimer...
Si j'ai une fonction dont la complexité temporelle est O ( mn ), où m et n sont les tailles de ses deux entrées, appellerions-nous sa complexité temporelle "linéaire" (car elle est linéaire en m et n ) ou "quadratique" ( puisqu'il s'agit d'un produit de deux tailles)? Ou autre chose? Je pense que...
Au cours ici , Dave Clarke a proposé que pour comparer la croissance asymptotique vous devez tracer les fonctions à portée de main. En tant qu'informaticien théoriquement enclin, j'appelle (ed) ce vodoo comme un complot n'est jamais une preuve. Après réflexion, je dois convenir qu'il s'agit d'une...
Quand le grand O a-t-il été utilisé pour la première fois en informatique et quand est-il devenu standard? La page Wikipedia à ce sujet cite Knuth, Big Omicron et Big Omega And Big Theta , SIGACT avril-juin 1976, mais le début de cet article se lit comme suit: La plupart d'entre nous se sont...
Le théorème maître est un bel outil pour résoudre certains types de récurrences . Cependant, nous masquons souvent une partie intégrante lors de son application. Par exemple, lors de l'analyse de Mergesort, nous sommes heureusement passés de T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad...
Souvent, si les complexités ont des constantes telles que 3n, nous négligeons cette constante et disons O (n) et non O (3n). Je n'arrive pas à comprendre comment pouvons-nous négliger ce triple changement? Une chose varie 3 fois plus rapidement qu'une autre! Pourquoi négligeons-nous ce fait?...
Actuellement, j'étudie moi-même l'introduction aux algorithmes (CLRS) et il y a une méthode particulière qu'ils décrivent dans le livre pour résoudre les relations de récurrence. La méthode suivante peut être illustrée par cet exemple. Supposons que nous ayons la récurrence T( n ) = 2 T( n--√) +...
Construisons deux fonctions satisfaisant:f,g:R+→R+f,g:R+→R+ f,g: R^+ → R^+ f,gf,gf, g sont continus; f,gf,gf, g augmentent de façon monotone; g ≠ O ( f )f≠O(g)f≠O(g)f \ne O(g) et .g≠O(f)g≠O(f)g \ne O(f)
On pense généralement qu'une limite inférieure asymptotique telle que la dureté exponentielle implique qu'un problème est "intrinsèquement difficile". Le cryptage qui est "intrinsèquement difficile" à casser est considéré comme sûr. Cependant, une borne inférieure asymptotique n'exclut pas la...
Lorsque nous comparons la complexité de deux algorithmes, il arrive généralement que f(n)=O(g(n))f(n)=O(g(n))f(n) = O(g(n)) ou (éventuellement les deux), où et sont les temps d'exécution (par exemple) des deux algorithmes.f gg(n)=O(f(n))g(n)=O(f(n))g(n) = O(f(n))fffggg Est-ce toujours le cas?...
Que signifie ?logO(1)nlogO(1)n\log^{O(1)}n Je connais la notation big-O, mais cette notation n'a aucun sens pour moi. Je ne trouve rien non plus à ce sujet, car il n'y a aucun moyen qu'un moteur de recherche interprète cela correctement. Pour un peu de contexte, la phrase où je l'ai trouvée se lit...