在 Python 中测量乘法大 O

Question

据我了解，乘法的复杂度阶数是二次的，因此如果将两个 1 位数字相乘将进行 1 次运算，将两个 2 位数字相乘将进行 4 次运算，将两个 3 位数字相乘数字 9 操作等等。

我想通过对简单地将两个数字相乘的程序的执行计时来了解这种复杂性。没想到不管数字大小，执行时间都是一样的

import time

num1 = 135
num2 = 342

start = time.time()
total = num1 * num2
finish = time.time()
elapsed = finish - start

print elapsed

所以如果我将两个 3 位数字或两个 30 位数字相乘，结果是 9.53674316406e-07。

我误会了什么？

Answer 1

您的数字太小了，无法显示相乘所需时间的差异。尝试一些大小合适的数字，大约为 10^10⁶.

例如：

import time

for k in range(10):
    num = 10**(10**k)

    start = time.time()
    total = num * num
    finish = time.time()
    elapsed = finish - start

    print k, elapsed

在我的机器上输出：

0 2.86102294922e-06
1 5.00679016113e-06
2 2.14576721191e-06
3 7.86781311035e-06
4 0.000285148620605
5 0.010409116745
6 0.391373157501
7 15.7926459312

（我还在等8）。

Answer 2

你是正确的，对于大数乘法是二次的（或者甚至使用更好的算法至少 >O(n)）。只要它们适合 64 位数字，您就可能看不到任何变化。有两个问题你运行到 64 位数字最多可以容纳 9.223372e+18（一个 19 位数字），而你的 30 位数字将只是两个 64 位数字。尝试使用几个 64 位数字（比如 10000，这将是一个 180000 位数字）：

import time
import random

for i in range(0, 190000, 10000):
    a = random.randint(10**i, 10**(i+1)-1)
    b = random.randint(10**i, 10**(i+1)-1)

    start = time.time()
    c = a*b
    end = time.time()

    print i, str(c)[0], end-start # str(c)[0] just in case optimization on c (unlikely)

结果：

0 1 0.0
10000 3 0.000855922698975
20000 5 0.00253701210022
30000 1 0.00445008277893
40000 4 0.00767087936401
50000 3 0.00982689857483
60000 1 0.0133669376373
70000 9 0.0174329280853
80000 4 0.0230648517609
90000 3 0.0251250267029
100000 4 0.0296058654785
110000 4 0.0344429016113
120000 3 0.0401389598846
130000 1 0.0457019805908
140000 2 0.0524950027466
150000 1 0.0619490146637
160000 5 0.0693421363831
170000 2 0.068922996521
180000 2 0.0755639076233

基于 90000 和 180000 的结论是 >O(n) 但是

在 Python 中测量乘法大 O

Measuring Big O of multiplication in Python

python

math

big-o