0%

时间复杂度使用大 O 标记法,这个大家应该都清楚,下面是常见的增长量级:

增长量级 名称
$O(1)$ 常量级
$O(log_bn)$ 对数级
$O(n)$ 线性级
$O(nlog_bn)$ $nlogn$
$O(n^2)$ 平方级
$O(n^3)$ 立方级
$O(c^n)$ 指数级

Python 中基本操作分析

常量时间

算术操作大部分都是常量时间,除法 > 乘法 > 加法和减法;

索引操作(下标访问)和 len 函数也是常量时间;

假如一个字符串只包含一个字符,所有的操作都是常量的;

在列表结尾添加和删除一个元素是常量的;

大部分字典操作都是常量的,但是 update 方法的运行时间和传入的字典大小成正比,keys、values 和 items 都是常量时间,因为它们返回的是迭代器,但是如果循环遍历这个迭代器,则循环是线性的。

线性时间

使用 for 循环遍历一个序列或字典是线性的;

字符串和元组的大部分操作都是线性的;

min 和 max 函数也是线性的;

切片操作的运行时间与输出的长度成正比,而与输入的长度无关;

内置函数 sum 也是线性的,但速度更快;

字符串拼接是线性的,运行时间与操作数的长度的总和有关,所有的字符串方法都是线性的。

其他时间

大多数列表方法是线性的,但是除非空间不足时复制到另一个更大的空间,排序是 $nlogn$;

如果循环体的增长量级是 $O(n^a)$ 则整个循环是 $O(n^{a+1})$,如果不论 $n$ 是多少,循环只最多运行 $k$ 次,则及时对很大的 $k$ 来说,整个循环的增长量级还是 $O(n^a)$。

搜索算法的分析

遍历操作是线性的,二分查找是对数级的,散列表是常量时间。

条件表达式

我们经常会使用条件语句来从两个值中选择一个,例如:

1
2
3
4
if x > 0:
y = math.log(x)
else:
y = float('nan')

这几行代码会检查 x 是否为正数。如果为正数,则计算 math.log;如果为负数,math.log 会抛出 ValueError 异常。为了避免程序停止,则直接生成了“NAN”,一个特殊的浮点数,代表“不是数”。

实际上这几行代码可以使用更加简洁的方式:

1
y = math.log(x) if x > 0 else float('nan')

这条语句是不是可以非常简洁?

有时候,递归表达式也可以用条件表达式重写,以斐波那契数列为例:

1
2
3
4
5
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)

可以将它重写为:

1
2
def factorial(n):
return 1 if n ==0 else n * factorial(n-1)

一般来说,如果条件语句的两个分支都只包含简单的判断或对同一变量进行赋值的表达式,那么就可以转化为条件表达式。

列表解析式和生成器

列表解析式可以快速生成一个列表,例如假如需要对列表中的元素做某些操作,生成一个新的列表,可能我们会这样写:

1
2
3
4
5
def capitalize_all(t):
res = []
for s in t:
res.append(s.capitalize())
return res

而使用列表解析式操作是这样子的:

1
2
def capitalize_all(t):
return [s.capitalize() for s in t]

生成器表达式与列表解析式有一点不同,那就是生成器表达式使用圆括号:

1
2
3
>>> g = (x**2 for x in range(5))
>>> g
<generator object <genexpr> at 0x000001B46BB8FE08>

这个结果是一个生成器对象,它不会把所有的结果一次性计算出来,而是请求一个获取一个,它使用 next 函数获取下一个值:

1
2
3
4
>>> next(g)
0
>>> next(g)
1

生成器表达式经常和 sum、max 和 min 之类的函数配合使用:

1
2
>>> sum(x**2 for x in range(5))
30

any 和 all

Python 中有两个内置函数 any 和 all。any 接收一个由布尔值组成的序列,并当其中任何值是 True 时返回 True。它可以用于列表:

1
2
>>> any([True, False])
True

但更常见于生成器表达式:

1
2
>>> any(letter == 't' for letter in 'monty')
True

all 函数则是在序列中所有元素都是 True 时返回 True。

集合和 collections 模块

集合 set 是 Python 中的另一种数据类型,集合中的元素是没有重复的。

例如,判断一个字符集是不是在另一个字符集中全部出现:

1
2
def uses_only(word, available):
return set(word) <= set(available)

