在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

因此，结果是9.53674316406e-07我将两个3位数或两个30位数相乘。

我误会什么？

Answer 1

您的数字太小，以至于在相乘时间上没有任何差异。尝试一些适当大小的数字，数量级为10 ^{10 6}。

例如：

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）。