Python零基础速成班-第7讲 _时间复杂度

零基础速成班-第7讲-注释、算法基础、排序、查找、时间复杂度学习目标注释算法基础排序、查找、时间复杂度课后作业（4必做1挑战）
友情提示：将下文中代码拷贝到中直接执行即可，部分代码需要连续执行。
1、注释(note)介绍
1.注释就是对代码的解释和说明，其目的是让人们能够更加轻松地了解代码。
2.注释是编写程序时，写程序的人给一个语句、程序段、函数等的解释或提示，能提高程序代码的可读性。
3.在有处理逻辑的代码中，源程序有效注释量必须在20％以上。
代码注释分类 1.1 行注释：使用#号开头，在符号后那一行不会被编译（显示）
print("hello everyone!")#向大家打招呼
hello everyone!
1.2 块注释：使用三个单引号 ’ 或者双引号 " 开头和结尾，被块注释符号中间的部分不会被编译
'''这是使用三个单引号的多行注释这是第二行这是第三行'''
'\n这是使用三个单引号的多行注释\n这是第二行\n这是第三行\n'
"""这是使用三个双引号的多行注释"""
'\n这是使用三个双引号的多行注释\n'
1.3 注释的使用，文档注释在函数中的应用
在函数体的第一行使用一对三个单引号 ‘’’ 或者一对三个双引号 “”" 来定义文档字符串。你可以使用 doc（注意双下划线）调用函数中的文档字符串属性。
编写示例如下：
def addfun(num1,num2):""" 完成传入的两个数之和:param num1: 加数1:param num2: 加数2:return: 求两个数的和"""return num1 + num2print( addfun.__doc__ )
完成传入的两个数之和:param num1: 加数1:param num2: 加数2:return: 求两个数的和
1.4 文档注释常用编写风格
文档注释常用关键字：
①为函数传入参数
②为函数返回结果
③为函数可能会有的报错信息
1.4.1 这是现在流行的一种风格，reST风格，的御用格式，比较紧凑。
“”"
This is a reST style.
:param : this is a first param
:param : this is aparam
:: this is aof what is
: :an
“”"
1.4.2 风格
“”"
This is astyle docs.
:
- this is the first param
- this is aparam
:
This is aof what is \
:
-an
“”"
1.4.3. (Numpy风格)
“”"
Myof a kind
of very.
first :
the 1st param name first

文章插图
:
the 2nd param
third : {‘value’, ‘other’},
the 3rd param, by‘value’
a value in a
when a key error
when an other error
“”"
1.5 一些注释经验注释不是越多越好。对于一目了然的代码，不需要添加注释。对于复杂的操作，应该在操作开始前写上相应的注释。对于不是一目了然的代码，应该在代码之后添加注释。绝对不要描述代码。一般阅读代码的人都了解的语法，只是不知道代码要干什么。2、算法基础basis 2.1 我们以计算 π \pi π值为例子：可以使用下面公式π 4 = 1 ? 1 3 + 1 5 ? 1 7 + 1 9 . . . \frac{\pi}{4}= 1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}... 4π?=1?31?+51??71?+91?...
算法思路：
我们设计一个变量flag ，当它为0时，做+法并设置为1，当他为1时，做-法并设置为0，反复循环形成+ - + - + -…
通过i%2有余数，求出奇数，得出1/i
pi=0flag=0for i in range(1,1000000):if i%2: #有余数 Trueif flag == 0:pi += 1/iflag=1else:pi -= 1/iflag=0print(pi*4)
3.141590653589692
2.2 我们还可以通过预估模型：蒙特卡洛模拟计算 π \pi π值
算法思路：
想象一个圆形靶子，我们不停地向靶面射击，命名圆内的我们算是"击中" 也就是 x 2 + y 2 = 1 x^2+y^2=1 x2+y2=1 。假如我们不停地射击，直到我们把这个方形的靶子全部覆盖"打成筛子" 。圆的面积应该是 S c i r c l e = π r 2 S_{}={\pi}r^2 ?=πr2方形的面积应该是 S s q u a r e = a 2 S_{}=a^2 ?=a2也就是说 S c i r c l e / S s q u a r e = π r 2 / a 2 r = 1 , a = 2 {S_{}/S_{}={\pi}r^2/a^2}_{r=1,a=2} ?/?=πr2/a2r=1,a=2? S c i r c l e / S s q u a r e = π / 4 S_{}/S_{}={\pi}/4 ?/?=π/4 π = 4 ? ( S c i r c l e / S s q u a r e ) {\pi}= 4 * (S_{}/S_{}) π=4?(?/?)
在程序中trys 变量为我们尝试的次数，次数越多，越精确
hits 变量为命中数量
x = -1+2 * ()表明x轴在-1到1之间；y = -1+2 * ()表明y轴在-1到1之间
x ** 2 + y ** 2 1 ，求x的平方根y，0 ②假设 guess是(low+high)/2 ，如果guess的平方非常接近x，那么y=guess
③若 g u e s s 2 guess^2④若 g u e s s 2 guess^2 >x，high设定为guess，然后重复第二步
在程序中， trys为迭代次数，次数越多，越精准。

