python - すべての O(1) 関数は、実行にまったく同じ時間がかかります。正しいか間違っているか？

Question

「すべての O(1) 関数は、実行にまったく同じ時間がかかります。」正しいか間違っているか？誰かが私に答えを説明できますか?

Answer 1

間違い。O(1) は一定時間を意味します。これは、入力のサイズに関係なく、関数がほぼ同じ時間で実行されることを意味します。ランタイムは入力に合わせてスケーリングされません。

これは、2 つの O(1) 関数がそれぞれ一定の時間内に実行されることを意味しますが、それらの定数は異なる場合があります。したがって、2 つの O(1) 関数fとがありg、それぞれが同じ結果を計算し、同様の入力を期待している場合 (議論のために、リストを期待しているとしましょう)、 の実行時間はfリストのサイズに依存しません。のランタイムも同様ですg。

ただし、fが よりも複雑な (または時間のかかる) 手順で答えを計算する場合g、fの実行時間は よりも長くなりますg。が終了するのに必要な秒数(この値を としましょう)。それでも、入力リストのサイズに依存することはなく、入力リストがどれほど大きくても小さくても同じですが、常に よりも小さくなります。ffsecggsecfsecgsecgsecfsec

O(1) アルゴリズムとして分類されるのは、ランタイムが入力リストのサイズに依存しないためです。特定の数の操作を実行するためではありません。