Comment puis-je trouver le nombre de fois où x = x + 1 est exécuté en termes de N?

Question

im aussi avoir du mal à trouver les oméga(), et thêta() selon le cas

x=0; 
    for k=1 to n 
    for j=1 to n-k 
     X=X+1; 

Answer 1

la réponse est comme ceci: n-1 + n + n -2 -3 + ... = n * n - (1 + 2 + 3 + ... + n) = n^2 - n (n-1)/2

Answer 2

La boucle interne est n-1 + n-2 + n-3 ... + 1 + 0. Utilisez this tutorial pour calculer la somme d'une série arithmétique pour trouver la solution. La boucle externe est évidemment juste "n".

Ce sera le big-thêta. Le grand-oh sera le même que le grand-thêta lorsque vous retirez tout sauf le premier terme et supprimez le multiplicateur, par ex. Thêta (2 * log (n) + 5) devient O (log (n)). Omega est la même chose que gros - Oh dans ce cas, parce que le meilleur des cas et le pire des cas sont identiques; ou vous pouvez tricher et dire que le grand-Omega est le temps constant, parce que le grand-Omega de TOUTES les fonctions est le temps constant.

Answer 3

D'abord, regardez vos limites. k = 1 et k = n.

Pour k = 1, la boucle interne est exécutée (n-1) fois. Pour k = n, la boucle interne est exécutée (0) fois. Donc, 0 + 1 + ... + (n-1) est une somme arithmétique => (n-1) (n)/2 fois.

Maintenant, testez-le sur quelques petites valeurs :)