[注意:在回答问题时,我忘记了您的代码正在使用digit^2
,但我只是提供了基于digit
. 复杂度计算机制相同。如果您阅读答案,您可以自己轻松找出复杂性digit^2
。当我有时间时,我会更新答案。希望你不会介意]
好吧,如果有一个数字n(base 10)
,那么它最多可以有log10(n) + 1
数字。我希望,我不会解释它......只是谷歌它how many digits in a 10 based number and how to find it using log
。
现在,让我们解释一下所提供算法的复杂性:
只有当总和变成一位数时,算法才会停止。
所以,我们可以计算位数,我们必须添加,这最终将是复杂性。
精确计算该算法的复杂性是不可能的,但我们可以计算最坏情况的复杂性......3 digits
当然,最大数可能是999
,所以我们总是会考虑d nines
一个d digits
数字。
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
...
...
我想,你可以看到这是怎么回事。总位数可以写成:
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))
我希望你已经正确理解了这个概念......