python-3.x - DigitalRoot 的时间复杂度是多少？

Question

示例 1： 输入：n = 1 输出：1 说明：1 的数字根为 1

示例 2： 输入：n = 99999 输出：9

解释：99999 的位数和是 45，不是个位数，因此 45 的位数和是 9，是个位数。

有人可以帮助我的代码的时间复杂度是多少？我认为它的 O(loglog(N)) 但不确定。

def sumOfDigits(n):
    if n==0:
        return 0
    else:
        return int(n%10) + sumOfDigits(n//10)
        

def digitalRoot(n):
    ans = n
    if n<=9:
        return n
    else:
        while ans>9:
            ans = sumOfDigits(ans)
            
        return ans

标签： python-3.xrecursion

Answer 1

让我们计算第一步的复杂度

如果一个算法取决于它包含的位数，则该算法的时间复杂度为：

O(log ₁₀ (n))

这是因为我们以 10 为基数表示数字。例如，这将使关系一清二楚：

O(log ₁₀ (100)) = 2

O(log ₁₀ (1000)) = 3

O(log ₁₀ (10000)) = 4

现在这在一定程度上回答了这个问题，如果我们只将所有数字相加一次，我们就会停在这里。

但既然我们不是，让我们继续前进。现在，如果所有数字都添加一次，我们再次添加该结果数字的数字。使它成为一个收敛的系列。

因此答案可能是：

O(log ₁₀ (n)) + O(log ₁₀ (log ₁₀ (n))) + O(log ₁₀ (log ₁₀ (log ₁₀ (n)))) + ...

这是我对复杂性上限的最佳估计。