1 + 2 + 3 + ... + n sumアルゴリズムの例

Question

T(n)=1+2+3+...+nの複雑さは何ですか？答えはO(n^2)です。ランタイムT(n)を持つアルゴリズムの例は何ですか？

EDIT：私は1 + 2 + 3 + ... + nの合計を計算することについて話していませんでした。

Answer 1

関数の成長の順序は、完了するために必要な操作の数と関係があります。 O（n）を持つ関数の例は、あなたが質問で言及した関数の遅いバージョンです。 Pythonで：

これは、完了に要する時間がnに基づいて線形になるため、O（n）になります。

質問で例として挙げた関数は、n(n+1)/2という操作を1回だけ行うだけで、実際はO（1）です。 n(n+1)/2を計算するのに要する時間は、バーのバックエンドクォークを変更することはありませんが、このような場合には、実際にははとなりません。

Answer 2

ランタイムT（n）を持つアルゴリズムの例を教えてください。

あなたはn回とiは、外側のループの指標であるi回反復し、内側のループを反復する外側のループを持っている場合は、内側のループの本体はT(n)回実行されます。

以下のアルゴリズムであろうそのようなネストされたループの例：

1 
1 2 
1 2 3 

Answer 3

：共通の宿題に溶液であり、以下の形状の数ピラミッドを印刷

for i from 1 to n 
    for j from 1 to i 
     print "$j " 
    print "\n" 

挿入ソートでは、最悪の場合、有界時間ステップであるT(n)=1+2+3+...+nが必要です。選択ソートでは、毎回多くの手順が必要ですが、一般的ではありません。

Answer 4

@ sepp2kは素晴らしい答えを与えるが、ここではその最悪のケースで

---

Insertion Sort（したがって、私たちはこのようなアルゴリズムO(n^2)と呼ばれる）T(N) = 1+2+3+...+nがあり、いくつかの実際の生活のアルゴリズムである： をそれは外側のループを持っていますループn回、内部ループの場合は配列のソートされた部分をループして次の要素を挿入する位置を探します。ソートされた部分は外側ループの繰り返しごとに1ずつ増加するため、最悪の場合の内側ループは1+2+3+4+..+n-1回

間隔をソートした後、用：各反復 iのために、私たちは素朴な実装を使用して、すべての j < i

Interval Graph Coloring（インターバル・パーティション）を介して見ている漸化式 の直接実装：naive implementationを使用して

Longest Increasing Subsequence（LIS）各間隔xの場合、xと矛盾するまでにいくつの間隔を見つけなければならず、問題の答えは最大矛盾番号です。だから、外側のループは、各区間iをループしている間に、内側のループは、ナイーブ素数判定テストを使用して、すべてのj < i

Prime Generatingのためにループしている：もちろん、我々は内のすべてのiにナイーブ素数判定テストを使用して、n内のすべての素数を生成することができますn。それはjがi

---

を分けるかどうかを確認するために、すべてのj < iため、我々ループ、すべてのiのために、ある確かに多くのアルゴリズムは、このような構造を含む、と私は見ているそれらのほとんどが使用することによって改善することができるがありますより鮮明なアルゴリズムまたは高度なデータ構造。

• クイックソート/プライオリティキュー
• を `O（N） 'で行うことができる