爲什麼代碼O（log n）的時間複雜度？

下面是Gayle Laakmann編寫的「破解編碼訪問」一書中給出的代碼。在此時刻的代碼的複雜性找到： -爲什麼代碼O（log n）的時間複雜度？

int sumDigits(int n) 
{ int sum=0; 
while(n >0) 
{ 
    sum+=n%10; 
    n/=10 
} 
return sum ; 
}

我知道時間複雜度應爲n個位數。根據該書，其運行時間複雜度爲O（log n）。本書提供了簡要描述，但我不明白。

來源

2017-10-07 rani rawat

n中的位數是log n。（或者O複雜度近似接近。） –

n不減1，所以不是線性的。在循環中的每次傳遞，n減少一個數量級 – Tim

[代碼複雜度]的可能的重複（https://stackoverflow.com/questions/39797459/code-complexity） –

while(n > 0) 
{ 
    sum += n % 10; 
    n /= 10; 
}

，是多少步驟將這個while循環採取使n來0？你在每一步中所做的事情，將n與10分開。所以，你需要做到這一點k次，以達到0。請注意，k是n中的位數。

讓我們一步一步來吧：第一步是當n > 0，您將n除以10。如果n仍然是正數，則將它除以10。你得到的是n/10/10或n/(10^2)。第三次後，其n/(10^3)。而且經過k次，其n/(10^k) = 0。循環將結束。但這不是0在數學意義上，它是0，因爲我們處理整數。你真正擁有的是|n|/(10^k) < 1，其中k∈N。

所以，我們現在有這樣的：

n/(10^k) < 1 
n < 10^k 
logn < k

順便說一句。其也n/(10^(k-1)) > 1，所以其：

k-1 < logn < k。（btw。別忘了，這是基地10）。

所以，你需要做logn + 1步驟才能完成循環，這就是爲什麼它的O(log(n))。

來源

2017-10-07 17:08:54

感謝Adnan爲這個完美的答案。 –

邏輯運行的次數是log（n）到10的基數，它等於（log（n）到基2）/ log（10）到2）的基數。就時間複雜度而言，這只是O（log（n））。請注意，以10爲底的log（n）是您如何表示n中的位數。

來源

2017-10-22 17:04:24

爲什麼代碼O（log n）的時間複雜度？

回答

相關問題