我已经使用数组编写了一个Happy number程序，请帮助我如何计算时间复杂度？如果在用等于其所有位数的平方和的数字重复替换之后，使我们得到数字“ 1”，则该数字将被称为快乐数字。所有其他（不满意的）数字将永远不会达到“ 1”。相反，它们将陷入一个不包含“ 1”的数字循环中。
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 = result
def sqr_digits(num):
result = 0
while(num > 0):
digit = num % 10
result += digit ** 2
num //= 10
return result
num = 145
print(happy(num))
[注意：在回答问题时，我忘记了您的代码正在使用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))
希望您已经正确理解了这个概念...
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句