algorithm - 漸近境界と実行時間の関係は?

Question

二分探索を例に取りましょう。最良の場合の実行時間は、最初の比較で得られます。

key_to_find == (imin + imax) / 2;

そして、最良の場合の実行時間は O(1) で表されます。私はそれを完全に理解していますが、私を混乱させるのは、O(1) が使用される理由と、なぜ Θ(1) または他の表記法を使用できないのかということです。

すなわち。実行時間を表すためにどの表記法を使用する必要があるかを特定する方法 (最高、平均、または最悪のケース)。

Answer 1

O 表記と Θ 表記は、最良のケース、平均的なケース、または最悪のケースとは直接関係ありません。それらは、関数の漸近境界に使用されます。次のように書くことができます: 47n lg n = O(n lg n), 3n^2 + 4n = O(n^2)

そしてOとΘ表記の違いがあります。O は「せいぜい (定数係数を使用)」を意味し、Θ は「等しい (定数係数を使用)」を意味します。たとえば、47n ln n = O(n^2) ですが、Θ(n^2) ではありません。

最良のケース、平均的なケース、または最悪のケースを表現したい場合は、通常、「最良のケースは O(1) (または Θ(1))、平均的なケースは O(lg n)、最悪のケースは O( n)」

「実行時間はO(x)」という場合もありますが、これはつまり、実行時間は最大でも x に比例するということです。「実行時間は Θ(x) です」というのは、実行時間は常に x に比例するということです。

Answer 2

You can use any notation you want. Big Theta is the most precise so you should use it whenever you know it. As a side note, O(1) is equivalent to Θ(1) in the context of complexity analysis (where the number of operations is an integer, i.e. one cannot have O(1/n) as a complexity).