数据结构与算法python-01
在认识算法之前,先测试以下例子:
给定a,b,c 假定 a+b+c=1000,并且a^2 + b^2 = c^2,请求出a、b、c所有可能的组合?
方案1:
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**2 + b**2 == c**2 and a+b+c == 1000:
print("a, b, c: %d, %d, %d" % (a, b, c))
end_time = time.time()
print("运行时间为: %f" % (end_time - start_time))
print("完成!")
运行结果为:
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
运行时间为: 1066.117884
完成!
方案二:
# 注意是两重循环
for a in range(0, 1001):
for b in range(0, 1001-a):
c = 1000 - a - b
if a**2 + b**2 == c**2:
print("a, b, c: %d, %d, %d" % (a, b, c))
end_time = time.time()
print("运行时间为: %f" % (end_time - start_time))
print("complete!")
运行结果为:
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
运行时间为:0.632128
由以上两种方案可知,不同算法带来时间复杂度的大幅提升,第一种算法复杂度为O(n**3),第一种为O(n**2)
算法是什么?
时间复杂度与“大O记法”
最坏时间复杂度
常见的时间复杂度:
时间大小关系:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)