1.时间复杂度_代码示例
# 如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?
# O(n^3) vs O(n^2) 效率
# O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
import time
start_time = time.time()
for a in range(0, 1001):
for b in range(0, 1001):
for c in range(0, 1001):
if a+b+c==1000 and a**2+b**2==c**2:
print("a={0}, b={1}, c={2}".format(a, b, c))
end_time = time.time()
print("第一种方法用时：",end_time-start_time) # 输出： 109.12208700180054
start_time = time.time()
for b in range(0, 1001):
for c in range(0, 1001):
if (1000-b-c)**2+b**2==c**2 and 1000-b-c>=0:
print("a={0}, b={1}, c={2}".format((1000-b-c), b, c))
end_time = time.time()
print("第二种方法用时：", end_time-start_time) # 输出： 1.1500554084777832
?
2.数据结构 _代码示例
# 抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。
from timeit import Timer
def test1():
li = []
for x in range(1000):
li = li + [x]
# print(li)
def test2():
li = []
for x in range(1000):
li.append(x)
def test3():
li = [i for i in range(1000)]
def test4():
li = list(range(1000))
t1 = Timer("test1()", "from __main__ import test1")
print("concat", t1.timeit(number=10000), "seconds") # 10.48 seconds
t2 = Timer("test2()", "from __main__ import test2") # 0.5406 seconds
print("append", t2.timeit(number=10000), "seconds")
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension", t3.timeit(number=10000), "seconds") # 0.2888 seconds
t4 = Timer("test4()", "from __main__ import test4")
print("list_range", t4.timeit(number=10000), "seconds") # 0.1246 seconds
?