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中的数
网友评论