1 | 对应本书第二章。 |
2.Analysis
笔记
这章主要讲了算法复杂度的分析。
一. 大O
名称源自于Order of magnitude function $O(f(n))$ 描述了时间复杂度$T(n)$当中增长速度最快的部分。
例如:$T(n)=5n^2+27n+1005$的阶是$O(n^2)$。
因为不同的机器计算速度的区别,和不同的编程语言的效率的不同,所以分析算法的时间复杂度使用这样的粗粒度就足够了。
不同函数的增长速度:
python自带的数据结构:
二. List
Operation | Big-O Efficiency |
---|---|
index [] | O(1) |
index assignment | O(1) |
append | O(1) |
pop() | O(1) |
pop(i) | O(n) |
insert(i,item) | O(n) |
del operator | |
O(n) | |
iteration | O(n) |
contains (in) | O(n) |
get slice [x:y] | O(k) |
del | |
slice | O(n) |
set slice | O(n+k) |
reverse | O(n) |
concatenate | O(k) |
sort | O(n |
log n) | |
multiply | O(nk) |
其中,需要注意的是concatenate还有pop和pop(i)的区别。
三. Dictionary
operation | Big-O Efficiency |
---|---|
copy | O(n) |
get item | O(1) |
set item | |
O(1) | |
delete item | O(1) |
contains (in) | O(1) |
iteration | O(n) |
dict的in操作是O(1),list是O(n)
作业
q1
是证明list的index操作是O(1)。暂且认为list的pop(0)是O(n)是已知条件。
1 | from timeit import Timer |
1 | t5 = Timer("test5()", "from __main__ import test5") |
1 | list index operation: 0.0006067330032237805 milliseconds |
q2
是证明dict的get和set是O(1),先认为dict的遍历是O(n)
1 | def test7(): |
1 | t7 = Timer("test7()", "from __main__ import test7") |
1 | dict set item: 0.13327282800310059 milliseconds |
q3
对比list和dict的del操作
1 | def test10(): |
1 | t10 = Timer("test10()", "from __main__ import test10") |
1 | list del item: 0.14648991199646844 milliseconds |
q4
给定一个list,返回第k小的数。先给出时间复杂度是O(nlogn)的简单版:
1 | def kth_smallest_1(nums, k): |
1 | kth_smallest_1([1, 5,9,10,2,3], 4) |
1 | 5 |
q5
q4时间复杂度是O(n)的解法。利用快排的思路。平均时间复杂度是O(n),最坏情况时间复杂度是$O(n^2)$
1 | def kth_smallest_2(nums, k): |
1 | kth_smallest_2([1,5,9,10,2,3], 4) |
1 | 5 |
1 | t12 = Timer("kth_smallest_1([1, 5,9,10,2,3], 4)", "from __main__ import kth_smallest_1") |
1 | kth_smallest_1: 7.706003088969737e-06 milliseconds |