废话时间：
算法实际上是高于语言的。所以我是第一！！！比如说你的列表.sort 它里面其实就是实现了一种算法。算法：一个计算过程，解决问题的方法。程序 = 数据结构 + 算法。
一：时间复杂度：用来评估算法运行效率（时间）的一个式子。
光年是距离。
一般来说：时间复杂度高的算法比复杂度低的算法慢。
问题规模基本上差不多一样的时候。即n
与机器有关。
时间复杂度是独立于机器的。
常见的时间复杂度：
o(1) < o(logn) < o(n) < o(nlogn) < o(n的平方) < o(n平方logn) < o(n的三次方)
如何简单判断时间复杂度？
最好是根据运行过程来估计找到代表问题规模的n 魑魅魍魉chi‘mei’wang‘liang
如何一眼判断时间复杂度？
是否有循环减半的过程 -> o(logn)几层循环就是n的几次方的复杂度
二：空间复杂度
用来评估算法内存占用大小的一个式子
空间换时间
例如：如果你想让你的算法快点，就需要更多的缓存。
三：基本算法
算法里面重要的思想
递归的两个特点： - 调用自身 - 结束条件def qq(n): if n == 0 : print('我的小可爱',end='') else: print('抱着',end='') qq(n-1) print('的我',end='')qq(5)# 抱着抱着抱着抱着抱着我的小可爱的我的我的我的我的我def fun(x): if x > 0: print(x) fun(x-1)def func(x): if x > 0: func(x-1) 3.0 汉诺塔
当n个盘子时，把n-1看做一部分。 1. 把n-1个圆盘从a经过c移动到b 2. 把第n个圆盘从a移动到c 3. 把n-1个圆盘从b经过a移动到c
t = 0def hanoi(n,a,b,c): global t if n > 0: hanoi(n-1,a,c,b) t +=1 print(':moving from %s --> %s.'%(a,c)) hanoi(n-1,b,a,c)hanoi(5,'a','b','c')print('本次总共运行 %s 次'%t) 汉诺塔移动次数的递推式：h(x) = 2h(x-1)+1
前部分算法分为两部分：查找和排序
3.1 列表查找：从列表中查找指定元素- 输入：列表、待查找元素- 输出：元素下标或未查找到元素3.2 顺序查找- 从列表第一个元素开始，顺序进行搜索，直到找到为止。3.3 二分查找- 从有序列表的候选区data[0:n]开始，通过对待查找的值和候选区中间值的比较，可以使候选区减少一半。
3.1 二分查找
- 使用二分查找来找3
- 1，2，3，4，5，6，7，8，9
- Low high
- mid
- 如果high < low ，说明你要找的值不存在。
def erfen_search(li,val): low = 0 high= len(li) - 1 while low<=high: mid = (low+high) // 2 if li[mid] == val: return mid elif li[mid] < val: low = mid + 1 else: high = mid - 1a = erfen_search([1,2,3,4.123,123,12,3,12,3,12,3,21,3,213,21,321,3,213,21,321,3,21,4,3,543,53,45,435,342,5],435)# 上面这个方法有问题，不信你试。# 递归版本二分查找def bin_search_rec(data_set,value,low,high): if low <= high: mid = (low + high) // 2 if data_set[mid] == value: return mid elif data_set[mid] < value: low = mid + 1 return bin_search_rec(data_set,value,low,high) else: high = mid - 1 return bin_search_rec(data_set,value,low,high) else: return
列表排序
- 列表排序 - 将无序列表变为有序列表。 .sort- 应用场景 - 各种榜单 - 各种表格 - 给二分查找用 - 给其他算法用输入：无序列表输出：有序列表排序Low B三人组- 冒泡排序- 插入排序- 选择排序算法关键点：- 有序区- 无序区升序与降序排序凶凶组：- 快排 - 思路： - 取一个元素p（第一个元素），使元素p归位； - 列表被p分成两部分，左边逗比p小，右边逗比p大‘ - 递归完成排序。 递归终止条件：列表剩一个元素。 - 算法关键点：1. 归位 2. 递归- 堆排- 归并排序没什么人用的排序：- 基数排序- 希尔排序- 桶排序
总览：
| 执行次数函数 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n²+2n+1 | O(n²) | 平方阶 |
| 5log2n + 20 | O(logn) | 对数阶 |
| 2n + 3nlog2n + 19 | O(nlogn) | nlogn阶 |
| 6n³ + 2n² + 3n +4 | O(n³) | 立方阶 |
| 2" | O(2") | 指数阶 |