這個解決方案的時間複雜度是O（N）還是O（LogN）？

Question

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

考慮到這一點：

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

如果最大孔的長度，到目前爲止小於其餘數字的長度，以檢查它打破了環

此行let bin = parseInt(N, 10).toString(2);是將一個數字從基數10轉換爲基數2的字符串，這是我重複的。

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

仍然爲O（n）。複雜性不考慮係數。另外，O（log n）函數就像二分查找一樣。

編輯： O（log n）算法的簡單解釋： 以二分查找爲例。你有一個從1到100的數字x，它隱藏在一個包含從1到100的n個數字的有序數組中。從數組中間開始，取決於與x相比中間數字的大小，你搜索數組的左半部分或右半部分。該過程遞歸地繼續，直到找到數字。

例如，我想在[1,3,5,6,7,9,10]中找到5。 我從第4位開始。它是6，大於5，所以我們從1到5搜索左半部分。然後，我再次在縮小的範圍內檢查中間位置，這是3。它小於5，因此我們搜索右半部分。在這一點上，我們只剩下一個數字 - 它是5.

搜索不斷將數組分成兩半，所以最糟糕的情況是log 2 n（以n的對數2爲底）。這是一個O（log n）函數。

但是，正如我所說的，複雜性的係數並不重要。例如，Bubble排序通常需要大約（n^2）/ 2圈，但我們只需將其計爲O（n^2），忽略1/2係數。

Answer 2

我同意O（n），但實際上它取決於parseInt函數的實現。