1

コードがある場合:

for(int i = 0; i<N; i++)
{
   array[i] += N
}

ループが繰り返されるたびに変数 i と N を比較していませんか。さらに言えば、ループが繰り返されるたびに i に 1 を追加していませんか?

では、これはループの反復ごとに 3 つの操作ではないでしょうか。

通常、これらの操作を無視して、このコードは O(n) であると言うのはなぜですか? これらの操作が CPU をどのように使用しているかに関係がありますか?

4

5 に答える 5

12

Big-O 表記法は、操作の実際のコストを扱うのではなく、問題のサイズに応じてそのコストがどのように増加するかを扱います。その範囲でO(n)は、コストが であることを意味するのではなく、問題のサイズに比例nしてコストが増加することを意味します。100 要素のコストが何であれ、200 の場合は 2 倍、1000 の場合は 10 倍になります。同様に、コストは2 次的に増加することを意味します。したがって、問題のサイズが 2 倍になると、操作のコストは 4 倍になり、サイズが 10 倍になると、演算のコストは 4 倍になります。 、コストは100倍になります。O(n^2)

定数はここではあまり重要ではなく、通常は除外されます。さらに、多くの分析では、コストは実際の時間やメモリ コストではなく、他の操作のコストで表されます。たとえば、キーの種類に関係なく、std::map::find関数は を持っていると言われます。O( log N )理由はまったく同じです。要素を含むO( log N )マップで検索するコストが何であれN、それは対数的に増加することを意味します。

やる気を起こさせる例として、かなりばかげた問題を考えてみましょう: 完全な本の内容と 2 つの実装から本の著者を見つけることです。最初の実装では を使用しますstd::map<std::string, std::string>。最初std::stringは本の内容で、2 番目は著者の名前です。2 番目の実装では、本の内容を整数にハッシュ化し、それを unorderedstd::vector< std::pair<int, std::string> >に格納します。intはハッシュであり、std::stringは著者の名前です (ハッシュの衝突はないと仮定します)。マップで本の著者をO( log N )見つけるコストは で、ベクトルで著者を見つけるコストは でO( N )、これはさらに悪いことです。しかし、これらのコストは比較の複雑さを隠しています。マップ内の本の内容全体を比較するコストは膨大になる可能性があります。ハッシュを比較するコストと比較すると、ベクトルの場合に必要なすべての比較よりも、書籍の内容を 1 回比較する方がコストが高くなる可能性があります。

Big-O 表記法は、問題のサイズに応じてコストがどのように増加するかのみを扱い、各操作の実際のコストを隠します。アルゴリズムの複雑さを分析する場合、個々のコストは無視されますが、Big-O 表記はすべてを説明するものではなく、アルゴリズムを実行する実際のコストは一定のコストで発生するため、それらに注意する必要があります。分析で無視しました。

于 2012-06-21T22:40:38.830 に答える
6

Big-O [*]の定義：

2つの関数の場合f、およびはg、次のような数値が存在する場合に限ります。f(n)O(g(n))Mc

for all n > M, |f(n)| <= c * |g(n)|

（ここで、|x|はの絶対値ですx）。

3*nしたがって、この定義から、関数がO(n)次のようになっc = 3ていることが簡単にわかりMます。

「成長率」に関する説明はかなり厄介です（または実際には、上記の定義の動機です）が、Big-Oがどのように機能するかを直感的に理解するのに役立つ場合があります。

なぜ一定の係数を許可するのですか？それを定義しないのはfなぜですか？いくつかの理由-最初は「成長率」のワッフル/モチベーションのためです。私たちが実際にbig-O表記で言っているのは、2倍、3倍などの場合に起こることです。次に、「操作」のアイデアのためです。明確ではありません。整数に1を加算しても、比較やジャンプと同じ時間はかかりません。必ずしも同じ数のCPU命令を使用する必要はありません。では、何を測定しますか？秒？CPUサイクル？どのCPUで、どの速度で、どのバス帯域幅で実行されていますか？アルゴリズムAがx86で非常にわずかに高速である場合はどうなりますか？一方、アルゴリズムBはARMでは非常にわずかに高速ですか？では、どちらかの時間はBig-O（もう一方の時間）でしょうか？O(g)|f(x)| < |g(x)|n > Mn

抽象分析には、特定のハードウェアに根ざしていないアルゴリズムを比較する方法が必要です。Big-Oはそれらのツールの1つです。

したがって、ループごとに3つの定数時間操作を実行するか、100万を実行するかは、アルゴリズムのbig-Oの複雑さとは無関係です。彼らはまだO(n)時間を貢献し、十分な大きさを選ぶだけcです。

log(n)ループごとの操作（ループ時間）を実行する場合nは、もはやO(n)、いずれの場合もc、最終的log(n) > cには十分な大きさになるためnです。Mしたがって、c条件を満たすためのは存在しません。n * log nではありませんO(n)。

[*]アルゴリズムの複雑さに適用されるため、無限大以外の制限に近づく場合にもBig-Oが使用されますが、それについては気にしません。

于 2012-06-22T01:00:55.953 に答える
6

Big-O 記法では、すべての定数要素を削除できます。1 回の反復の比較、加算、およびその他すべてのオーバーヘッドを呼び出しますc。総実行時間はcnでありO(cn) = O(n)、定数因子をドロップする場合です。

この数学的トリックは、大規模なデータセットで機能する関数を比較するために使用されます。時間の複雑さを持つアルゴリズムは、小さなデータセットO(n^2)を使用するアルゴリズムよりも非常に高速である可能性がありますO(n)(後者の定数係数が大きい場合) が、小さなデータセットはアルゴリズムに関係なく高速に処理されることがよくあります。興味深いのは、データセットが大きくなるとどうなるかということです。10 億件のレコードを検索するのに 10 秒かかるのでしょうか、それとも何年もかかるのでしょうか? これは、時間の複雑さに大きく影響されます。

于 2012-06-21T22:18:16.697 に答える
0

定数係数が2または2^10のどちらであるかは重要ではありません。最も重要なことは、「nの増加と比較して実行時間がどのように増加するか」です。コードがコンパイラによって最適化されるという事実のためにも、定数係数は削除されます。c最適化後も3に等しいかどうかはわかりません。

www.coursera.orgAlgorithms: Design and Analysis, Part Iオンラインコースに精通することをお勧めします。定数因子の削除とBigO表記についてのいくつかの（短い）講義があります。

于 2012-06-21T22:27:26.780 に答える
0

n が無限大に近づくと、n に比例すると言います。したがって、プロセッサでどれくらいの時間がかかるかわからない n*(4 操作) は、n に比例します。

于 2012-06-21T22:18:24.763 に答える