Est de complexité O(log(n)) équivalent à O(sqrt(n))?

Mon professeur titulaire nous a appris que toute opération qui réduit de moitié la longueur de l'entrée a un O(log(n)) de la complexité comme un pouce à la règle. Pourquoi n'est-il pas O(sqrt(n)), ne sont pas à la fois de leur équivalent?

Tracer les graphes de log(n) et sqrt(n) jusqu'à environ n==1000, voir si vous avez encore de penser qu'ils sont équivalents, ce que vous entendez par là.
log(1) = 0 et sqrt(1) = 1
Désolé, je ne sais pas ce que je pensais, toutes les réponses sont extrêmement instructif. Merci

OriginalL'auteur white_tree | 2017-02-04

algorithm time-complexity

35

Ils ne sont pas équivalents: sqrt(N) va augmenter beaucoup plus que log₂(N). Il n'existe pas de constante C de sorte que vous avez sqrt(N) < C. log(N) pour toutes les valeurs de N est supérieure à la valeur minimale.

Un moyen facile de saisir, c'est que log₂(N) sera une valeur proche du nombre d' (binaire) chiffres de N, tandis que sqrt(N) sera un nombre qui est elle-même la moitié du nombre de chiffres que N. Ou, en l'état avec une égalité:

log₂(N) = 2log₂(sqrt(N))

Si vous avez besoin de prendre le logarithme(!) de sqrt(N) pour le ramener à un même ordre de complexité que log₂(N).

Par exemple, pour un nombre binaire à 11 chiffres, 0b10000000000 (=2¹⁰), la racine carrée est 0b100000, mais le logarithme est seulement 10.

+1 pour log(N) will be a value close to the number of (binary) digits of N, while sqrt(N) will be a number that has itself half the number of digits that N has.
Fantastique réponse.

OriginalL'auteur trincot
10

En supposant natural logarithm (sinon, il suffit de multiplier par une constante), nous avons

lim {n->inf} log n /sqrt(n) = (inf /inf)
```
                        =  lim {n->inf} 1/n /1/(2*sqrt(n)) (by L'Hospital)
                        =  lim {n->inf} 2*sqrt(n)/n
                        =  lim {n->inf} 2/sqrt(n)
                        =  0 < inf
```
Reportez-vous à https://en.wikipedia.org/wiki/Big_O_notation pour alternative defination de O(.) et, partant, à partir de ci-dessus, nous pouvons dire log n = O(sqrt(n)),

Également de comparer la croissance de f les fonctions ci-dessous, log n est toujours supérieure délimitée par sqrt(n) pour les grandes n.

OriginalL'auteur Sandipan Dey
3

Non, Il n'est pas équivalent.

@trincot a donné une excellente explication avec un exemple dans sa réponse. Je vais ajouter un point de plus. Votre professeur vous a enseigné que
```
any operation that halves the length of the input has an O(log(n)) complexity
```
Il est également vrai que,
```
any operation that reduces the length of the input by 2/3rd, has a O(log3(n)) complexity
any operation that reduces the length of the input by 3/4th, has a O(log4(n)) complexity
any operation that reduces the length of the input by 4/5th, has a O(log5(n)) complexity
So on ...
```
C'est même vrai pour toute la réduction des longueurs de l'entrée en (B-1)/Bth. Il a alors une complexité de O(logB(n))

N:B: O(logB(n)) signifie B en fonction du logarithme de n

OriginalL'auteur jbsu32
2

Non, ils sont pas équivalent; vous pouvez même prouver que
```
   O(n**k) > O(log(n, base)) 
```
pour tout k > 0 et base > 1 (k = 1/2 en cas de sqrt).

Lorsque vous parlez O(f(n)) nous voulons étudier le comportement de grand n,
limites est un bon moyen pour cela. Supposons que les deux grandes O sont équivalentes:
```
  O(n**k) = O(log(n, base)) 
```
qui signifie qu'il ya une certaine constante C tels que
```
  O(n**k) <= C * O(log(n, base)) 
```
à partir de quelques assez grand n; en d'autres termes (log(n, base) n'est pas 0 à partir de grandes n, les deux fonctions sont continûment dérivable):
```
  lim(n**k/log(n, base)) = C 
  n->+inf
```
Pour trouver la limite de la valeur, nous pouvons utiliser La Règle de l'Hospital, c'est à dire prendre des produits dérivés pour le numérateur et le dénominateur et de les diviser:
```
  lim(n**k/log(n)) = 

  lim([k*n**(k-1)]/[ln(base)/n]) =

  ln(base) * k * lim(n**k) = +infinity
```
nous pouvons donc conclure qu'il n'y a pas de constante C tels que O(n**k) < C*log(n, base) ou en d'autres termes
```
 O(n**k) > O(log(n, base)) 
```
OriginalL'auteur Dmitry Bychenko

Vous devez vous connecter pour publier un commentaire.