2.1引言

求解问题的算法往往并不唯一，为了量化不同算法的效率，需要通过渐近分析方法来计算算法的时间复杂度。前一章的例子可知，通过巧妙得设计可以缩短寻找到局部高点得时间，算法的时间复杂度可以从O(n)提高到O(logn).
渐进分析简化算法时间复杂度的计算，在渐进分析下，并不需要精确计算算法的执行时间，而只需要计算时间函数在输入规模n增长时增长趋势。也就是说，算法执行的时间函数中，n的低次项和高次项前的常数项均可略去。n在变大时，n的高次项决定了函数的增长趋势。

2.2 计算模式

代码2.1

def compare_num(i,j):
    k = 3
    if i>j:
        return i
    else:
        return k

2.3 算法的渐进分析

2.4 Python 计算模型

学习的算法设计和分析所有的算法描述均采用 Python

2.4.1 控制流语句

条件语句

代码2.2 条件语句的示例

def num_verify(num):
    if num<0:
        num = 0
        print('非负数转换为 0！')
    elif num == 0:
        print('零)
    elif num ==1:
        print('等于1')
    else:
        print('大于1')
    return num

循环语句

代码2.3 循环语句示例

def sum_nums(low,high):
    if high<low:
        print("error")
        return 
    sumnum = 0
    for i in range(low,high+1)
        sumnum += i
    return sumnum

2.4.2 数据结构

x**2 for x in range(10)

代码 2.5 列表推导生成随机数组

import random
def generate_rand_array(num=10,maxnum=1000):
    arrary = [random.randint(1,maxnum) for in in range(num)]
    random.shuffle(array) # 随机打乱array 中的元素
    random.shuffle(array)
    return array

在序列中循环时，索引位置和对应值可以使用enumerate()函数同时得到：
for i,v in enumerate(['tic','tac','toe']):

2.5 算法分析实例

2.5.1 求最大值

2.5.2 二分搜索

代码 2.8 二分搜索

def binary_search(A,K):
    first = 0
    last = len(A)-1
    found = False
    while first <= last:
        midpoint = (first + last)//2
        if k== A[midpoint]:
            found = True
        else:
            if k<A[midpoint]:
                last = midpoint-1
            else:
                first = midpoit+1
    return found 

2.5.3 子集求和问题

代码2.9 求子集和

def subset_sum(lst,target):
    for i in range(2**len(lst)):
        pick  = list(mark(lst,bin(i)[2:]))  
        if sum(pick) == target:
            return pick
def mark(lst,m):  # 产生由m(二进制数)决定的 lit的子集
    m = m.zfill(len(lst))  # 按照lst 的位数扩展m 和lst长度一致的数
    return map(lambda x:x[0],filter(lambda x: x[1] != '0',zip(lst,m))) #通过zip 组成一个元组数据（lst中的数，m中的数），过滤掉每个元组数组中m为0的数，剩下的取lst中的数