继续学习第二章算法分析的内容
1 算法时间复杂度
通过累加器的例子感受同一问题的不同算法之间的差异
import time
def plus(number):
ST = time.time()
count = 0
for i in range(1, number + 1):
count = count + i
ET = time.time()
cost_time = ET - ST
return count, cost_time
def plus_GS(number):
ST = time.time()
count = (number * (number + 1)) / 2
ET = time.time()
cost_time = ET - ST
return count, cost_time
ori_num = input("print the num please: ")
ori_num = int(ori_num)
ct_plus, tm_plus = plus(ori_num)
ct_GS, tm_GS = plus_GS(ori_num)
print("the plus result is ", ct_plus, "costs ", tm_plus, "s")
print("the plus result is ", ct_GS, "costs ", tm_GS, "s")
>>> the plus result is 50000005000000 costs 1.043466329574585 s
>>> the plus result is 50000005000000.0 costs 0.0 s
大O记法
上例所示两种算法中，plus函数赋值语句数是1+n(count=0 与 count=count+i)，可将其定义为函数T， 令T(n) = 1+n， 参数n常被称作问题规模。可解读为：“当问题规模为n时，解决问题所需时间是T(n)，即所需n+1步。如例中所示，处理前1000个整数的问题规模就要比处理前100000个整数的问题规模要小，消耗的时间就少。
随着问题规模的增长，T(n)函数的某一部分回避其余部分增长的更快，最后比较的其实是这一起决定性作用的部分——数量级函数描述的就是当n增长时，T(n)增长最快的部分。
数量级常备称作大O记法（O指order），记为O(f(n))。 f(n)为T(n)函数中起决定性作用的部分提供了简单的表示。对于T(n) = 1+n而言，随着n的变大，常数1对结果的影响越来越小，如果要给出T(n)的近似值，可以舍去1，直接说执行时间是O(n)。
a = 1
b = 2
c = 3
for i in range(n):
for j in range(n):
x = i*i
y = j*j
z = i*j
for k in range(n):
w = a*k +45
v = b*b
d = 33
该例中，赋值操作的数量是4项之和，T(n) = 3+3n2+2n+1 = 3n2+2n+4，易知n2起主导作用，所以这段代码的时间复杂度O(n) = n2
同时算法的性能不仅仅依赖于问题规模，还依赖于数据值，对于该种算法，要用最好情况，最坏情况，普通情况来描述性能
异序词检测示例
如果一个字符串知识重排了另一个字符串的字符，那这个字符串就是另一个的异序词，比如heart和earth。为了简化问题，假设要检查的两个字符串的长度相同，并且都是由26个英文字母的小写形式组成的。目标是编写一个布尔函数，它接受两个字符串，并能判断它们是否为异序词。
清点法与排序法
s1 = 'earth'
s2 = 'heart'
s1_list = list(s1)
s2_list = list(s2)
# 由于字符串不可改变，所以将其转换为列表
def way_1(list1, list2): # 清点法
pos1 = 0
matches = True
while pos1 < len(list1) and matches:
pos2 = 0
same_num = False
while pos2 < len(list2) and not same_num:
if list1[pos1] == list2[pos2]:
list2[pos2] = None
same_num = True
else:
pos2 = pos2 + 1
if same_num is True:
pos1 = pos1 + 1 # pos1在s2中出现过，继续循环
else:
matches = False # pos1在s2中没出现，跳出循环，不匹配
return matches
def way_2(list1, list2): # 排序法
list1.sort()
list2.sort()
pos = 0
matches = True
while pos < len(list1) and matches:
if list1[pos] == list2[pos]:
pos = pos + 1
else:
matches = False
return matches
result = way_1(s1_list, s2_list)
print(result)
>>> True
法一为清点法，即使用s1中的每个元素同s2中的元素进行比较，如果出现相同元素，则将s2中的该元素替换为None。O(n) = n2
法二为排序法，将s1和s2以相同方法排序后，按照对应位置进行比较。由于排序2方法本身具有时间复杂度，所以本方法的O(n)≠n，而是等同于排序算法的O(n)（常为n2或nlogn）
法三为计数法，由于字符串s1和s2都是由26个英文字母的小写形式组成，可以编写一个计数器分别记录两个字符串中字母出现的频率，如果最终两个字符串的计数器列表相同，则可认定s1、s2为异序字符串。（代码中未列出，不会写。。。）
