Quelle est la complexité temporelle de la boucle triple imbriquée suivante?Gentiment résoudre en termes de n

Question

Je veux demander que quelle est la complexité de cette fonction (boucle triple imbriquée) Analyse de manière complète pour que je puisse comprendre.

function loop_nested(n)
  r := 0
  for i := 1 to n - 1 do
    for j := i + 1 to n do
      for k := 1 to j do
        r := r + 1
  return(r)

Answer 1

la valeur de $ r $ à la fin est $$ \ sum_ {i= 1} ^ {n-1} \ sum_ {j= i + 1} ^ n \ sum_ {k= 1} ^ j 1= \ sum_ {i= 1} ^ {n-1} \ sum_ {j= i + 1} ^ n j. $$ Vous le prenez d'ici.Vous pouvez utiliser un système d'algèbre informatique tel que Wolfram Alpha pour vous aider avec les calculs.

Si vous n'êtes intéressé que par Asymptotics, vous pouvez utiliser la limite supérieure suivante: $$ \ sum_ {i= 1} ^ {n-1} \ sum_ {j= i + 1} ^ n j \ leq \ sum_ {i= 1} ^ n \ sum_ {j= 1} ^ n n. $$ Je vais vous laisser travailler dans quelle partie supérieure ceci donne.Il s'avère que cette limite supérieure est assez bonne, car vous pouvez vérifier en utilisant la limite inférieure suivante (valide pour le grand $ n $ ): $$ \ sum_ {i= 1} ^ {n-1} \ sum_ {j= i + 1} ^ n j \ geq \ sum_ {i= 1} ^ {n / 2} \ sum_ {j= n / 2 + 1} ^ n n / 2. $$