trys =10000x =int(input("请输入需要求平方根的数字>>>\n"))low,high=0,xfor i in range(trys):guess = (low+high)/2if guess**2 < x:low = guesselse:high = guessprint(guess)

请输入需要求平方根的数字>>>52.23606797749979
3、排序、查找、时间复杂度 3.1 我们简单介绍冒泡、插入、归并三种排序Sort 多次遍历数组，每次遍历相邻元素，如果没有按照顺序排列，则互换他们。Sort 重复地将新元素插入到一个排好序的子线性表中，直到整个线性表排好序。Merge Sort 将数组分为两半，对每部分递归地应用归并排序，在两部分都排好序后，对它们进行归并。1.冒泡排序 Sort示例：因为是双循环嵌套，所以时间复杂度是O( n 2 n^2 n2)
①
②
③
④
⑤

import random#冒泡排序def bubbleSort(list:"需要排序的数组")->"输出排好序的数组":for i in range(1,len(list)):for j in range(0,len(list)-i):if list[j] > list[j+1]:list[j],list[j+1]=list[j+1],list[j]return listbubbleSort(random.sample(range(0,100),8))

[32, 40, 42, 69, 80, 86, 91, 96]
2.插入排序 Sort示例：将不断与之前的元素进行比较，如小于前一个元素则互换位置，时间复杂度介于 O(n) and O( n 2 n^2 n2)之间
① =9
② >> =5
③ >> =4
④ >> =8
⑤ >> =1

def insertionSort(list:list)->"sortedlist":for i in range(1,len(list)):current =list[i]k= i-1 #从左边第一个开始循环while k>=0 and list[k] > current: #左边大于current值时 ， 向右移一位，直到不大于currentlist[k+1] = list[k]k-=1list[k+1] = current#把current相应的位置赋值currentreturn listinsertionSort([3,7,10,5,8,12,4,6])

[3, 4, 5, 6, 7, 8, 10, 12]
3.归并排序Merge Sort示例：不断向下拆分后比较，最后合并，时间复杂度O(n log n)
29548167295481672954816729548167294518672459167812456789
merge sort 时间复杂度

文章插图
64log n3232O(n)1616O(n)88O(n)
【Python零基础速成班-第7讲】

import randomdef mergeSort(list):n = len(list)#获取长度if n <=1:#如果列表长度1，直接返回return listmid = n//2 #取中间值，把数组拆分left = mergeSort(list[:mid])#取左半部分right = mergeSort(list[mid:])#取右半部分leftp = 0 #左半指针从0开始rightp = 0 #右半指针从0开始result =[]#定义空数组存储每次归并好的列表while leftp < len(left) and rightp < len(right):#当左右指针分别小于长度时if left[leftp] <= right[rightp]:result.append(left[leftp])leftp +=1else:result.append(right[rightp])rightp +=1result += left[leftp:]#考虑数组为奇数，把最后元素添加进来result += right[rightp:]return resultmergeSort(random.sample(range(0,100),20))

[0, 4, 8, 14, 16, 24, 35, 38, 49, 56, 62, 68, 75, 77, 78, 81, 87, 88, 89, 97]
3.2 系统排序采用归并排序和插入排序相结合例如对128位长度的数组进行排序，前期均采用归并排序，当长度到达16时，则采用插入排序
128Merge6464Merge3232Merge1616Insertion
3.3 查找及时间复杂度 O(1)时间复杂度为1的情况
def square(x):return x*xsquare(100)
10000
查找数组中的最大值，需要遍历数组，时间复杂度为O(n)

def findmax(list):max = list[0]for i in range(1,len(list)):if list[i] > max:max = list[i]return maxfindmax([1,4,0,8,4,9,3])

9
查找数组中重复的数字，需要双循环嵌套，时间复杂度为 O( n 2 n^2 n2)

def findduplicate(list):dupli=[]for i in range(len(list)):for j in range(i+1,len(list)):if list[i] == list[j]:dupli.append(list[i])breakreturn duplifindduplicate([1,3,5,7,9,2,3,6,8,0,7])

[3, 7]
二分法查找，又称折半检索，时间复杂度为 O( l o g 2 nlog2?n)
二分法查找思路：
首先将给定值key与字典中间位置上元素的关键码(key)比较，如果相等，则检索成功。否则，若key小，则在字典前半部分中继续进行二分法检索。若key大，则在字典后半部分中继续进行二分法检索。这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败，失败返回-1 。二分法检索是一种效率较高的检索方法。
进阶提示：
二分法查找需要先对数组进行排序。

def binarySearch(list,value):low=0high=len(list)while(low <= high):mid = (low + high) // 2if (list[mid]==value):return midelif (value > list[mid]):low = mid + 1else:high = mid - 1return -1print(binarySearch([1,2,3,4,5,6,7],5))

