Wie viele Anweisungen werden für eine O (1) -Operation in einer Liste mit n Elementen ausgeführt?

Question

a. immer eine
b. nicht mehr als n
c. einige feste Nummer
d. nicht mehr als 3

Ich wählte "nicht mehr als n", aber mein Lehrer sagte mir, dass es falsch ist. Sie gab nicht den Grund, warum es falsch war, und wenn es falsch ist, was ist die Antwort darauf?

Answer 1

Die richtige Antwort ist c. eine feste Nummer. Die Idee ist, dass die Operation unabhängig von der Anzahl der Elemente immer die gleiche Zeit benötigt. See constant time

Answer 2

Einige feste Zahl.

O(1) bedeutet konstante Zeit oder es bedeutet, dass die Ausführungszeit nicht von der Größe der Eingabe abhängt (obwohl es länger dauern kann, bis das Ende des Universums ausgeführt wird).

Answer 3

Einige feste Zahl wäre die richtige Antwort. Sie können eine Funktion haben n-1 oder n + 1 Operationen und b)/d) wäre erfüllt, wäre aber immer noch in O (n) Zeit. O (1) Zeit erfordert, dass es eine feste Zahl C gibt, so dass die Funktion in C-Operationen unabhängig von n ausgeführt wird.

Es sollte ein Algorithmen-Tag statt ein Java-Tag sein: P

Answer 4

Die Antwort ist keines von ihnen. Die folgende Methode ist O (1).

1. Klar ist es nicht immer einer.
2. Es ist manchmal mehr als n.
3. Offensichtlich ist es keine feste Zahl.
4. Es ist immer mehr als drei.

//

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