嵌套 Big-O 的总时间复杂度

Question

我编写了一个程序来计算一个数的阶乘，并将结果的数字存储在一个 Python 列表中。

为了找到阶乘，我运行一个采用 O(N) 并将结果存储在“ans”中的循环
为了找到“ans”的位数，我运行另一个采用 log10(ans) 的循环。
最后，我就地反转列表

我正在努力查看总时间复杂度 (TC) 是多少。我相信：

TC = O(d) = O(log10(ans))，因为对于 N->inf，d > N，其中 d（ans 中的位数）= log10(ans)，并且 ans ∈ O( N).

我错了吗？是否有任何其他方式来表达总 TC，也许类似于嵌套的 Big-O:

O(log10(O(N))) ???

注：log10表示以10为底的对数

下面是我的代码：

def factorial(N):
        ans = N
        ans_digits = []

        # 1. O(N)
        while N > 1:
            N -= 1
            ans *= N

        # 2. O(log10(ans))
        while ans > 0:
            digit = ans % 10
            ans //= 10
            ans_digits.append(digit)

        # 3. O(log10(ans))
        for i in range(len(ans_digits)//2):
            temp = ans_digits[i]
            ans_digits[i] = ans_digits[-(i+1)]
            ans_digits[-(i+1)] = temp

        # Shorter way of doing 2 and 3: O(log10(ans))
        #ans_digits = str(ans).split()

        return ans_digits

Answer 1

感谢@user3386109，通过 Stirling's approximation 阶乘，时间复杂度可以用 N 表示为：

TC = O(d) = O(logN!) = O(NlogN - c.N + O(logN)) = O(NlogN)

其中 log 以 10 为底，N 是整数。

嵌套 Big-O 的总时间复杂度

Total Time Complexity of Nested Big-O's

algorithm

data-structures

time-complexity

computer-science