Questions sur les notations asymptotiques telles que Big-O, Omega, etc.
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 ....
Je lis un livre intitulé Principles of Computer Science (2008), de Carl Reynolds et Paul Tymann (publié par Schaum's Outlines). Le deuxième chapitre présente les algorithmes avec un exemple de recherche séquentielle qui itère simplement dans une liste de noms et renvoie VRAI si un nom donné est...
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| +
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...
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...
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...
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)
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...
J'ai lu Introduction aux algorithmes de Cormen et al. et je lis l'énoncé du théorème maître à partir de la page 73 . Dans le cas 3, il existe également une condition de régularité qui doit être satisfaite pour utiliser le théorème: ... 3. Si f(n)=Ω(nlogba+ε)f(n)=Ω(nlogba+ε)\qquad \displaystyle...
Je comprends que est plus rapide que et plus lent que . Ce qui est difficile à comprendre pour moi, c'est comment comparer réellement et avec où .Θ ( n )Θ(n)\Theta(n)Θ ( n logn )Θ(nJournaln)\Theta(n\log n)Θ ( n / logn )Θ(n/Journaln)\Theta(n/\log n)Θ ( n logn )Θ(nJournaln)\Theta(n \log n)Θ ( n /...
Supposons que l'on nous donne deux nombres et et que nous voulons trouver pour l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r L'algorithme naïf vérifie simplement toutes les paires possibles; par exemple en rubis, nous aurions: def max_xor(l, r) max = 0...
Je lis un article, et il dit dans sa description de la complexité temporelle que la complexité temporelle est .O~( 22 n)O~(22n)\tilde{O}(2^{2n}) J'ai cherché sur Internet et wikipedia, mais je ne trouve pas ce que ce tilde signifie en notation big-O / Landau. Dans le journal lui-même, je n'ai...
J'ai écrit ∑i = 1n1je= ∑i = 1nO (1)= O (n)∑je=1n1je=∑je=1nO(1)=O(n)\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n) mais mon ami dit que c'est faux. De la feuille de triche TCS, je sais que la somme est également appelée qui a une croissance...
Tout d'abord, permettez-moi d'écrire la définition du grand juste pour rendre les choses explicites.OOO f(n)∈O(g(n))⟺∃c,n0>0f(n)∈O(g(n))⟺∃c,n0>0f(n)\in O(g(n))\iff \exists c, n_0\gt 0 tel que0≤f(n)≤cg(n),∀n≥n00≤f(n)≤cg(n),∀n≥n00\le f(n)\le cg(n), \forall n\ge n_0 Disons que nous avons un...
Disons par exemple que je fais un traitement de chaîne qui nécessite une analyse de deux chaînes. Je n'ai aucune information sur leur longueur, ils proviennent donc de deux familles distinctes. Serait-il acceptable d'appeler la complexité d'un algorithme ou O (n + m) (selon que l'on utilise un...
J'ai donc cette question pour prouver une déclaration: O(n)⊂Θ(n)O(n)⊂Θ(n)O(n)\subset\Theta(n) ... Je n'ai pas besoin de savoir comment le prouver, juste que dans mon esprit cela n'a aucun sens et je pense que ce devrait plutôt être Θ(n)⊂O(n)Θ(n)⊂O(n)\Theta(n)\subset O(n) . Ma compréhension est que...
Comment l'analyse asymptotique (big o, little o, big theta, big theta etc.) est-elle définie pour les fonctions à variables multiples? Je sais que l'article Wikipedia contient une section, mais il utilise beaucoup de notation mathématique que je ne connais pas. J'ai également trouvé l'article...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...