基础
时间复杂度
一种表示算法快慢的方式
是用来估计算法运行时间的一个式子(单位)
一般来说, 时间复杂度高的算法比时间复杂度低的算法慢
- 一行代码的时间复杂度1 :
- 一个 for 循环时间复杂度为:
- 两层循环时间复杂度:
例:
时间复杂度为 的代码
1
2
3
| for i in range(n):
for j in range(n):
print("Hello~")
|
时间复杂度为 的代码
1
2
3
| while n > 1:
print(n)
n = n // 2
|
简单来说, 当算法过程出现循环折半的时候
时间复杂度就会出现
简单判断时间复杂度
绝大多数简单情况:
- 确定问题规模
n
- 循环过程减半
- k 层关于 n 的循环
空间复杂度
用于评估算法内存占用的式子
空间复杂度的表示方式与时间复杂度完成一样
- 算法使用了几个变量:
- 算法使用了长度为 n 的一维列表:
- 算法使用了 m 行 n 列的二维列表:
在算法中, 时间远比空间重要
因此, 大多算法常采用 “时间换空间” 的做法
递归
递归的特点:
例:
1
2
3
4
5
6
7
8
9
10
| def go(x: int):
if x > 0:
print(x)
go(x - 1)
go(3)
>>>3
>>>2
>>>1
|
1
2
3
4
5
6
7
8
9
10
| def go(x: int):
if x > 0:
go(x - 1)
print(x)
go(3)
>>>1
>>>2
>>>3
|
汉诺塔
著名的递归问题, 具体内容自己网上查
当有 n 个盘子时:
- 把 n-1 个盘子从 A 经过 C 移动到 B
- 把 n 个盘子从 A 移动到 C
- 把 n-1 个小圆盘经过 A 移动到 C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def hanoi(n, a, b, c):
'''
参数a, b, c 分别对应a柱, b柱, c柱
'''
if n > 0:
hanoi(n-1, a, c, b)
print(f"把{a}移动到{c}上")
hanoi(n-1, b, a, c)
hanoi(3, "A", "B", "C")
|
查找
查找: 在一些数据元素中
通过一定的方法找出与给定关键字相同的数据元素的过程
列表查找(线性表查找): 从列表中查找指定元素
顺序查找
也称线性查找, 从列表的第一个元素开始
顺序进行搜索, 直到找到元素或搜索到列表最后一个元素为止
例:
1
2
3
4
5
6
7
|
def linear_search():
for i, e in enumerate(li):
if e == value:
return e
else:
return -1
|
二分查找
二分查找仅适用于有序列表
又称折半查找, 从有序列表的初始候选区 li[0:n] 开始
通过对待查找的值与候选区中间值的比较, 可以使候选区减少一半
例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def binary_search(value, li: list) -> int:
left = 0
right = len(li) - 1
while left < right:
mid = (left + right) // 2
if li[mid] == value:
return mid
elif li[mid] > value:
right = mid - 1
else:
left = mid + 1
else:
return -1
|
排序
将一组无序的记录序列调整为有序的记录序列
简单的排序:
复杂的排序:
冒泡排序
过于简单, 不予介绍
例:
1
2
3
4
5
| def bubble_sort(li: list):
for i in range(len(li) - 1):
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
|
时间复杂度:
改进代码:
如果在冒泡排序过程中
二层循环没有发生冒泡, 就说明列表已经排序完成
可以直接终止循环
1
2
3
4
5
6
7
8
9
| def bubble_sort(li: list):
for i in range(len(li) - 1):
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange:
return
|
选择排序
简单的选择排序
遍历一遍列表, 将最小的数添加进新列表
然后删除旧列表中的最小数
1
2
3
4
5
6
7
| def select_sort_simple():
new_li = []
for i in range(len(li)):
min_val = min(li)
new_li.append(min_val)
li.remove(min_val)
return new_li
|
min(li) 和 li.remove(min_val) 的时间复杂度为
该代码的时间复杂度为:
该算法空间复杂度较大, 不推荐使用
改进的选择排序
相较于冒泡排序, 这一算法的交换次数会较少一点
原理:
第一层循环为有序区的起始位置
第二层循环找到最小的数的位置, 并将最小数移动到有序区
1
2
3
4
5
6
7
8
| def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i+1, len(li)):
if li[j] < li[min_loc]:
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i]
|
插入排序
原理:
第一层循环为无序区
第二层循环, 判断插入元素大小
按要求移动有序区元素, 然后将元素有序的插入有序区
tmp 为插入的元素
i 为无序区的起始位置
j 为有序区的结束位置
1
2
3
4
5
6
7
8
| def insert_sort(li):
for i in range(1, len(li)):
tmp = li[i]
j = i - 1
while tmp < li[j] and j>= 0:
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
|
时间复杂度:
快速排序
原理:
- 取一个元素 p(第一个元素), 使元素 p 归位
- 归位: 列表 p 分为两部分, 左边比 p 小, 右边比 p 大
- 递归完成排序
1
2
3
4
5
6
7
8
|
[5, 7, 4, 6, 3, 1, 2, 9, 8]
[2, 1, 4, 3, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
|
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp:
left += 1
li [right] = li[left]
li[left] = tmp
return left
|
1
2
3
4
5
| def quick_sort(li, left, right):
if left < right:
mid = partition(li, left, right)
quick_sort(li, left, mid-1)
quick_sort(li, mid+1, right)
|
由于 python 有着递归深度限制, 默认为 1000
所以上述代码在排序较大的列表时, 会引发 maximum recursion depth exceeded in comparison 报错
不建议使用太深的递归算法
在最坏的情况下(即倒序的列表), 时间复杂的为
堆排序