0. 目标
- To understand why algorithm analysis is important.
- To be able to use “Big-O” to describe execution time.
- To understand the “Big-O” execution time of common operations on Python lists and dictionaries.
- To understand how the implementation of Python data impacts algorithm analysis.
- To understand how to benchmark simple Python programs.
1. 课程笔记
1.1 如何记录代码的运行时间
如何写好的代码：
- 可读性
- 考虑空间复杂度
- 考虑时间复杂度——可调用python的内置函数记录程序运行的时间
import time
def sumOfN3(n):
start = time.time()
theSum = (n * (n + 1)) / 2
end = time.time()
return theSum,end-start
for i in range(5):
print("Sum is %d required %10.7f seconds"%sumOfN3(100000))
1.2 big-O （big order）
O(n^2)和O(n)的对比
### bad algorithm-find the smallest number O(n^2) ####
import time
from random import randrange
def find_min(list):
n = len(list)
for i in range(n):
for j in range(n):
if list[j] < list[i]:
continue
print('the smallest number is', list[i])
def mainA():
list = [5, 4, 3, 2, 1, 0]
find_min(list)
def mainB():
for listsize in range(1000, 10001, 1000):
list = [randrange(100000000) for x in range(listsize)]
start = time.time()
find_min(list)
end= time.time()
print ("size: %d time: %f " % (listsize, end-start))
mainB()
#### good algorithm O(n) ######
def Find_Min(list):
flag = list[0]
for i in list: ##python很高级，可以直接循环list！
if i < flag:
flag = i
return flag
