Was ist die zeitliche Komplexität dieser Lösung O (N) oder O (LogN)?

Question

https://codility.com/programmers/lessons/1-iterations/

In Anbetracht dieser:

if (largestHole > (bin.length - i) && subHole < (bin.length - i)) { 
    break; 
} 

Wenn die Länge des größten Loch weit so geringer ist als die Länge der verbleibenden Ziffern

es bricht die Schleife überprüfen Diese Linie let bin = parseInt(N, 10).toString(2); ist wandle eine Zahl von Base 10 in Base 2 String um, über die ich iteriere.

function solution(N) { 
    let bin = parseInt(N, 10).toString(2); 
    let subHole = 0; 
    let largestHole = 0; 
    for (var i = 0; i < bin.length; i++) { 
    if (largestHole > (bin.length - i) && subHole < (bin.length - i)) { 
     break; 
    } 
    if (bin[i] === '0') { subHole++; } 
    else { 
     if (subHole > largestHole) { 
     largestHole = subHole; 
     } 
     subHole = 0; 
    } 
    } 
    return largestHole; 
} 

https://codility.com/programmers/lessons/1-iterations/

Answer 1

Noch O (n). Die Komplexität berücksichtigt keine Koeffizienten. Außerdem wäre eine O (log n) -Funktion etwas wie eine binäre Suche.

EDIT: eine einfache Erklärung eines O (log n) Algorithmus: Nehmen Sie binäre Suche zum Beispiel. Sie haben eine Zahl x von beispielsweise 1 bis 100, und sie ist in einem sortierten Array mit n Zahlen von 1 bis 100 versteckt. Sie beginnen von der Mitte des Arrays, abhängig von der Größe der mittleren Zahl im Vergleich zu x, Sie suche die linke Hälfte oder die rechte Hälfte des Arrays. Der Prozess wird rekursiv fortgesetzt, bis Sie die Nummer gefunden haben.

Zum Beispiel möchte ich 5 in [1,3,5,6,7,9,10] finden. Ich fange vom 4. Platz an. Es ist 6, und es ist größer als 5, also suchen wir die linke Hälfte, von 1 bis 5. Dann überprüfe ich die mittlere Position erneut in dem verengten Bereich, der 3. Es ist kleiner als 5, also suchen wir die rechte Hälfte. An dieser Stelle haben wir nur eine Zahl übrig - das ist 5.

Die Suche teilt das Array in zwei Hälften, so dass das schlechteste Szenario log 2 n (Basis 2 Logarithmus von n) dauern würde. Das ist eine O (log n) -Funktion.

Wie gesagt, der Koeffizient der Komplexität spielt keine Rolle. Zum Beispiel dauert die Bubble-Sortierung normalerweise ungefähr (n^2)/2 Umdrehungen, aber wir zählen das einfach als O (n^2) und ignorieren den Koeffizienten 1/2.

Answer 2

Ich stimme mit O (n) überein, aber tatsächlich hängt es von der Implementierung der parseInt-Funktion ab.