递归
递归行为
任何非递归行为都可以改为递归- 程序会帮我们实现压栈
- 一个函数调用子过程之前,会把自己的所有过程全部压到 栈 中, 信息完全保存
- 子过程返回之后, 会利用这些信息,彻底还原现场.继续执行了
- 就这样完成子过程和父过程的通信
时间复杂度
- 子问题规模一样的时候，使用master公式推理时间复杂度（只分析父问题到子问题的这一步）
- master公式：T(N) = a*T(N/b) + O(N^d)
- log(b, a) > d -> 复杂度为O(N^log(b,a))
- log(b, a) = d -> 复杂度为O(N^d * logN)
- log(b, a) < d -> 复杂度为O(N^d)
- 补充阅读：www.gocalf.com/blog/algorithm-complexity-and-mastertheorem.html
"""
使用递归的方式, 在一个数组中找最大值
找左边的最大值, 再找右边的最大值, 这两个最大的数据, 就是最大值 ==> 分治
"""
class GetMax(object):
def get_max(self, arr: list, L: int, R: int):
"""
无限的缩小, 把大问题 化解 成小问题
这个方法里面, 数组自己没有发生变化, 是取值的索引一直在变
:param arr: 数组本身
:param L: 左边界
:param R: 右边界
:return:
"""
# 终止条件
if L == R:
return arr[L]
mid = int((L + R) / 2)
max_left = self.get_max(arr, L, mid)
max_right = self.get_max(arr, mid + 1, R)
return max(max_left, max_right)
arr = [2, 5, 3, 6]
max_num = GetMax().get_max(arr, 0, len(arr) - 1)
print(max_num)
归并排序
时间复杂度O(N*logN)
额外空间复杂度O(N)
- 采用分治法
- 分割：递归地把当前序列平均分割成两半
- 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）
class MergeSort(object):
def __init__(self, arr: list):
self.arr = arr
def sort(self):
if self.arr and len(self.arr) > 2:
# sortProcess: 递归过程，排序的实质
self.sort_process(self.arr, 0, len(self.arr) - 1)
return self.arr
def sort_process(self, arr: list, L: int, R: int):
"""
归并排序, 从L~R上排好序
:param arr: 无序数列
:return: 有序数列
"""
if L != R: # L=R：数列中只有一个数
mid = int((L + R) / 2)
self.sort_process(arr, L, mid)
self.sort_process(arr, mid + 1, R)
self.merge(arr, L, mid, R)
def merge(self, arr: list, L: int, mid: int, R: int):
"""将左右 有序的 合并 到一起"""
i = 0
p1 = L # 整个左侧部分的最小值
p2 = mid + 1 # 整个右侧的最小值
help = [0] * (R - L + 1)
while p1 <= mid and p2 <= R: # 左右部分，任一部分超出边界，这部分已经填完了
if arr[p1] < arr[p2]:
help[i] = arr[p1]
p1 += 1
else:
help[i] = arr[p2]
p2 += 1
i += 1
# 有且只有一个越界了， 两个while只会有一个发生
while p1 <= mid:
help[i] = arr[p1]
p1 += 1
i += 1
while p2 <= R:
help[i] = arr[p2]
p2 += 1
i += 1
for index in range(len(help)):
self.arr[L + index] = help[index]
arr_ = MergeSort([2, 4, 3, 5, 10, 6, 9, 8, 7]).sort()
print(arr_)
小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。
例子： [1, 3, 4, 2, 5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为：1 + 1 + 3 + 1 + 1 + 3 + 4 + 2 = 16
class SmallSum(object):
"""
小和问题：使用归并排序，每个小组在合并的同时，产生小和
"""
def small_sum(self, arr):
if arr is None or len(arr) < 2:
return 0
return self.merge_sort(arr, 0, len(arr) - 1)
def merge_sort(self, arr: list, L: int, R: int):
if L == R:
return 0
mid = int((L + R) / 2)
# 左侧部分产生的小和 + 右侧部分产生的小和 + merge过程中产生的小和
return self.merge_sort(arr, L, mid) \
+ self.merge_sort(arr, mid + 1, R) \
+ self.merge(arr, L, mid, R)
def merge(self, arr: list, L: int, mid: int, R: int):
help = [0] * (R - L + 1)
p1 = L
p2 = mid + 1
i = result = 0
while p1 <= mid and p2 <= R:
if arr[p1] < arr[p2]:
result += (R - p2 + 1) * arr[p1] # 右侧比x大的数有多少个 * 当前x的数值
help[i] = arr[p1]
p1 += 1
else:
result += 0
help[i] = arr[p2]
p2 += 1
i += 1
while p1 <= mid:
help[i] = arr[p1]
i += 1
p1 += 1
while p2 <= R:
help[i] = arr[p2]
i += 1
p2 += 1
for index in range(len(help)):
arr[L + index] = help[index]
return result
result = SmallSum().small_sum([1, 3, 4, 2, 5])
print(result)
逆序对问题
在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对。
例子：[1, 3, 4, 2, 5]
打印所有逆序对
评论区