1
J'ai avec moi une récursion de la forme,Quelle est la valeur de O (n) + O (n-1) + O (n-2) + ... + O (1)? Est-ce O (n^2)? Comment?
T(n) = T(n-1) + O(n)
qui devrait être équivalent à
T(n) = T(1) + O(2) + O(3) + .... + O(n-1) + O(n)
donc ma solution dépend de la valeur de
O(n) + O(n-1) + O(n-2) + ... + O(1)
Depuis, n + n-1 + n-2 + ... + 1 = n*(n+1)/2, Je pense que cela devrait être O(n^2) mais je ne sais pas comment utiliser les maths Big-O pour arriver à cette solution.
Je veux dire,
c * O(n) is O(n)
mais
n * O(n) is O(n^2)
Comment puis-je conclure que
O(n) + O(n-1) + O(n-2) + ... + O(1) = O(n^2)
@ polkovnikov.ph, je n'ai pas demandé est question mais serait intéressé de voir comment cela s'appliquait. Le lien du théorème des maîtres que vous avez mentionné semble être pour les algorithmes récursifs de la forme T (n) = T (n/b) + F (n). Comment formeriez-vous la complexité du problème actuel sous cette forme? – user3684792
@ polkovnikov.ph J'ai pensé à la méthode maître pour calculer la complexité, mais comment puis-je l'appliquer ici? Ce n'est pas sous la forme appropriée que T (n) = aT (n/b) + f (n) – Krash