以下のトリプルネストループの時間の複雑さは何ですか？N.の用語で解決する

Question

この関数の時間の複雑さが何であるかを尋ねたい（トリプルネストループ） ・理解できるように完全に分析を完全に分析します。

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

$ r $ の値は最後です。 $$ \ 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。 $$ あなたはここからそれを取ります。Wolfram Alphaなどのコンピュータ代数システムを使用して、計算を手助けすることができます。

漸近ティクスにのみ興味がある場合は、次の上限を使用できます。 $$ \ sum_ {i= 1} ^ {n-1} \ sum_ {j= i + 1} ^ n j \ leq \ sum_ {i= 1} ^ n ^ n ^ n n。 $$ これが与える上限を見つけることができます。次の下限を使用して検証できるように、この上限は非常に良いことがわかります（大きい $ 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。 $$