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

Question

A. immer eins
b. nicht mehr als n
c. eine feste Anzahl
d. nicht mehr als 3

Ich habe "nicht mehr als n" gewählt, aber meine Lehrerin hat mir gesagt, dass es falsch ist. Sie hat mir nicht den Grund genannt, warum es falsch ist, und wenn es falsch ist, was ist dann die richtige Antwort?

Answer 1

Die Antwort ist keine von ihnen. Die untenstehende Methode ist O(1).

1. Es ist klarerweise nicht immer eins.
2. Manchmal ist es mehr als n.
3. Es ist klarerweise keine feste Nummer.
4. Es ist immer mehr als drei.

//

public void run ( Liste der Größe n )
{
     for ( int i = 0 ; i < 100 + ( n  % 100 ) ; i ++ )
     {
          Schritt ( ) ;
     }
}

Answer 2

Die richtige Antwort ist c. eine feste Zahl. Die Idee ist, dass die Operation immer die gleiche Zeit benötigt, unabhängig von der Anzahl der Elemente. Siehe konstante Zeit

Answer 3

Eine feste Nummer.

O(1) bedeutet Konstante Zeit oder es bedeutet, dass die Ausführungszeit nicht von der Größe des Eingabewerts abhängt (auch wenn es länger dauern kann als das Ende des Universums, um ausgeführt zu werden).

Answer 4

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

Es sollte auch ein Algorithmen-Tag anstelle eines Java-Tags sein :P