我用數(shù)組寫了一個Happy number程序，請問如何計算時間復雜度？如果在用等于其所有數(shù)字的平方和的數(shù)字反復替換它之后，將我們引向數(shù)字“1”，則任何數(shù)字都將被稱為快樂數(shù)字。所有其他（不快樂的）數(shù)字永遠不會達到“1”。相反，他們將陷入不包括“1”的數(shù)字循環(huán)中。def happy(num): ls = [] result = 0 while True: result = sqr_digits(num) if result == 1: return True elif result in ls: return False # not happy else: ls.append(result) num = resultdef sqr_digits(num): result = 0 while(num > 0): digit = num % 10 result += digit ** 2 num //= 10 return result num = 145 print(happy(num))
1 回答
慕森王
TA貢獻1777條經(jīng)驗 獲得超3個贊
[注意：在回答問題時，我忘記了你的代碼正在使用digit^2，但我只是提供了基于digit. 復雜度計算機制相同。digit^2如果您閱讀答案，您可以輕松地自己找出復雜性。當我有時間時，我會更新答案。希望你不會介意]
好吧，如果有一個 number n(base 10)，那么它最多可以有l(wèi)og10(n) + 1數(shù)字。我希望，我不會解釋它......只是谷歌它how many digits in a 10 based number and how to find it using log。
現(xiàn)在，讓我們解釋一下所提供算法的復雜性：
只有當總和變?yōu)閭€位數(shù)時，算法才會停止。
所以，我們可以計算位數(shù)，我們必須添加，這將是最終的復雜性。
精確計算該算法的復雜性是不可能的，但我們可以計算最壞情況的復雜性……最大數(shù)當然是3 digits，999所以我們總是考慮d nines一個d digits數(shù)字。
1st iteration:: no of digits, d1 = log10(n) + 1, and n1 = d1*10, (originally d1*9 in worst
case, but we're taking much worse and the reason is to calculate complexity properly)
2nd iteration:: no of digits, d2 = log10(n1) + 1 and n2 = d2*10
= log10(d1*10) + 1
= log10(d1) + 1 + 1 (cause, log(a*b) = log(a)+log(b))
= log10(log10(n) + 1) + 1 + 1
3rd iteration:: no of digits, d3 = log10(log10(log10(n)+1)+1) + 1 + 1 + 1
...
...
我想，你可以看到這是怎么回事。總位數(shù)可以寫為：
total digits = d1 + d2 + d3 + ....
By removing the 1 inside log's(for simplification) we can write simply:
total digits = log10(n) + 1 + log10(log10(n)) + 2 + log10(log10(log10(n))) + 3 + ...
but, log10(n) + 1 >>> log10(log10(n)) + 2
所以，我們可以看到最終的復雜度是由 決定的log10(n)。最終的復雜性將是：
complexity = c * log10(n) // here is "c" a constant such that c * log10(n) > total digits
which
we can say O(log10(n))
我希望你已經(jīng)正確理解了這個概念......
添加回答
舉報
0/150
提交
取消