Beeinflusst die Anzahl der Vergleiche in der gleichen for-Schleife die Zeitkomplexität?

Question

In einer Beispielaufgabe sollte ich prüfen, ob alle Elemente in einem Array identisch sind. DIESE FRAGE IST NICHT DIE EFFIZIENTESTE MÖGLICHKEIT, DIES ZU TUN. Es geht vielmehr um diese beiden Lösungen.

for(var i=0; i < set.length-1; i++) 
    { 
    if (set[i] != set[i+1]) // could have compared all elements to the firstelement instead of switching 
    { 
    isTrue=false; 
    } 

    } 

Dieser obige Algorithmus vergleicht jeden Index mit dem Index danach.

var firstIndex=set[0]; 
for(var i=0; i < set.length-1; i++) 
{ 
    if(set[i] != firstIndex) 
    { 
     isTrue=false; 
    } 
} 

Während dieser Algorithmus vergleicht den aktuellen Index mit dem ersten Index. Obwohl diese Algorithmen mindestens O (N) sind. Beeinflusst der Unterschied in den Vergleichen die Komplexität von Zeit und Raum?

Answer 1

Nun lässt klare Dinge

Zeitkomplexität für beide O(n) wäre. Die Raumkomplexität ist O(1).

Dinge wie Array-Index-Zugriff oder etc hat keinen Einfluss auf die Big-O-Timne-Komplexität.

Obwohl diese Algorithmen mindestens O (N) sind.

Dies sind O(n) nicht atleast.

Sie können Dinge tun, wie

if(set[i] != firstIndex) 
{ 
    isTrue=false; 
    break; 
} 

Laufzeit keine Zeit Komplexität verbessern

Answer 2

Platzkomplexität: Keine Änderung, da Sie keine zusätzliche Variable/Datenstruktur verwenden (firstIndex im zweiten Snippet wird nicht berücksichtigt, da es konstanten Platz benötigt).

Zeit Komplexität: wenig oder keine Änderung. In beiden Snippets führen Sie einen einzigen Vergleich durch, aber der erste Snippet wird etwas langsamer sein, da der Zugriff auf Arrays im Vergleich zum direkten Variablenzugriff langsamer ist.