第二章——算法分析

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 如何记录代码的运行时间

如何写好的代码：

1. 可读性
2. 考虑空间复杂度
3. 考虑时间复杂度——可调用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