1.1 数据结构和算法的概念
数据结构与算法相辅相成，不会孤立存在；数据结构是为算法服务的，算法是作用在特定的数据结构之上（如数组具有随机访问的特点，二分查找算法需要用数组来存储数据）。
数据结构是静态的，只是组织数据的一种形式，若不在它的基础上操作、构建算法、孤立存在的数据结构是没有意义的。
两种层面区分数据结构和算法
- 广义：
- 数据结构：一组数据的存储结构
- 算法：操作数据的一组方法
- 狭义：
- 指的是某些著名的数据结构和算法，如：队列、栈、堆、二分查找、动态规划等
为什么学数据结构和算法
学好算法写出 时间复杂度高、空间复杂度高的垃圾代码也会越来越少，可以提升自己的代码性能，从而使自己的编程水平得到质的飞升。
建立时间、空间复杂度意识，写出高质量代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现你的价值，完善人生。
1.2 算法的五大特性
- 输入：算法具有0个或多个输入
- 输出：算法至少有1个或多个输出
- 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
- 确定性：算法中的每一步都有确定的含义，不会出现二义性
- 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
1.3 算法的提出
如果 a+b+c=1000，且 a2+b2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合？
1、方法一：
import time
start_time = time.time()
for a in range(1001):
for b in range(1001):
for c in range(1001):
if a + b + c == 1000 and a**2 + b**2 == c**2:
print(a, b, c)
end_time = time.time()
print('总耗时：', end_time-start_time)
运行结果如下：
0 500 500
200 375 425
375 200 425
500 0 500
总耗时：300.36014199256897
2、方法二：
import time
start_time = time.time()
for a in range(1001):
for b in range(1001):
c = 1000 - a - b
if a**2 + b**2 == c**2:
print(a, b, c)
end_time = time.time()
print('总耗时：', end_time-start_time)
运行结果如下：
0 500 500
200 375 425
375 200 425
500 0 500
总耗时：2.6143789291381836
同样的一道题，只是解题的思路不同，性能却是天差地别，这就是算法的魅力。
1.4 大 O 表示法
理论上来讲依靠执行时间就能衡量一个算法的效率，但若将两个相同的算法放在不同配置的机器上运行，那么单纯地依靠运行时间来衡量，显然是不合理的。那么应该用什么方式来衡量一个算法的效率呢？
算法效率衡量
假设计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么多少个操作就有多少个时间单位。可能每台机器的单位时间不同，但是对算法来说进行多少个基本操作在规模数量级上是相同的，由此可忽略机器环境（配置/网络）对算法的客观影响。
大 O 表示法
下面我们通过两个小示例来理解什么是 大 O 表示法：
假设每行代码执行时间为：unit_time
示例一：
def func():
a = 3 # 1
b = 9 # 2
for i in range(n): # 3
c = a*i + b # 4
return c
第1 、2 行代码各花费 一个 unit_time，而第 3 、4 行需要执行 n 次，各花费 n * unit_time，那么代码总执行时间 T(n) 即为：T(n) = （2n + 2）*unit_time。
示例二：
def func():
a = 3 # 1
b = 9 # 2
for i in range(n): # 3
for j in range(n): # 4
c = a*i + b + j # 5
return c
- 第1 、2 行：
2 * unit_time - 第 3 行：
n * unit_time - 第 4 、5 行：每一行都是
n^2 * unit_time，那么总共为2n^2 * unit_time，因为有内外两层循环
那么代码总执行时间为：T(n) = (2n^2 + n + 2) * unit_time
根据上面两个例子的推导，可以得出一个规律：“所有代码执行时间 T（n）与每行代码执行次数 n 成正比”
将其总结成一个公式，即为 大 O 时间复杂度分析法
T(n) = O(f(n))
- T(n)：代码总执行时间
- n：表示数据规模大小
- f(n)：表示每行代码执行的次数总和
- O：表示代码的执行时间 T(n) 与 f(n) 成正比
当 n 很大时，公式中的 低阶、常量、系数三部分几乎不左右增长趋势，常常忽略不计，而只取 最大量级。所以上述两个例子用 大 O 复杂度表示法表示为：T(n) = O(n)、T(n) = O(n^2)
注意：大 O 时间复杂度不具体表示代码真正运行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫做 ——渐进时间复杂度 （asymptotic time complexity），简称时间复杂度
1.5 时间复杂度分析
如何分析一段代码的时间复杂度，有三个方法：
- 只关注循环次数最多的一段代码：因为低阶、系数、常量随着规模的增长对变化趋势没有很多的影响，所以只取最大量级的，即循环次数最多的那部分。
-
加法法则：总复杂度等于量级最大的那段代码的复杂度（如：
T(n) = (2n^2 + n + 2) * unit_time，只取n^2 - 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
# 若 T1(n) = O(f(n)), T2(n) = O(g(n))，那么
T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))
# 假设 T1(n) = O(n), T2(n) = O(n^2)，那么
T(n) = T1(n) * T2(n) = O(n * n^2) = O(n^3)
1、只关注循环次数最多的代码：
def func(n):
a = 0
b = 1
c = 0
for i in range(n): # 循环 n 次
c += i
return c
第2/3/4 行都是常量级的执行时间，与 n 大小无关，因此对整个复杂度也没有影响。第 6 行循环执行了 n 次，因此总的时间复杂度为 O(n)，只需要关心循环次数最多的代码。
2、加法法则：总复杂度等于量级最大的那段代码的复杂度。
def func(n):
sum_1, p = 0, 1
while p < 100:
sum_1 += sum_1 + p
p += 1
sum_2, q = 0, 1
for i in range(n):
sum_2 += i
sum_3, i, j = 0, 1, 1
for i in range(n):
j = 1
for j in range(n):
sum_3 += i * j
return sum_1, sum_2, sum_3
整段代码可以分为三部分，分别是求：sum_1、sum_2、sum_3 的值，每一部分的时间复杂度为：
-
sum_1：执行了 100 次，但是是常量级，可忽略，为O(1) -
sum_2：循环执行 n 次，为O(n) -
sum_3：两次循环执行 n 次，为O(n^2)
总的时间复杂度为：O(1) + O(n) + O(n^2)，取最大量级为：O(n^2)
3、乘法法则：
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
def func(m, n):
a, b, sum = 0, 0, 0
for i in range(n):
a = b + i
for p in m:
sum = a + p
return sum
时间复杂度为：O(n) * O(n) = O(n^2)
最坏时间复杂度
分析算法时，存在几种可能的考虑：
- 算法完成工作最少需要多少基本操作，即最优时间复杂度
- 算法完成工作最多需要多少基本操作，即最坏时间复杂度
- 算法完成工作平均需要多少基本操作，即平均时间复杂度
最好时间复杂度并没有什么实际意义，往往需要特殊情况才能达到。平均时间复杂度是对这个算法的全面评价，反映了这个算法的本质，但是这种衡量没有保证，不是每个计算都能保证在这个操作内完成。因此我们更应该关心的是最坏时间复杂度，因为不管怎样在这个操作内，都能完成。
1.6 算法分析
现在我们已经知道什么是时间复杂度，也知道怎么用大 O 表示法，现在我们来分析下开头的两个示例各自的时间复杂度。
for a in range(1001):
for b in range(1001):
for c in range(1001):
if a + b + c == 1000 and a**2 + b**2 == c**2:
print(a, b, c)
我们只关注循环次数最多的，根据乘法法则，得出应为：T(n) = (n*n*n)*unit_time 即 O(n^3)
for a in range(1001):
for b in range(1001):
c = 1000 - a - b
if a**2 + b**2 == c**2:
print(a, b, c)
根据加法法则和乘法法则，可得出为：T(n) = (n*n + n*n) * unit_time 即 O(n^2)
随着规模的增长，显然第二个方法要比第一个方法快得多。
1.7 常见时间复杂度
| 执行次数函数举例 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n^2+2n+1 | O(n^2) | 平方阶 |
| 5log2n+20 | O(logn) | 对数阶 |
| 2n+3nlog2n+19 | O(nlogn) | 线性对数阶 |
| 6n3+2n2+3n+4 | O(n^3) | 立方阶 |
| 2^n | O(2^n) | 指数阶 |
| n! | O(n!) | 阶乘阶 |
| n^k | O(n^k) | k 次方阶 |
Tips：
log2n（以2为底的对数）简写成logn
常见时间复杂度对比
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2^n) < O(n!) < O(nn)
1.8 Python 内置类型分析
Python 给我们提供了一个 timit 模块，可以用来测试一小段 Python 代码的执行速度。
# 类 Timer 是测量小段代码执行速度的类
Timer(stmt='pass', setup='pass', timer=<timer function>)
# stmt参数是要测试的代码语句（statment）
# setup参数是运行代码时需要的设置
# timer参数是一个定时器函数，与平台有关
# timeit() 方法，执行速度的对象方法，number参数是测试代码时的测试次数，默认为1000000次，返回执行代码的平均耗时，一个float类型的秒数
timeit(number=1000000)
示例
from timeit import Timer
def test1():
"""列表相加"""
l = []
for i in range(1000):
l = l + [i]
def test2():
"""append 尾部添加"""
l = []
for i in range(1000):
l.append(i)
def test3():
"""列表生成式"""
l = [i for i in range(1000)]
def test4():
"""range() 方法"""
l = list(range(1000))
t1 = Timer('test1()', 'from __main__ import test1')
t2 = Timer('test2()', 'from __main__ import test2')
t3 = Timer('test3()', 'from __main__ import test3')
t4 = Timer('test4()', 'from __main__ import test4')
print('test1 总耗时：', t1.timeit(number=1000), '秒')
print('test2 总耗时：', t2.timeit(number=1000), '秒')
print('test3 总耗时：', t3.timeit(number=1000), '秒')
print('test4 总耗时：', t4.timeit(number=1000), '秒')
运行结果：
test1 总耗时： 2.0456191 秒
test2 总耗时： 0.10657389999999989 秒
test3 总耗时： 0.03904730000000001 秒
test4 总耗时： 0.016495899999999786 秒
list pop 测试
from timeit import Timer
x = list(range(2000000))
pop_zero = Timer("x.pop(0)","from __main__ import x")
print("pop_zero ",pop_zero.timeit(number=1000), "seconds")
y = list(range(2000000))
pop_end = Timer("y.pop()","from __main__ import y")
print("pop_end ",pop_end.timeit(number=1000), "seconds")
运行结果：
pop_zero 2.4630802 seconds
pop_end 0.00010299999999974219 seconds
列表常见操作的时间复杂度
| 操作 | 时间复杂度 | 操作 | 时间复杂度 |
|---|---|---|---|
| index() | O(1) | index assignment 索引赋值 | O(1) |
| append() | O(1) | pop() | O(1) |
| pop(i) | O(n) | insert(i, item) | O(n) |
| del list | O(n) | iteration 迭代 | O(n) |
| contains(in) 包含 | O(n) | get slice [x:y] 分片 | O(k) |
| set slice | O(n + k) | reverse() 翻转 | O(n) |
| concatenate 两个列表拼接 | O(k) | sort() 排序 | O(nlogn) |
| multiply 两个列表相乘 | O(nk) |
字典常见操作时间复杂度
| 操作 | 时间复杂度 | 操作 | 时间复杂度 |
|---|---|---|---|
| copy | O(n) | get(item) | O(1) |
| set(item) | O(1) | delete item | O(1) |
| contains(in) | O(1) | iteration 迭代 | O(n) |
1.9 常用数据结构的算法
要想搞懂什么是数据结构，就要懂得什么是数据，什么又是结构？
数据是一种抽象的概念，我们经常与之打交道，它有不同的存储类型，就Python 中有：
int、float、list、dict等。数据之间存储不是相互独立的，而是以一种特殊的关系联系在一起，这就是结构。
Python 给我们提供了很多内置的数据结构类型：int、float、list、dict...，而有一些并没有提供，需要我们自己去定义，如：队列、栈等。
算法与数据结构区别
- 数据结构是存储数据的一种表现形式
- 算法是解决问题的一种设计
一个好的程序应该是在合适的数据结构基础上选择算法。一个合适的数据结构非常重要，比如：存储全世界人们的个人信息，如果用列表存储。那么遍历时其时间复杂度为 O(n)，而用字典存储，遍历其时间复杂度为 O(1)。
常用的数据运算
插入、删除、查找、修改、排序
常用的二十种数据结构和算法
在实际开发中，我们能够经常用到的有如下 20种，数据结构和算法各 10种：
- 数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
