この質問は、さまざまな回答で提案されているアルゴリズムが O(1) か O(n) かについて、いくつかの混乱と多くのコメントを引き起こしました。
簡単な例を使用して、2 つの観点を説明しましょう。
、およびが既知の、null でないlong
x
のようなlong を見つけたいと考えています。a * x + b = 0
a
b
- 明白な 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 にあるため、 Javaを追加しましたが、この質問は言語に依存しません。