Python零基础速成班-第7讲-Python注释、算法基础、排序、查找、时间复杂度

Python零基础速成班-第7讲-Python注释、算法基础、排序、查找、时间复杂度

学习目标

1. 注释
2. 算法基础
3. 排序、查找、时间复杂度
4. 课后作业（4必做1挑战）

友情提示：将下文中代码拷贝到JupyterNotebook中直接执行即可，部分代码需要连续执行。

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 文档注释常用编写风格

文档注释常用关键字：

①Parameters为函数传入参数
②Returns为函数返回结果
③Raises为函数可能会有的报错信息

1.4.1 这是现在流行的一种风格，reST风格，Sphinx的御用格式，比较紧凑。

“”"
This is a reST style.

:param param1: this is a first param
:param param2: this is a second param
:returns: this is a description of what is returned
:raises keyError: raises an exception
“”"

---

1.4.2 Google风格

“”"
This is a groups style docs.

Parameters:
param1 - this is the first param
param2 - this is a second param

Returns:
This is a description of what is returned\

Raises:
KeyError - raises an exception
“”"

---

1.4.3.Numpydoc (Numpy风格)

“”"
My numpydoc description of a kind
of very exhautive numpydoc format docstring.

Parameters

first : array_like
the 1st param name first
second :
the 2nd param
third : {‘value’, ‘other’}, optional
the 3rd param, by default ‘value’

Returns

string
a value in a string

Raises

KeyError
when a key error
OtherError
when an other error
“”"

1.5 一些注释经验

1. 注释不是越多越好。对于一目了然的代码，不需要添加注释。
2. 对于复杂的操作，应该在操作开始前写上相应的注释。
3. 对于不是一目了然的代码，应该在代码之后添加注释。
4. 绝对不要描述代码。一般阅读代码的人都了解Python的语法，只是不知道代码要干什么。

2、算法基础 Algorithm basis

2.1 我们以计算$\pi$值为例子：可以使用下面公式

$\frac{\pi }{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}...$

算法思路：

我们设计一个变量flag，当它为0时，做+法并设置为1，当他为1时，做-法并设置为0，反复循环形成+ - + - + -…

通过i%2有余数，求出奇数，得出1/i

pi=0
flag=0
for i in range(1,1000000):if i%2: #有余数 Trueif flag == 0:pi += 1/iflag=1else:pi -= 1/iflag=0
print(pi*4)    

3.141590653589692

2.2 我们还可以通过预估模型：蒙特卡洛模拟计算$\pi$值

算法思路：

1. 想象一个圆形靶子，我们不停地向靶面射击，命名圆内的我们算是"击中" 也就是$x^2+y^2=1$。假如我们不停地射击，直到我们把这个方形的靶子全部覆盖"打成筛子"。
2. 圆的面积应该是$S_{circle}=\pi r^2$
3. 方形的面积应该是$S_{square}=a^2$
4. 也就是说${S_{circle}/S_{square}=\pi r^2/a^2}_{r=1,a=2}$
5. $S_{circle}/S_{square}=\pi /4$
6. $\pi =4\ast (S_{circle}/S_{square})$
   

在程序中trys 变量为我们尝试的次数，次数越多，越精确
hits 变量为命中数量
x = -1+2 * random()表明x轴在-1到1之间；y = -1+2 * random()表明y轴在-1到1之间
x ** 2 + y ** 2 <=1 表明击中⚪内

from random import random
trys =800000
hits =0
for i in range(trys):x = -1+2*random()y = -1+2*random()if x**2 + y**2 <=1:hits+=1
print("Estimate for pi={}".format(4*hits/trys))

Estimate for pi=3.140415

2.3 举例:从 0~100 中猜数字，有哪些算法，时间复杂度是多少？

1. 我们可以遍历0-100，时间复杂度$O(n)$
2. 我们可以不断取中数，不断逼近答案，时间复杂度$Olo{g}_2^{100}$
3. 哪种时间复杂度更低，不断取中数最多几次能取中？
4. 答案是7次，不断取中效率最高，时间复杂度最低。

2.4 完成一个计算机求平方根的算法：

提示：

①x>1，求x的平方根y，0<y<x，low为0，high为x
②假设 guess是(low+high)/2，如果guess的平方非常接近x，那么y=guess
③若$gues{s}^2$<x，low设定为guess，然后重复第二步
④若$gues{s}^2$>x，high设定为guess，然后重复第二步
在程序中，trys为迭代次数，次数越多，越精准。

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

请输入需要求平方根的数字>>>
5
2.23606797749979

3、排序、查找、时间复杂度

3.1 我们简单介绍冒泡、插入、归并三种排序

1. Bubble Sort 多次遍历数组，每次遍历相邻元素，如果没有按照顺序排列，则互换他们。
2. Insertion Sort 重复地将新元素插入到一个排好序的子线性表中，直到整个线性表排好序。
3. Merge Sort 将数组分为两半，对每部分递归地应用归并排序，在两部分都排好序后，对它们进行归并。

