bulle complexité temporelle de trouver l'algorithme de tri

Question

j'essaie de trouver la complexité du temps de la bulle sorte

n=length[A] 
for j <- n-1 to 1 
for i <- 0 to j-1 
if A[i]>a[i+1] 
temp=A[i] 
A[i]=A[i+1] 
A[i+1]=temp 

return A 

s'il vous plaît quelqu'un peut aider grâce

Answer 1

• Dans la ligne 1, nous attribuons la longueur du tableau à n temps si constant
• Dans la ligne 2, nous avons une boucle for qui décrémente j par 1 à chaque itération jusqu'à j = 1 et au total va itérer n-2 fois.
• A l'intérieur de la première boucle for, nous avons une seconde boucle for qui incrémente i par 1 à chaque itération jusqu'à i = j-1 et va itérer j-1 fois. A chaque itération de la boucle interne, nous avons les lignes 4, 5, 6, 7 qui sont toutes des assignations et un accès au tableau qui coûtent, au total, un temps constant.
• Nous pouvons penser aux deux boucles for de la façon suivante: Pour chaque itération de la boucle for externe, la boucle interne fortera itérativement j-1 fois.
• Par conséquent, lors de la première itération de la boucle for externe, nous avons j = n-1. Cela signifie que la boucle for interne va itérater (n-1) -1 = (n-2) fois. Ensuite, à la deuxième itération de la boucle for externe, nous avons j = n-2, de sorte que la boucle for interne va itérer (n-2) -1 = (n-3) fois et ainsi de suite. Et nous faisons cela jusqu'à j = 1.
• Nous aurons alors l'équation: (n-2) + (n-3) + ... + 2 + 1 qui est le nombre total de fois que la boucle interne va itérer après l'exécution de l'algorithme entier. Nous savons que 1 + 2 + ... + n-1 + n = n (n-1)/2 donc notre expression peut être simplifiée à ceci: n (n-1)/2 - (n-1) -n = n (n-1)/2 -2n + 1 = O (n^2). Puisque notre boucle for interne va itérater O (n^2) fois, et à chaque itération faire un travail constant, alors cela signifie que notre exécution sera O (cn^2) où c est la quantité de travail constant effectué par les lignes 4,5,6,7. Combinez O (cn^2) avec la ligne 1 qui est O (1) nous avons O (cn^2) + O (1) qui est juste O (n^2).
• Par conséquent, l'exécution de BubbleSort est O (n^2).

Si vous êtes encore confus alors cela aidera peut-être: https://www.youtube.com/watch?v=Jdtq5uKz-w4