python - 为什么我计算数字阶乘的算法的时间复杂度是 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 (运行时间为O(N^2))。然而，对于更大的数字，它 uses Karatsuba算法，其估计复杂度为 O(N^1.58)(N = 数字长度)。由于乘法不是在 O(1) 内实现的，因此时间复杂度不是线性的。

如果您想研究的话，还有“更快”的乘法算法(例如 Toom-Cook 和 Schönhage-Strassen)。