Trouver Big O de la série harmonique
prouver que
1 + 1/2 + 1/3 + ... + 1/n is O(log n).
Assume n = 2^k
j'ai mis la série dans la sommation, mais je n'ai aucune idée de comment aborder ce problème. Toute aide est appréciée
3 réponses
cela découle facilement d'un simple fait dans le calcul:
et nous avons l'inégalité suivante:
ici, nous pouvons conclure que S = 1 + 1/2 + ... + 1 / n est à la fois Ω(log(n)) et O(log(n)), donc il est E Xposé(log(n)), la liaison est en fait étanche.
Voici une formulation utilisant des mathématiques discrètes:
So, H(n) = O(log n)
Question
1 + 1/2 + 1/3 + ... + 1 /n
Supposons que n = 2^k
-
si le terme
3rdest1/3et pas1/4 (1/2^2), cela signifie qu'il n'y a aucun terme dans tous, donc il sera O(n) . Il est vrai que leur somme peut-être journal n , mais la complexité est le nombre d'itérations et non la somme des séries. -
envisagez de le résoudre de façon programmatique. Vous finiriez boucle en cours d'exécution 1 À n fois et en ajoutant 1 / n à la somme. Combien de fois ne s'est-il exécuté????
1 to nO(n) -
si le problème a été changé à
1 + 1/2 + 1/4 + ... + 1/n, série peut maintenant être écrit comme 1/2^0 + 1/2^1 + 1/2^2 + ... + 1/2^(k). Maintenant indice fourni par votre enseignant aussi du sens. Combien de fois boucle va fonctionner???0 to k = k + 1 times, et des deux séries nous pouvons voir2^k = nd'oùk = log (n). Donc, nombre de fois où il a couru =log(n) + 1 = O(log n) -
je suppose que vous ou votre professeur avez fait une typographie.
mise à Jour
comme Dukeling l'a souligné, je suppose bien sûr que the provided function is pseudo-code and calculating the time complexity of that . Maintenant, après un année je comprends pourquoi j'ai obtenu des votes mitigés pour cette réponse particulière. Les gars c'est stackoverflow et est principalement conçu pour le codage. Si vous avez des problèmes qui ne sont pas directement liés à la programmation, veuillez utiliser un autre site stackexchange tel que https://math.stackexchange.com /