为什么我的算法计算数字阶乘的时间复杂度为 O(n^2) 而不是预期的 O(n)？

Question

对这个很困惑。我有一个算法的三个实现来计算一个数字的阶乘。我计算了每个输入大小高达 2500 的平均运行时间并绘制了它们。从目测来看，它们似乎没有表现出线性时间复杂度，而是二次的。为了进一步探索这一点，我使用了曲线拟合，并确认了目视检查的结果。

为什么会这样？这可能与 Python 中小数的乘法处理方式有关吗？（看这里Complexity of recursive factorial program）

import matplotlib.pyplot as plt
import numpy as np
import random
from scipy.optimize import curve_fit
import statistics as st
import timeit
import sys

sys.setrecursionlimit(3000)

def factorial_iterative(n):
    ''' Function that calculates the factorial of its argument using iteration
    
    Assumes that its argument is a positive integer
    Uses iteration
    Returns the factorial of the argument
    '''
    factorial = n
    while n > 1:
        n -= 1
        factorial *= n
    return factorial

def factorial_recursive_non_tail(n):
    ''' Function that calculates the factorial of its argument using non-tail recursion
    
    Assumes that its argument is a positive integer
    Uses non-tail recursion
    Returns the factorial of the argument
    '''
    if n == 1:
        return 1
    else:
        return n * factorial_recursive_non_tail(n - 1) 

def factorial_recursive_tail(n, factorial):
    ''' Function that calculates the factorial of its argument using tail recursion
    
    Assumes that its first argument is a positive integer
    Assumes that its second argument is an accumulator with a value of 1
    Uses tail recursion
    Returns the factorial of the argument
    '''
    if n == 1:
        return factorial
    else:
        return factorial_recursive_tail(n-1, n*factorial)

# max input size
n = 2500

# create input values list and initialise lists to store runtimes
n_values = list(range(1, n+1))
fact_iterative_runtimes_list = []
fact_non_tail_runtimes_list = []
fact_tail_runtimes_list = []

# for each n, time the implementation 100 times, calculate avg runtime, and store in dedicated list
for i in n_values:
    # iterative
    fact_iter_runtime = timeit.repeat(lambda: factorial_iterative(i), number=1, repeat=100)
    fact_iterative_runtimes_list.append(st.mean(fact_iter_runtime))

    # non-tail recursive
    fact_recursive_non_tail_runtime = timeit.repeat(lambda: factorial_recursive_non_tail(i), number=1, repeat=100)
    fact_non_tail_runtimes_list.append(st.mean(fact_recursive_non_tail_runtime))

    # tail recursive
    fact_recursive_tail_runtime = timeit.repeat(lambda: factorial_recursive_tail(i, 1), number=1, repeat=100)
    fact_tail_runtimes_list.append(st.mean(fact_recursive_tail_runtime))

# Plot avg runtimes against input sizes
plt.figure(figsize=(18, 6))
plt.plot(n_values, fact_iterative_runtimes_list, label = "Iterative")
plt.plot(n_values, fact_non_tail_runtimes_list, label = "Recursive non-tail")
plt.plot(n_values, fact_tail_runtimes_list, label = "Recursive tail")
plt.ylabel("Running time (seconds)")
plt.xlabel("Values of n")
plt.legend()
plt.show()

Answer 1

正如@Konrad 指出的那样，这是由于 Python 中处理乘法的方式所致。

对于较小的数字，简单的 school level multiplication (which runs in O(N^2)) is used. However, for bigger numbers, it uses the Karatsuba 算法，估计复杂度为 O(N^1.58)（N = 数字的长度）。由于乘法未在 O(1) 中实现，因此您的时间复杂度不是线性的。

如果您想研究一下，可以使用“更快”的乘法算法（例如 Toom-Cook 和 Schönhage-Strassen）。

为什么我的算法计算数字阶乘的时间复杂度为 O(n^2) 而不是预期的 O(n)？

Why is the time complexity of my algorithm to calculate the factorial of a number O(n^2) instead of the expected O(n)?

python

algorithm

big-o

factorial