操作符 <= 检查一个集合是否是另一个集合的子集。

collections 模块包含了一些常用的方法,例如计数器 Counter、defaultdict、命名元组等。

列表

列表与字符串类似,也是一个序列,所不同的地方在于,字符串中的元素是字符,列表中的元素可以是任意类型,并且可以嵌套,例如,字典、元组、列表、字符串、数值类型都可以作为列表的元素。

创建列表

最简单的方式就是使用 [] 创建列表:

1
2
3
4
5
6
>>> l = []
>>> l
[]
>>> l = ['str', 2.0, 5, [10, 20]]
>>> l
['str', 2.0, 5, [10, 20]]

遍历列表

遍历一个列表元素最常见的方法,就是使用 for 循环:

1
2
3
4
5
6
>>> for i in l:
... print(i)
str
2.0
5
[10, 20]

修改列表

列表是可变的,因此可以任意修改列表中的元素,修改的方法可以直接通过下标修改:

1
2
3
>>> l[1] = 10
>>> l
['str', 10, 5, [10, 20]]

还可以通过列表切片的方式修改:

1
2
3
>>> l[1:3] = 1, 2
>>> l
['str', 1, 2, [10, 20]]

需要注意的是,切片操作的第二个下标是不包含在内的。

添加列表元素

使用 append 方法在列表尾部添加元素:

1
2
3
>>> l.append('new')
>>> l
['str', 1, 2, [10, 20], 'new']

使用 extend 添加整个列表,extend 方法接收一个列表作为参数,并将其所有元素添加到原列表后面:

1
2
3
4
>>> l1 = [4, 5]
>>> l.extend(l1)
>>> l
['str', 1, 2, [10, 20], 'new', 4, 5]

同样可以通过切片操作添加列表元素:

1
2
3
>>> l[len(l):] = 'new2'
>>> l
['str', 1, 2, [10, 20], 'new', 4, 5, 'n', 'e', 'w', '2']

len(l) 计算列表的长度,同时没有指定切片操作第二个下标,表示将新元素全部添加到列表之后。

注意,使用切片操作添加或修改列表元素,如果元素长度超出了切片指定的下标长度,则会按照元素长度修改列表:

1
2
3
4
5
6
7
8
>>> l
['l', 'i', 's', 't']
>>> l[4:5] = 1, 2
>>> l
['l', 'i', 's', 't', 1, 2]
>>> l[0:1] = 2, 4, 6
>>> l
[2, 4, 6, 'i', 's', 't', 1, 2]

删除列表元素

如果知道元素的下标,可以使用 pop 方法删除:

1
2
3
>>> l.pop()
'2'
>>> l.pop(0)

不指定 pop 方法的参数的话,表示删除最后一个元素,同时 pop 可以返回删除的值。

del 方法同样可以删除元素,但是没有返回值:

1
2
3
>>> del l[2]
>>> l
[1, 2, 'new', 4, 5, 'n', 'e', 'w']

如果不知道要删除元素的下标,可以使用 remove 删除该元素:

1
2
3
4
5
>>> l
[2, 'new', 4, 5, 'n', 'e', 'w', 2]
>>> l.remove(2)
>>> l
['new', 4, 5, 'n', 'e', 'w', 2]

可以看到,这个列表中有两个 2,但是 remove 方法只删除了第一个 2,表示 remove 方法只会删除列表中第一个符合的元素就立即返回。

如果要删除多个元素,可以使用 del 和切片操作:

1
2
3
>>> del l[4:]
>>> l
['new', 4, 5, 'n']

字符串和列表的相互转换

使用 list 函数将字符串转换为列表:

1
2
3
4
>>> s = 'list'
>>> l = list(s)
>>> l
['l', 'i', 's', 't']

list 函数会将字符串中的每一个字符作为一个列表元素。

如果字符串可以按照分隔符分割,可以使用字符串方法 split:

1
2
3
>>> s = 'this is a str'
>>> s.split()
['this', 'is', 'a', 'str']

split 方法默认使用空格作为分隔符,当然也可采用其他分隔符,如 ‘-‘、’,’ 等,直接作为参数传入 split 方法即可。

使用 join 方法连接字符串列表:

1
2
3
4
5
6
>>> t
['this', 'is', 'a', 'str']
>>> ''.join(t) # 不使用分隔符
'thisisastr'
>>> ' '.join(t) # 空格作为分隔符
'this is a str'

