C'est une question de devoirs du livre d'Udi Manber. Tout indice serait bien :) Je dois montrer que: n ( log3( n ) )5= O ( n1.2)n(log3(n))5=O(n1.2)n(\log_3(n))^5 = O(n^{1.2}) J'ai essayé d'utiliser le théorème 3.1 du livre: (pour c > 0 ,)F( n )c= O ( aF( n ))f(n)c=O(af(n))f(n)^c = O(a^{f(n)})c...
Du point de vue du comportement asymptotique, qu'est-ce qui est considéré comme un algorithme "efficace"? Quelle est la norme / raison de tracer la ligne à ce point? Personnellement, je penserais que tout ce que je pourrais naïvement appeler "sous-polynôme", tel que tel que serait efficace et tout...
Quelle notation est utilisée pour discuter des coefficients des fonctions en notation big-O? J'ai deux fonctions: F( x ) = 7 x2+ 4 x + 2F(X)=7X2+4X+2f(x) = 7x^2 + 4x +2 g( x) = 3 x2+ 5 x + 4g(X)=3X2+5X+4g(x) = 3x^2 + 5x +4 Évidemment, les deux fonctions sont , en effet , mais cela ne permet pas une...
J'ai posé une question (initiale) sur des sommes de termes Landau auparavant , essayant de mesurer les dangers d'abuser de la notation asymptotique en arithmétique, avec un succès mitigé. Maintenant, ici, notre gourou de la récurrence, JeffE, fait essentiellement ceci:
J'essaie de comprendre ce qui ne va pas avec la preuve suivante de la récurrence suivante T(n)≤2(c⌊nT(n)=2T(⌊n2⌋)+nT(n)=2T(⌊n2⌋)+n T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n)T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n) T(n) \leq...
On m'a confié un devoir avec Big O. Je suis coincé avec des boucles imbriquées qui dépendent de la boucle précédente. Voici une version modifiée de ma question de devoirs, car je veux vraiment la comprendre: sum = 0; for (i = 0; i < n; i++ for (j = 0; j < i; j++) sum++; La partie qui me jette...
3n=2O(n)3n=2O(n)3^n = 2^{O(n)}est apparemment vrai. Je pensais que c'était faux car3n3n3^n croît plus rapidement que n'importe quelle fonction exponentielle avec une base de 2. Comment est 3n=2O(n)3n=2O(n)3^n = 2^{O(n)}
Disons que j'ai un graphique |G||G||G| avec |E|=O(V2)|E|=O(V2)|E|=O(V^2)bords. Je veux exécuter BFS surggG qui a une durée de O (V+E)O(V+E)O(V+E). Il semble naturel d'écrire que le temps d'exécution sur ce graphique serait O ( O (V2) + V)O(O(V2)+V)O(O(V^2)+V) puis simplifier pour O (V2)O(V2)O(V^2)....
Dans CLRS (aux pages 49-50), quelle est la signification de l'énoncé suivant: Σni=1O(i)Σi=1nO(i)\Sigma_{i=1}^{n} O(i) n'est qu'une seule fonction anonyme (de ), mais n'est pas la même chose queiiiO(1)+O(2)+⋯+O(n)O(1)+O(2)+⋯+O(n)O(1)+O(2)+\cdots+O(n), qui n'a pas vraiment d'interprétation. "...