4

[1,2,3,4,5,6,7,8,9,10] という配列が与えられた場合、次のことを行うアルゴリズムがあるとします。

for i in 0..a.length
  for j in 0..a.length
    ...

これは、要素ごとに配列全体をトラバースするため、O(n^2) の Big O ランタイムになります。

しかし、内側のループが外側のインデックスから順方向にのみトラバースした場合はどうなるでしょうか?

for i in 0..a.length
  for j in i..a.length
    ...

つまり、比較すると、最初のアルゴは反復ごとに n 個の要素を調べます (外側のループ)。2 番目のアルゴリズムは次のようになります。

  • 最初の反復で n 個の要素
  • 2 回目の繰り返しで n-1 要素
  • 3 回目の繰り返しで n-2 要素
  • ...
  • 最後の反復で 1 要素

この種のアルゴリズムの Big O ランタイムを計算するとき、それはまだ O(n^2) ですか?

4

2 に答える 2

10

これはまだO（n ^ 2）です。合計1+2 + ... + nはn（n + 1）/ 2であり、これはO（n ^ 2）です。

より一般的には、任意の多項式関数p（n）の場合、p（1）+ p（2）+ ... + p（n）の合計はO（np（n））です。nの任意の累乗の合計について推論する必要があるため、この証明ははるかに困難ですが、それは確かに真実です。これは、たとえば、jからnの範囲の内側のループの内側に3番目のループをネストした場合、実行時間はO（n ^ 3）になることを意味します。

于 2012-06-14T17:35:07.750 に答える
0

a がその特定の配列である場合、そのアルゴリズムの時間計算量は一定 (または O(1)) です。多分私はあなたがあまりにも文字通りに尋ねたことを読んだかもしれませんが、最も狭い範囲が O(n^2) であるためには、a は [1,2,...,n] のような配列でなければなりません。a が明示的にサイズ 10 である場合、アルゴリズムは常に同じステップ数で実行されます。

うまくいけば、この答えは不必要でしたが、私は個別の数学クラスのティーチングアシスタントであり、これに非常によく似たひっかけ問題をかなり頻繁に出しています。質問を誤解していた場合は、時間を無駄にして申し訳ありません。また、すでに投稿された回答はとても良いです！

于 2012-06-14T21:30:32.923 に答える