列表操作注意事项

  1. 修改列表的方法可以通过 append、extend、切片操作完成;
  2. 删除列表元素可以通过 pop 方法、del 函数、remove 方法完成;
  3. 切片操作可以对原列表修改,也可复制一个列表;
  4. ‘+’ 操作符会创建一个新的列表;
  5. 大部分列表方法没有返回值,这一点与字符串方法不同;
  6. 列表的很多操作可以通过多种方式完成,应该选定一个操作并坚持不变。

字典

字典中的元素是一个键值对。作为键必须使用不可变类型,如字符串、元组等,而作为值则可以使用任意类型。这是因为,字典是通过散列表的形式实现的,因此字典的键必须是可散列的,可变类型是不可散列的。

在 3.7 版本之前,Python 字典中的元素是无序的,在 3.7 版本中解决了这个问题,元素的顺序按照添加的顺序确定。

字典的操作

创建字典

可以直接通过 {} 操作符创建字典:

1
2
3
4
5
6
>>> dic = dict()
>>> dic
{}
>>> dic1 = {}
>>> dic1
{}

同样可以使用 in 操作符遍历字典,不同的是,无论字典多大,in 操作符所花费的时间都差不多,这是采用散列表实现的原因。字典的修改直接对相应的键赋值即可。

反转字典

顾名思义,反转字典就是要将字典的值作为键,而键作为值,在原来的字典中,由于键是唯一的,所以可能会出现有多个相同的值,这个时候需要一个列表来存储新的值。

1
2
3
4
5
6
7
8
9
def invert_dict(d):
inverse = {}
for key in d:
val = d[key]
if val not in inverse:
inverse[val] = [key]
else:
inverse[val].append(key)
return inverse

优化的斐波那契数列

传统的斐波那契数列当参数变的较大时,函数运行的时间非常长,分析函数调用图可以发现,很多值是被重复计算的,因此可以将已经计算过的值保存在字典中。

1
2
3
4
5
6
7
8
known = {0: 0, 1: 1}
def fibonacci(n):
if n in known:
return known[n]
else:
res = fibonacci(n - 1) + fibonacci(n - 2)
known[n] = res
return res

使用字典作为备忘,可以使得程序的运行速度大大提高。

元组

作为另外一种内置类型,元组最大的特点就是不可变,元组和列表类似,可以通过下标索引。

创建元组

元组就是用 , 分割的一列值:

1
2
3
>>> t = 'a', 'b', 'c', 'd'  # 这种创建方法不常用,但是需要了解
>>> t
('a', 'b', 'c', 'd')

通常创建元组需要用括号括起来:

1
>>> t = ('a', 'b', 'c', 'd')

如果元组只包含一个元素,需要在元素后面加上逗号:

1
2
>>> t = 'a',
>>> t = ('a',)

还可以通过 tuple 函数创建:

1
2
3
4
5
6
>>> t = tuple()
>>> t
()
>>> t = tuple('tuple')
>>> t
('t', 'u', 'p', 'l', 'e')

不带参数会创建一个空的元组,如果参数是一个序列,结果就是一个包含序列的元素的元组。

除此之外,tuple 也支持切片操作,但不支持所有的修改操作。

元组赋值

Python 中交换两个变量的值非常轻松:

1
>>> a, b = b, a

一条语句即可完成交换,另外,语句的右边可以是任意类型的序列,例如想要拆分电子邮件地址:

1
2
3
4
5
6
>>> addr = 'monty@python.org'
>>> uname, domain = addr.split('@')
>>> uname
'monty'
>>> domain
'python.org'

参数的收集和分散

函数可以接收不定个数的参数,使用 * 操作符来收集参数:

1
2
def printall(*args):
print (args)

* 会将所有的参数收集到一个元组中。

另外,如果有一个序列的值想将它们作为可变长参数传入到函数中,可以使用 * 操作符:

1
2
3
>>> t = (7, 3)
>>> divmod(*t)
(2, 1)

列表和元组

zip 函数可以接收多个序列,并返回一个元组列表,长度是序列中较短的一个,zip 是一种迭代器,可以使用 for 循环遍历,可以使用 zip 对象制作一个列表:

1
2
>>> list(zip('abc', '123'))
[('a', '1'), ('b', '2'), ('c', '3')]

