关于自己写的和时间复杂度有关的代码和测试/python
-
import matplotlib.pylab as plt
import numpy as np
import math
import statistics
import timeit
import random
#%matplotlib inline
#1,O（N）时的代码ns = [i for i in range(0,100,2)]
ts = [timeit.timeit('f1({})'.format([i for i in range(n)]), number=10000, globals=globals()) for n in ns]plt.plot(ns, ts, 'or')
avg_slope = statistics.mean((ts[i+1] - ts[i]) / (ns[i+1] - ns[i]) for i in range(len(ns)-1))
plt.plot(ns, [1.2avg_slopen for n in ns], '-b')
plt.plot(ns, [0.8avg_slopen for n in ns], '-g');
#2,O(logn)时的代码ns = [i for i in range(0,100,2)]
ts = [timeit.timeit('f2({})'.format(n), number=1000, globals=globals()) for n in ns]plt.plot(ns, ts, 'or')
avg_slope = 0.4statistics.mean((ts[i+1] - ts[i]) / (math.log(ns[i+1]+1,2) - math.log(ns[i]+1,2)) for i in range(len(ns)-1))
plt.plot(ns, [1.2abs(avg_slopemath.log(n+1,2)) for n in ns], '-b')
plt.plot(ns, [0.8abs(avg_slope*math.log(n+1,2)) for n in ns], '-g')#3,O(N)代码的列表形式
ns = [i for i in range(0,100,2)]
ts = [timeit.timeit('f3({})'.format([i for i in range(n)]), number=10000, globals=globals()) for n in ns]plt.plot(ns, ts, 'or')
avg_slope = statistics.mean((ts[i+1] - ts[i]) / (ns[i+1] - ns[i]) for i in range(len(ns)-1))
plt.plot(ns, [1.2avg_slopen for n in ns], '-b')
plt.plot(ns, [0.8avg_slopen for n in ns], '-g');
#4,O（e^n）的代码ns = [i for i in range(0,20,2)]
ts = [timeit.timeit('f4({})'.format(n), number=1, globals=globals()) for n in ns]plt.plot(ns, ts, 'or')
avg_slope = 0.1*statistics.mean((ts[i+1] -ts[i]) / (math.exp(ns[i+1]) - math.exp(ns[i])) for i in range(len(ns)-1))
plt.plot(ns, [0.8avg_slopemath.exp(n) for n in ns], '-b')
plt.plot(ns, [1.2avg_slopemath.exp(n) for n in ns], '-b')
#5，O(sqrt(n))的代码ns = [i for i in range(0,100,2)]
ts = [timeit.timeit('f5({})'.format([i for i in range(n)]), number=100, globals=globals()) for n in ns]plt.plot(ns, ts, 'or')
avg_slope = 5*statistics.mean((ts[i+1] - ts[i]) / (ns[i+1] - ns[i]) for i in range(len(ns)-1))plt.plot(ns, [1.2avg_slopemath.sqrt(n) for n in ns], '-b')
plt.plot(ns, [0.8avg_slopemath.sqrt(n) for n in ns], '-b')