1.冒泡排序Bubble Sort示例：因为是双循环嵌套，所以时间复杂度是O($n^2$)

①295481 259481 254981 254891 254819

②254819 245819 245189

③245189 241589

④241589 214589

⑤124589

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 list
bubbleSort(random.sample(range(0,100),8))

[32, 40, 42, 69, 80, 86, 91, 96]

2.插入排序Insertion Sort示例：将Current不断与之前的元素进行比较，如小于前一个元素则互换位置，时间复杂度介于 O(n) and O($n^2$)之间

①295481 Current=9

②295481 >>259481 Current=5

③259481 >>245981 Current=4

④245981 >>245891 Current=8

⑤245891 >>124589 Current=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 list
insertionSort([3,7,10,5,8,12,4,6])

[3, 4, 5, 6, 7, 8, 10, 12]

3.归并排序Merge Sort示例：不断向下拆分后比较，最后合并，时间复杂度O(n log n)

---

        295481672954         816729     54     81    67
2   9  5  4  8   1  6   729     45     18    672459          167812456789    

---

merge sort 时间复杂度

          64         log n32  32         O(n)16      16       O(n)8          8      O(n)

import random
def 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 result
mergeSort(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 Python系统排序采用归并排序MergeSort和插入排序InsertionSort相结合

例如对128位长度的数组进行排序，前期均采用归并排序，当长度到达16时，则采用插入排序

         128          Merge64  64        Merge32      32      Merge16         16    Insertion

3.3 查找及时间复杂度

O(1)时间复杂度为1的情况

def square(x):return x*x
square(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 max
findmax([1,4,0,8,4,9,3])

9

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

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 dupli
findduplicate([1,3,5,7,9,2,3,6,8,0,7])

[3, 7]

二分法查找Binary Search，又称折半检索，时间复杂度为 O($lo{g}_{2}n$)

二分法查找思路：

1. 首先将给定值key与字典中间位置上元素的关键码(key)比较，如果相等，则检索成功。
2. 否则，若key小，则在字典前半部分中继续进行二分法检索。
3. 若key大，则在字典后半部分中继续进行二分法检索。
4. 这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败，失败返回-1。
5. 二分法检索是一种效率较高的检索方法。

进阶提示：
二分法查找需要先对数组进行排序。

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 -1
print(binarySearch([1,2,3,4,5,6,7],5))

4

4、课后作业，答案在下一讲

1、完成一个包含文档注释的函数(函数功能为两个数相除)，注释风格为主流reST Style，包含param，return，raise，design by，createdate等关键字。

您的代码：

2、请统计"Hello, have you tried our turorial section yet?" 中每个元音字母各出现了多少次？

您的代码：

3、根据公式$n\ast (n-1)$，生成一个100个数组的列表，例如：

[0,2,6,12,20,30,42…]

您的代码：

4、制作一个Length Uint Converter，通过dict快速实现①选择转换类型②参数输入③结果输出

1英寸inch=25.4毫米

1英尺feet=30.5厘米

1英里mile=1.61公里

1码yard=0.914米

1浪wave=204米

您的代码：

*(挑战) 5、编程实践项目

大数据下：比较两种排序的效率情况

随机从0~100000中，取1000个整数，填入数组，分别进行冒泡排序和归并排序(两种方法可参考上文书写)，比较它们的效率(执行耗时)。再取10000个整数，再试试执行效率。将程序写进class，分别通过class+函数名调用方法。

tips:函数运行时间可以使用下列函数

def timer(f):def _f(*args):t0=time.time()f(*args)return time.time()-t0return _f

您的代码：

5、上一讲Python零基础速成班-第6讲-Python异常处理Exception，try&except，raise，assert，输入模块pyinputplus 课后作业及答案

1、计算银行带来的回报，假设你存银行一笔钱是10000，年利率是5%，则计算20年后，变成了多少钱？打印每一年的变化

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

   1   10500.002   11025.003   11576.254   12155.065   12762.826   13400.967   14071.008   14774.559   15513.2810   16288.9511   17103.3912   17958.5613   18856.4914   19799.3215   20789.2816   21828.7517   22920.1818   24066.1919   25269.5020   26532.98

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

import matplotlib.pyplot as plt
fig,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、安装并使用输入模块pyinputplus，完成age输入验证(数字0~110，最多输入2次)，性别输入(男、女，限时10秒钟内)，输出年龄，性别

import pyinputplus as pi
age = 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：20
Please select one of: Male, Female
Male
age=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.面条         价格: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

*(挑战)5、编程实践项目

判卷问题：设计一个自动判卷程序

我们帮助数学老师判卷子，本次数学题一共10题，每题10分。已经知道正确答案分别是"adbdcacbda"，要求输入学生结果能找出错误并指出最终分数。

correct_answers = "adbdcacbda"
correct_list = list(correct_answers)
done =False
while 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"]*10
print("user_answers={}\njudgement={}\nfinallytotal={}".format(judge_list,judge_dict,total))

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