如果需要遍历序列中的元素及其下标,可以使用 enumerate 函数:

1
2
3
4
5
6
>>> for index, element in enumerate('abc'):
... print(index, element)
...
0 a
1 b
2 c

字典和元组

字典中的 items 方法返回元组序列,另外,使用 dict 和 zip 可以得到一个简洁的创建字典的方法:

1
2
3
>>> d = dict(zip('abc', range(3)))
>>> d
{'a': 0, 'b': 1, 'c': 2}

向下取整(//)和取余(%)

两个数相除,传统的除法会得到一个浮点数,向下取整会得到一个整数。

1
2
3
4
5
6
7
>>> minutes = 105
>>> minutes / 60
1.75
>>> minutes // 60
1
>>> minutes % 60
45

取余可以用来获取一个数后一位或者后几位数字,例如 x % 10 可以得到个位数字,x % 100 可以得到后两位数字;还可以检验是否能够被一个数整除。

在 Python 2 中,除法操作符(/)左右的操作对象都是整数时,进行的是向下取整操作,而有一个数是浮点数时,进行的就是浮点数操作。

1
2
3
4
>>> 65 / 3
21
>>> 65.0 / 3
21.666666666666668

无限递归的避免

函数调用自己也是一种合法行为,我们通常称为递归,但是如果一个递归永远达不到退出条件,就会无限的递归下去。

1
2
def recurse():
recurse()

因此写递归函数的时候,一定要加上一个退出的条件,如:

1
2
3
4
5
6
def countdown(n):
if n <= 0:
print('Bye!')
else:
print(n)
countdown(n-1)

该函数会在 n <= 0 的时候退出。

增量开发与函数的简化

通常在编写一个函数的时候会经常遇到输出中间值来验证程序的运行,这些中间值是便于我们调试而产生的,因此这个过程称为增量开发。

例如计算圆的面积:

1
2
3
4
5
def circle_area(xc, yc, xp, yp):
radius = distance(dc, yc, xp, yp) # 计算圆的半径的函数
result = area(radius) # 计算圆的面积
print(radius, result)
return result

这里面,radius 和 result 都是为了方便调试而设置的中间值,因此可以简化该函数:

1
2
def circle_area(xc, yc, xp, yp):
return area(distance(xc, yc, xp, yp))

再比如判断一个数能否被整除:

1
2
3
4
5
def is_divisible(x, y):
if x % y == 0:
return True
else:
return False

可以直接简化为:

1
2
def is_divisible(x, y):
return x % y == 0

函数代码是不是简洁了许多?当然这种情况只适用于这些值不需要的情况,在大型程序中如果这些值还会用到,就不必简化了,那样反而会使程序太过复杂。

首先介绍一个库,Python 中有一个模块叫 turtle,是一个图形库,可以用来画一些简单的形状。我将基于这个图形库教会大家如何做接口设计。

先来创建一个 turtle 对象。

1
2
3
import turtle
bob = turtle.Turtle()
turtle.mainloop()

这段代码就会新建一个窗口,里面包含一个小箭头,这个小箭头就是画图的起点。

下面介绍一下怎么用 turtle 来画图,以下是常用的方法,记住这些就够了。

1
2
3
4
5
6
7
8
9
import turtle
bob = turtle.Turtle() # 创建 turtle 对象
bob.fd(100) # 向前移动 100 个像素
bob.bk(100) # 向后移动 100 个像素
bob.lt(90) # 左转 90 度
bob.rt(90) # 右转 90 度
bob.pu() # 笔尖朝上
bob.pd() # 笔尖朝下
turtle.mainloop()

第一个任务,画一个正方形

当然可以用简单重复的办法来画,事实上新手也是这么做的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import turtle
bob = turtle.Turtle()

bob.fd(100)

bob.rt(90)
bob.fd(100)

bob.rt(90)
bob.fd(100)

bob.rt(90)
bob.fd(100)

turtle.mainloop()

更进一步你想到了用 for 循环:

1
2
3
4
5
6
7
8
import turtle
bob = turtle.Turtle()

for i in range(4):
bob.fd(100)
bob.rt(90)

turtle.mainloop()

(细心的同学可能会发现箭头方向变了)

这时,为了提高代码的可读性和重用性,一般会将代码封装起来,成为一个函数:

1
2
3
4
5
6
def square(t):
for i in range(4):
bob.fd(100)
bob.rt(90)

square(bob)

然后你可能会想了,这正方形的边长都是固定的,我想画一个不一样的怎么办?

第二个任务,画一个多边形

这个时候我们需要泛化

1
2
3
4
5
6
def square(t, length):
for i in range(4):
bob.fd(length)
bob.rt(90)

square(bob, 100)

更进一步,想要任意边数的多边形:

1
2
3
4
5
6
7
8
def polygon(t, n, length):
angle = 360/n
for i in range(n):
bob.fd(length)
bob.rt(angle)

polygon(bob, 7, 70)
polygon(bob, n=7, length=70) # 关键字参数

现在你就知道了,泛化就是给函数添加参数的过程,当参数比较多的时候可以用关键字参数。

第三个任务,画一个圆

这一步要写一个 circle 函数,接受形参 r,表示圆的半径,下面是一个例子:

1
2
3
4
5
6
7
def circle(t, r):
circumference = 2 * math.pi * r # math 是一个数学模块,math.pi 指 π 的值
n = 50
length = circumference / n
polygon(t, n, length)

circle(bob, 70)

这个方案的问题在于,n 是一个定值,我们是通过画很多个边,来近似成一个圆的,我们可以加上一个形参,给用户更多的选择,但是,这样接口就不太整洁。

函数的接口是如何使用函数的说明:有哪些参数?这个函数做什么?返回值是什么?

说一个接口整洁,是说它能够让调用者完成想要完成的事情,而不用关注细节,这里面 n 就属于画圆的细节,下面是另一个例子:

1
2
3
4
5
def circle(t, r):
circumference = 2 * math.pi * r # math 是一个数学模块,math.pi 指 π 的值
n = int(circumference / 3) + 1
length = circumference / n
polygon(t, n, length)

这里面 n 的值是一个接近 circumference / 3 的整数,所以每个边长都近似是 3,已经小到足够画出好看的圆了。

第四个任务,画一个圆弧

写 circle 函数的时候,可以复用 polygon,因为边数很多的正方形就是圆。但是圆弧则不太好办,因此需要修改 polygon 函数:

1
2
3
4
5
6
7
8
9
def arc(t, r, angle):
arc_length = 2 * math.pi * r * angle / 360
n = int(arc_length / 3) + 1
step_length = arc_length / n
step_angle = angle / n

for i in range(n):
t.fd(step_length)
t.lt(step_angle)

你会发现,这个函数下面的部分很像 polygon 函数,但是如果不修改 polygon 的接口,就没办法直接用,我们也可以泛化 polygon 函数,但是那样就不叫 polygon(多边形)了,因此将更泛化的名字叫 polyline(多边线):

1
2
3
4
def polyline(t, n, length, angle):
for i in range(n):
t.fd(length)
t.rt(angle)

现在就可以重写 polygon 和 arc 了:

1
2
3
4
5
6
7
8
9
10
def polygon(t, n, length):
angle = 360 / n
polyline(t, n, length, angle)

def arc(t, r, angle):
arc_length = 2 * math.pi * r * angle / 360
n = int(arc_length / 3) + 1
step_length = arc_length / n
step_angle = angle / n
polyline(t, n, step_length, step_angle)

最后,可以重写 circle,调用 arc:

1
2
def circle(t, r):
arc(t, r, 360)

这个过程,叫重构

而一个设计良好的接口,文档字符串是必不可少的,一般用三引号括起来:

1
2
3
4
5
6
7
8
def polyline(t, n, length, angle):
"""
Draws n line segments with the given length and angle between them. t is a turtle.

"""
for i in range(n):
t.fd(length)
t.rt(angle)

下面我们总结一下:

我们做一个开发计划一般有以下步骤:

  1. 最开始写一些小程序,不需要函数定义;
  2. 将部分功能封装成函数;
  3. 泛化函数,添加合适的形参;
  4. 重复 1 到 3;
  5. 重构程序,如果有相似的代码的话,就做成一个更通用的函数。

今天学到了几个概念,一并总结一下:

  1. 封装就是将部分功能组成一个函数;
  2. 泛化就是给函数添加形参;
  3. 接口需要整洁,形参中不要有关于函数内部细节的参数;
  4. 重构相似的代码,使代码更为通用。