2

私はアルゴリズム分析ドメインの新人です。スタック オーバーフローの質問 " "Big O" 表記の平易な英語の説明は何ですか?を読みましたが、O(2n^2)とO(100 n^2)は と同じO(n^2)です。n = 4 とすると、操作の数は次のようになるため、これはわかりません。

  • O(2 n^2)= 32 操作
  • O(100 n^2)= 1600 操作
  • O(n^2)= 16 操作

これらの異なる操作数を同じものとして扱うことになっている理由を説明できる人はいますか?

4

3 に答える 3

3

O(f(n))というのは、前述の関数が一定の時間によって制限されていることを意味しf(n)ます。gが の倍数で境界付けられている場合、 の倍数で100 f(n)も境界付けられていf(n)ます。具体的には、O(2 n^2)に対して 16 を超えないことを意味するのではなく、 に関係なく、固定されn = 4た に対して16 を超えない ことを意味します。nC * 2n^2Cn

于 2013-09-02T11:48:24.190 に答える
1

これは分類であるため、アルゴリズムをいくつかの複雑さのクラスに配置します。クラスは、O(1)、O(n)、O(n log n)、O(n ^ 2)、O(n ^ 3)、O(n ^ n) などです。定義により、2 つのアルゴリズムがn が無限大になるとき、差が一定の係数である場合は、同じ複雑さのクラスです (big-oh 表記は、n の値が大きい場合のアルゴリズムの複雑さを比較するためのものです)。

于 2013-09-02T11:48:43.870 に答える