python算法教程第二章节

第二章基础知识

2.1 核心理念

算法：指一个执行过程，包含了能够解决某个特定问题的有限步骤集。
正规描述形式：图灵机或随机存取机
属性：1.执行完一条指令才执行其他指令
2. 基本操作，如算数运算，比较运算及内存存取，所耗费时间为常数级

2.2 渐近记法

常数单位上的差距（这通常取决于一些特定事物，如通用编程语言的性能、硬件速度等），以及其在问题规模扩大时运行时间的增长幅度，才是我们研究算法分析时所要关心的重点。因此需要特定的表示方法去进行算法分析。

2.21 大O记法

渐近记法使用的是一组由希腊字母构成的记号体系。这之中最重要的记号（也是我们今后要用到的）分别是O （原本应读作omicron，但我们一般将其读作“大O ”）、Ω（omega）、Θ（theta）。

O 记法所代表的其实是所谓的渐近上界，而Ω记法所代表的则是渐近下界。

Θ记号所代表的集合正好是前面两种记号的交集，即Θ(g ) = O (g ) ∩ Ω(g )。

e.g. 当3n2 + 2属于Θ(n2)成立时，同样的关系也可以被写成n2属于Θ(3n2 + 2)。

2.22 常用时间复杂度

表2-1 几种常见的渐近运行时间实例

时间复杂度	相关名称	相关示例及说明
Θ(1)	常数级	哈希表的查询与修改（详见与dict相关的黑盒子专栏）
Θ(lg n )	对数级	二分搜索（详见第6章）。其对数基数并不重要4
Θ(n )	线性级	列表的遍历
Θ(n lg n )	线性对数级	任意值序列的最优化排序（详见第6章），其复杂度等同Θ(lg n !)
Θ(n^2)	平方级	拿n 个对象进行相互比对（详见第3章）
Θ(n^3)	立方级	Floyd-Warshall算法（详见第8、9章）
O(n^k )	多项式级	基于n 的k 层嵌套循环（其中k 为整数），且必须满足常数 k > 0
Ω(k^n )	指数级	每n 项产生一个子集（其中k = 2，详见第3章），且必须满足k > 1
Θ(n !)	阶乘级	对n 个值执行全排列操作

一个运行时间为多项式复杂度的算法是可以被接受的，而如果为指数复杂度，则通常是不被接受的。根据这种区分，只要运行时间为O (nk )，并且k >0，我们就可以称其为多项式级。反过来说，任何一个运行时间为Ω(kn )——甚至是Θ(n !)——的算法也都会被归于指数级。

2.23 渐近性问题实践

假设调用一次append的复杂度是Θ(1)，而调用一次insert（插入位置是0）的复杂度则为Θ(n )

num.append(1)
num.insert(0,2)

复杂度：Θ(1) + Θ(n ) = Θ(n )

seq=range(5)
s = 0
for x in range seq:
s += x 

复杂度：因为此函数时间复杂度决定因素为遍历，因此时间复杂度为 Θ(n )。 sum 和 map 等时间发杂都也为线性。

嵌套循环

seq=range(5)
s = 0
for x in range seq:
 for y in range seq:
s += x*y

复杂度：代码块的复杂度由其先后执行的语句累加而成。而嵌套循环的复杂度则在此基础上成倍增长。理由很简单：由于外循环每执行一次，内循环都要完整执行一遍。在这种情况下，其复杂度就相当于“线性级乘线性级”，即平方级。换句话说，其运行时间应该为Θ(n ·n ) = Θ(n 2)。实际上，这种乘法规则还可以被用于指代更多层嵌套，只需随之增加其乘方数即可（指数值）。例如，三层循环就是Θ(n3)，而Θ(n4)则意味着四层，依此类推 。

seq = range (n)
for x in seq:
 for y in seq:
s += x*y

 for z in seq:
 	for w in seq:
	s +=x-w

复杂度：Θ(n3)=（Θ(n)+Θ(n 2)）*Θ(n ），遍历一次为n, 嵌套一次 n 2

2.24 三种重要情况

有时候构建一个算法时，因为输入条件的不同，我们需要讨论以下三种情况

1. 最好的情况：当算法遇上最理想输入时候的运行时间。

2. 最坏的情况：通常为最有用的情况，算法最差运行时间。

3. 平均情况：大部分时候需要进行回避

 

我们可以放弃Θ记号的“双边界”，而选择直接用上界或下界，即用O 或Ω来描述问题。

 

2.25 实证式算法评估

算法工程：侧重于降低复杂度中的隐藏常量。 

方法1： 不断尝试各种算法

方法2：通过times模块进行计时操作 （可测试封装函数时间）

import timeit
timeit.timeit('x = 2+2')

0.017068776554085

PS：避免因重复操作带来的副作用

方法3：使用eProfile模块进行函数执行时间统计

import cProfile
cProfile.fun('main()')

方法4：利用matplotlib绘制出结果

练习题

2-1. 当我们用Python中的list构建一个多维数组时，通常需要使用循环来完成（或某种与list推导式等效的技术），为什么不能用表达式[[0]*10]*10来创建一个10×10的数组呢？这样做会有什么问题吗？

2-2. 让我们来做个假设（也许会有点不切实际）：如果我们允许在分配内存时出现未初始化的情况（也就是说，这块内存中还保有上一次被使用时留下的“垃圾数据”），并且分配内存也只需要常数时间。这时如果您想创建一个含有n 个整数的数组，并且希望跟踪其每一项——看看它是处于非初始化状态，还是您已经在它里面保存过一个数字了。这种检查操作也是可以在常数时间内完成的。那么，我们究竟应该怎样做，才能保证它在常数时间内完成它的初始化操作呢？（以及应该如何在常数时间里完成一个空邻接数组的初始化操作，以避免其成为一个以平方级时间为最小运行时间的操作？）

2-3. 请证明O 与Ω的性质正好相反，即如果f = O (g )，那么g = Ω(f )，反之亦然。

2-4. 对数通常有各自不同的底数，但在算法学上，我们往往并不会太在意它。为了明白其中的原因，我们可以来考虑一下这个等式：logbn= (logan )/(logab)。首先，您知道这个等式为什么成立吗？其次，为什么它能告诉我们不需要去操心对数的底数问题？

2-5. 请证明任何指数级操作（Θ(kn )，其中k > 1）的增长都要快于多项式级操作（Θ(nj )，其中j > 0）。

2-6. 请证明任何多项式操作（Θ(nk )，其中k 为任意常数且k > 0）的渐近增长都要快于对数级操作（Θ(lg n )）。（值得注意的是，这里的多项式中包括根数在内，如平方根（k = 0.5）等）。

2-7. 请研究或推算一下Python list类型上各个操作的渐近复杂度，如索引、元素项赋值、顺序反转、元素的追加及插入（最后两项我们在list的黑盒子专栏中已经讨论过了）。如果我们改用链表类型来实现这些操作会有什么不同？请以list.extend为例加以说明。

2-8. 请证明表达式Θ(f ) + Θ(g ) = Θ(f + g ) and Θ(f ) · Θ(g ) = Θ(f · g )成立。另外，您也可以试试是否能证明max(Θ(f ), Θ(g )) = Θ(max(f , g )) = Θ(f + g )成立。