algorithm - n個の要素を持つリストでO（1）操作に対して実行される命令はいくつですか？

Question

a。常に1つ
b。nc以下
。いくつかの固定数
d。3つ以下

「n以下」を選びましたが、先生から間違っていると言われました。彼女はそれが間違っていた理由を述べませんでした、そしてそれが間違っているなら、それに対する答えは何ですか？

Answer 1

答えは、どれでもないです。以下のメソッドは O(1) です。

1. 明らかに、それは常に 1 つではありません。
2. n を超える場合もあります。
3. 一定数ではないことは明らかです。
4. 常に 3 つ以上です。

///

public void run ( List of size n )
{
     for ( int i = 0 ; i < 100 + ( n  % 100 ) ; i ++ )
     {
          step ( ) ;
     }
}

Answer 2

正解はcです。いくつかの固定数。要素の数に関係なく、操作には常に同じ時間がかかるという考え方です。 一定時間を参照してください

Answer 3

いくつかの固定番号。

O(1)一定の時間を意味するか、実行時間が入力のサイズに依存しないことを意味します (実行に宇宙の終わりよりも時間がかかる場合があります)。

Answer 4

いくつかの固定数が正解です。関数に n-1 または n+1 操作を実行させることができ、b)/d) は満たされますが、それでも O(n) 時間になります。O(1) 時間では、n に関係なく、関数が C 演算で実行されるように固定数 C が必要です。

Javaタグの代わりにアルゴリズムタグもあるはずです:P