Analyse de l'algorithme QuickSort

Question

Je suis un cours sur le tri rapide sur YouTube. Je suis le plus de l'idée mais je suis coincé de ce qu'il a dit de la série Arithmétique dans le point suivant:

pire cas: T (n) = T (n-1) + Theta (n)

Il a demandé, "Qu'est-ce que cela équivaut à?"

Et puis il a dit qu'il est égal à Theta (n^2)

Pourquoi est-il égal à Theta (n^2) et non égal à Theta (n) ??

Answer 1

Il est un sum of arithmetic progressionT(n) = T(n-1) + n = n + n-1 + n-2 + ... + 1 = n(n+1)/2 qui est en Theta(n^2)

Vous pouvez également l'obtenir avec l'induction, en supposant Theta(n) représente n (pour plus de simplicité, peut être modifié en utilisant la même approche):

Hypothesis: T(n) = n(n+1)/2 
Base: T(1) = 1*2/2 = 1 
Step: 
T(n) = T(n-1) + n <= (*) (n-1)*n/2 + n = 
    = (n^2 -n)/2 + 2n/2 = (n^2-n + 2n)/2 = 
    = (n^2 +n) /2 = n(n+1)/2 
(*) induction hypothesis 

Cela nous montre T(n) = n(n+1)/2 qui est en effet dans Theta(n^2).