Si c'est le temps de la complexité de l'algorithme, il est en big-O notation déjà, donc, oui, gardez le journal. Asymptotiquement, il y a une différence entre O(n^2) et O((n^2)*log(n)).
Un moyen simple de comprendre le big O la notation consiste à diviser le nombre réel de atomique suit par le terme dans le big O et valider, vous obtenez une constante (ou une valeur qui est inférieure à une constante).
par exemple, si votre algorithme ne 10n2⋅logn suit:
10n2⋅logn/n2 = 10 log n -> pas constante dans le n -> 10n2⋅log n est pas O(n2)
10n2⋅logn/(n2⋅log n) = 10 -> constant dans la n -> 10n2⋅log n est O(n2⋅logn)
Vous faire garder le journal parce que log(n) augmentera à mesure que n augmente et augmentera vos complexité globale puisqu'il est multiplié.
En règle générale, vous ne retirez constantes. Ainsi, par exemple, si vous aviez O(2 * n^2), vous dirais juste que la complexité est O(n^2) parce qu'il tourne sur une machine qui est deux fois plus puissant ne devrait pas influencer la complexité.
De la même manière, si vous aviez complexité O(n^2 + n^2) vous arrivez dans le cas ci-dessus et juste dire que c'est O(n^2). Depuis O(log(n)) est plus optimale que O(n^2), si vous aviez O(n^2 + log(n)), vous pouvez dire la complexité est O(n^2) parce que c'est encore moins que d'avoir O(2 * n^2).
O(n^2 * log(n)) ne tombe pas dans la situation ci-dessus de sorte que vous ne devrait pas simplifier.
si la complexité d'un algorithme =O(n^2) il peut être écrit comme O(n*n). est-il O(n)?absolument pas. donc O(n^2*logn) n'est pas en O(n^2).ce que vous devez savoir, c'est que O(n^2+logn)=O(n^2).
Formelle de la preuve mathématique serait bien ici.
Nous allons définir les variables et les fonctions suivantes:
N - entrée de la longueur de l'algorithme,
f(N) = N^2*ln(N) - une fonction qui calcule l'algorithme de temps d'exécution.
Nous allons déterminer si la croissance de cette fonction est asymptotiquement bornée par O(N^2).
Selon la définition de la notation asymptotique [1], g(x) est une asymptotique lié pour f(x) si et seulement si: pour tout suffisamment grandes valeurs de x, la valeur absolue de f(x) est tout au plus une constante positive multiple de g(x). C'est, f(x) = O(g(x)) si et seulement si il existe un nombre réel positif M et un nombre réel x0 tels que
|f(x)| <= M*g(x) for all x >= x0 (1)
Dans notre cas, il doit exister un nombre réel positif M et un nombre réel N0 tels que: |N^2*ln(N)| <= M*N^2 for all N >= N0 (2)
Évidemment, de telles M et x0 n'existent pas, parce que pour n'importe quel grand M il est N0, tels que ln(N) > M for all N >= N0 (3)
Ainsi, nous avons prouvé que N^2*ln(N) n'est pas asymptotiquement bornée par O(N^2).
ou nous gardons le journal?
Si c'est le temps de la complexité de l'algorithme, il est en big-O notation déjà, donc, oui, gardez le journal. Asymptotiquement, il y a une différence entre
O(n^2)etO((n^2)*log(n)).OriginalL'auteur Martin Dinov
Un moyen simple de comprendre le big O la notation consiste à diviser le nombre réel de atomique suit par le terme dans le big O et valider, vous obtenez une constante (ou une valeur qui est inférieure à une constante).
par exemple, si votre algorithme ne 10n2⋅logn suit:
10n2⋅logn/n2 = 10 log n -> pas constante dans le n -> 10n2⋅log n est pas O(n2)
10n2⋅logn/(n2⋅log n) = 10 -> constant dans la n -> 10n2⋅log n est O(n2⋅logn)
OriginalL'auteur zvisofer
Vous faire garder le journal parce que log(n) augmentera à mesure que n augmente et augmentera vos complexité globale puisqu'il est multiplié.
En règle générale, vous ne retirez constantes. Ainsi, par exemple, si vous aviez O(2 * n^2), vous dirais juste que la complexité est O(n^2) parce qu'il tourne sur une machine qui est deux fois plus puissant ne devrait pas influencer la complexité.
De la même manière, si vous aviez complexité O(n^2 + n^2) vous arrivez dans le cas ci-dessus et juste dire que c'est O(n^2). Depuis O(log(n)) est plus optimale que O(n^2), si vous aviez O(n^2 + log(n)), vous pouvez dire la complexité est O(n^2) parce que c'est encore moins que d'avoir O(2 * n^2).
O(n^2 * log(n)) ne tombe pas dans la situation ci-dessus de sorte que vous ne devrait pas simplifier.
OriginalL'auteur Vlad Schnakovszki
si la complexité d'un algorithme =O(n^2) il peut être écrit comme O(n*n). est-il O(n)?absolument pas. donc O(n^2*logn) n'est pas en O(n^2).ce que vous devez savoir, c'est que O(n^2+logn)=O(n^2).
OriginalL'auteur tanmoy
Formelle de la preuve mathématique serait bien ici.
Nous allons définir les variables et les fonctions suivantes:
N- entrée de la longueur de l'algorithme,f(N) = N^2*ln(N)- une fonction qui calcule l'algorithme de temps d'exécution.Nous allons déterminer si la croissance de cette fonction est asymptotiquement bornée par
O(N^2).Selon la définition de la notation asymptotique [1],
g(x)est une asymptotique lié pourf(x)si et seulement si: pour tout suffisamment grandes valeurs dex, la valeur absolue def(x)est tout au plus une constante positive multiple deg(x). C'est,f(x) = O(g(x))si et seulement si il existe un nombre réel positifMet un nombre réelx0tels que|f(x)| <= M*g(x) for all x >= x0 (1)Dans notre cas, il doit exister un nombre réel positif
Met un nombre réelN0tels que:|N^2*ln(N)| <= M*N^2 for all N >= N0 (2)Évidemment, de telles
Metx0n'existent pas, parce que pour n'importe quel grandMil estN0, tels queln(N) > M for all N >= N0 (3)Ainsi, nous avons prouvé que
N^2*ln(N)n'est pas asymptotiquement bornée parO(N^2).Références:
Un: - https://en.wikipedia.org/wiki/Big_O_notation
OriginalL'auteur Alex T