4
4、课后作业，答案在下一讲 1、完成一个包含文档注释的函数(函数功能为两个数相除)，注释风格为主流reST Style，包含param ，，raise，by，等关键字。
您的代码：
2、请统计"Hello, have you tried ouryet?" 中每个元音字母各出现了多少次？
您的代码：
3、根据公式 n ? ( n ? 1 ) n * (n-1) n?(n?1)，生成一个100个数组的列表，例如：
[0,2,6,12,20,30,42…]
您的代码：
4、制作一个 Uint ，通过dict快速实现①选择转换类型②参数输入③结果输出 1英寸inch=25.4毫米 1英尺feet=30.5厘米 1英里mile=1.61公里 1码yard=0.914米 1浪wave=204米
您的代码：
*(挑战) 5、编程实践项目大数据下：比较两种排序的效率情况随机从0~中，取1000个整数，填入数组，分别进行冒泡排序和归并排序(两种方法可参考上文书写)，比较它们的效率(执行耗时) 。再取10000个整数，再试试执行效率。将程序写进class，分别通过class+函数名调用方法。
tips:函数运行时间可以使用下列函数
def timer(f):def _f(*args):t0=time.time()f(*args)return time.time()-t0return _f
您的代码：
5、上一讲零基础速成班-第6讲-异常处理，try& ， raise，，输入模块课后作业及答案 1、计算银行带来的回报，假设你存银行一笔钱是10000 ，年利率是5% ，则计算20年后，变成了多少钱？打印每一年的变化

rate=5.00balance =10000.00bal_list = []for year in range(1,21):balance += balance*rate/100print("%4d .2f" %(year,balance))bal_list.append(balance)

110500.00211025.00311576.25412155.06512762.82613400.96714071.00814774.55915513.281016288.951117103.391217958.561318856.491419799.321520789.281621828.751722920.181824066.191925269.502026532.98

2、(扩展)在第一题的基础上通过绘制一张x(金额)/y(年)的曲线图(收益表)

import matplotlib.pyplot as pltfig,ax =plt.subplots()ax.plot([i for i in range(1,21)],bal_list)ax.set(xlabel="n th year",ylabel="Money",title="How much I got")ax.grid()plt.show()

3、安装并使用输入模块，完成age输入验证(数字0~110 ，最多输入2次)，性别输入(男、女，限时10秒钟内)，输出年龄，性别

import pyinputplus as piage = pi.inputInt("Please enter age：",min=0,max=110,limit=2)gender = pi.inputChoice(['Male','Female'],timeout=10)print("age={} gender={}".format(age,gender))

Please enter age：20Please select one of: Male, FemaleMaleage=20 gender=Male
4、制作一个菜单，其中包括小吃、饮料、主食等分类，每个分类下包含多种食物，左边是名字右边是价格，请尽量美观的把菜单打印出来。

menu_dict={"1.主食":{"1.面条":6,"2.米饭":2,"3.抄手":8,"4.馒头":1},"2.饮料":{"1.芬达":3,"2.无糖可乐":4,"3.面汤":1,"4.酸梅汁":2},"3.小吃":{"1.甩饼":4,"2.糍粑":7,"3.小油条":8,"4.金银馒头":6},}

menu_dict={"1.主食":{"1.面条":6,"2.米饭":2,"3.抄手":8,"4.馒头":1},"2.饮料":{"1.芬达":3,"2.无糖可乐":4,"3.面汤":1,"4.酸梅汁":2},"3.小吃":{"1.甩饼":4,"2.糍粑":7,"3.小油条":8,"4.金银馒头":6},}for k,v in menu_dict.items():print("{}".center(20,"-").format(k))for k1,v1 in v.items():print("{}".ljust(6," ").format(k1),"价格:{}".rjust(15-len(k1.encode("GBK"))," ").format(v1))

---------1.主食---------1.面条价格:62.米饭价格:23.抄手价格:84.馒头价格:1---------2.饮料---------1.芬达价格:32.无糖可乐价格:43.面汤价格:14.酸梅汁价格:2---------3.小吃---------1.甩饼价格:42.糍粑价格:73.小油条价格:84.金银馒头价格:6

*(挑战)5、编程实践项目判卷问题：设计一个自动判卷程序我们帮助数学老师判卷子，本次数学题一共10题，每题10分。已经知道正确答案分别是""，要求输入学生结果能找出错误并指出最终分数。

correct_answers = "adbdcacbda"correct_list = list(correct_answers)done =Falsewhile not done:user_answers = input("Enter your exam answers!\n>>>")if len(user_answers)== len(correct_answers):user_list =list(user_answers)done = Trueelse:print("length is not equal")judge_list= list(map(lambda user,corr:"Y" if user ==corr else "X",user_list,correct_list))judge_dict={i: judge_list.count(i)for i in set(judge_list)}total= judge_dict["Y"]*10print("user_answers={}\njudgement={}\nfinallytotal={}".format(judge_list,judge_dict,total))

Enter your exam answers!>>>abbdaccddauser_answers=['Y', 'X', 'Y', 'Y', 'X', 'X', 'Y', 'X', 'Y', 'Y']judgement={'X': 4, 'Y': 6}finallytotal=60