4

この質問は、さまざまな回答で提案されているアルゴリズムが O(1) か O(n) かについて、いくつかの混乱と多くのコメントを引き起こしました。

簡単な例を使用して、2 つの観点を説明しましょう。

、およびが既知の、null でないlongxのようなlong を見つけたいと考えています。a * x + b = 0ab

  • 明白な O(1) アルゴリズムはx = - b / a
  • はるかに遅いアルゴリズムは、考えられるすべての long 値をテストすることで構成され、平均で約 2^63 倍遅くなります。

2 番目のアルゴリズムは O(1) または O(n) ですか?

リンクされた質問に示されている議論は次のとおりです。

  • 最悪の場合、考えられるすべての long 値をループする必要があるため、O(n) です。
  • これは O(1)です。これは、その複雑さが の形式c x O(1)であるためです。ここc = 2^64で、 は定数です。

O(1) であるという主張は理解できますが、直感に反するように感じます。

ps:元の質問が Java にあるため、 を追加しましたが、この質問は言語に依存しません。

4

5 に答える 5

7

複雑さは、変数 N がある場合にのみ関連します。したがって、質問はそのままでは意味がありません。質問が次の場合:

はるかに遅いアルゴリズムは、N 値の範囲内のすべての可能な値をテストすることで構成され、平均で約 N 倍遅くなります。

2 番目のアルゴリズムは O(1) または O(N) ですか?

答えは次のようになります。このアルゴリズムは O(N) です。

于 2012-09-07T13:34:11.087 に答える
5

Big O describes how an algorithm's performance will scale as the input size n scales. In other words as you run the algorithm across more input data.

In this case the input data is a fixed size so both algorithms are O(1) albeit with different constant factors.

「n」を数値のビット数を意味する場合 (つまり、64 ビット長であるという制限を削除した場合)、特定のビット サイズ n についてアルゴリズムがどのようにスケーリングするかを分析できます。

このシナリオでは、最初はまだ O(1) (Qnan のコメントを参照)ですが、2 番目は O(2^n) になります。

MIT の「Introduction to Algorithms」コースの初期の講義を視聴することを強くお勧めします。これらは、数学を十分に理解していることを前提としていますが、Big O (および Big Omega/Theta) の優れた説明です。

于 2012-09-07T13:37:23.230 に答える
3

Checking every possible input is O(2^N) on the number of bits in the solution. When you make the number of bits constant, then both algorithms are O(1), you know how many solutions you need to check.

于 2012-09-07T13:37:18.110 に答える
1

事実: コンピューターで実際に実行するアルゴリズムはすべて O(1) です。これは、宇宙の計算能力が有限であるためです (原子の数は有限であり、ビッグバンから有限の秒数が経過しています)。

これは真実ですが、物事を考えるのにあまり有用な方法ではありません。実際に big-O を使用する場合、一般に、関連する定数は漸近項に比べて小さいと想定します。そうでない場合、漸近項を与えるだけでは、アルゴリズムの実行方法について多くの情報が得られないからです。定数は通常、「配列またはハッシュマップを使用しますか」のようなものであり、最大で約30倍異なり、入力は10 ^ 6または10 ^ 9であるため、これは実際にはうまく機能します。線形アルゴリズムは定数因子よりも重要です。この規則 (アルゴリズム #2 など) を尊重しない big-O の議論は無意味です。

于 2012-09-07T19:50:09.763 に答える
0

a または b の値が何であれ、最悪のケースは 2^64 または 2^32 または 2^somevalue の値をチェックすることです。このアルゴリズムの複雑さは O(2^k) 時間 (k は long 値を表すために使用されるビット数)、または a と b の値を考慮すると O(1) 時間です。

于 2012-09-07T13:40:23.553 に答える