算法与数据结构
时间复杂度
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n^3)
空间复杂度
内存占用（空间换时间）
递归
经典汉诺塔问题
h(n) = 2h(n-1) + 1
def hanoi(n, a, b, c):
if n > 0:
hanoi(n-1, a, c, b)
print("moving from %s to %s" %(a, c))
hanoi(n-1, b, a, c)
1. 查找
查找目标值的索引
python内置查找函数index（）（使用线性查找）
1.1 顺序查找（线性查找）Linear Search
def linear_search(li, val):
for i in range(range(li)):
if li[i] == val:
return i
return
时间复杂度O(n)
1.2 二分查找 Binary Search
二分查找首要条件序列有序
def binary_search(li, val):
left = 0
right = len(li) - 1
while left < right:
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val:
right = mid -1
else:
left = mid +1
else:
return None
时间复杂度O(logn)
2. 排序
内置函数sort（）
1.1 冒泡排序 Bubble Sort
- 分为无序区和有序区
- 列表每两个相邻的数，如果前面比后面的数大，则交换两个数的位置
- 完成一轮排序之后，无序区减少一个数，有序区增加一个数
def bubble_sort(li):
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
时间复杂度O(n^2)
1.2 选择排序 Select Sort
- 将无序区第一个数与全序列比较大小，与最小的数交换位置
- 将第一轮排序最小的数，放到第一个位置
- 再一轮排序纪录无序区最小的数放入第二个位置，依次类推
- 算法关键点：有序区和无序区、无序区最小数的位置
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
if min_loc != i:
li[i], li[min_loc] = li[min_loc], li[i]
时间复杂度O(n^2)
1.3 插入排序 Insert Sort
- 将初始待排序序列第一个元素划入有序区，后面的全部划为无序区
- 从头到位依次扫描无序区，将扫描到的每个元素插入有序区的适当位置（如果待插入元素与有序区中某个元素相等，则将其插入到相等元素的后面）
def insert_sort(li):
for i in range(1, len(li)-1):
tmp = li[i]
j = i-1
while j >= 0 and li[j] > tmp:
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
时间复杂度O(n^2)
1.4 快速排序 Quick Sort
使用分治法
- 先从序列中抽取一个数作为基准数
- 分区，将比这个数大的全放在它的右边，小于等于的全放左边
- 左右区间重复以上操作，知道各区间只剩下一个为止
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
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)
时间复杂度O(nlogn)
1.5 堆排序 heap_sort
1.5.1 树与二叉树
树是一种可以递归定义的数据结构
树是由n个节点组成的集合
- 如果n=0，那这是一棵空树
- 如果n>0,那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树
满二叉树：每层节点数都达到最大值
完全二叉树：叶子节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
1.5.2 二叉树的存储方式
父节点和左子节点的编号下标的关系 2i+1
父节点和右子节点的编号下标的关系 2i+2
1.5.3 堆
堆是一种特殊的完全二叉树
- 大根堆：一棵完全二叉树，满足任一节点都比子节点大
- 小根堆：一棵完全二叉树，满足任一节点都比子节点小
堆下调整的性质
- 假设根节点的左右子树都是堆，但根节点不满足堆的性质
- 可以通过一次向下调整来将其变成一个堆
1.5.4 堆排序过程
- 建立堆
- 得到堆顶元素，为最大元素
- 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整使堆重新有序（保证完全二叉树）
- 堆顶元素为第二大元素
- 重复步骤三，直到堆空
构造堆（农村包围城市）
def sift(li, low, high):
"""
:param li:
:param low:初始堆顶
:param high:
:return:
"""
i = low
j = 2 * i + 1
tmp = li[i]
while j <= high:
if j < high and li[j] < li[j+1]:
j += 1
if tmp < li[j]:
li[i] = li[j]
i = j
j = 2 * i + 1
else:
break
li[i] = tmp
def heap_sort(li):
n = len(li)
for i in range(n//2-1, -1, -1):
sift(li, i, n-1)
for i in range(n-1, -1, -1):
li[0], li[i] = li[i], li[0]
sift(li, 0, i-1)
li = [i for i in range(1000)]
import random
random.shuffle(li)
heap_sort(li)
print(li)
时间复杂度O(nlogn)
1.5.5 内置模块 heapq
常用函数
heapify(x) 建堆
heappush(heap,item)
heappop(heap)
1.5.6 topk问题
现有n个数，设计算法得到前k大的数(k<n)
解决思路：
- 排序后切片 O(nlogn)
- 冒泡，插入，选择 O(mn)
- 使用堆排序 O(mlogn)
- 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数
- 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整
- 遍历列表所有元素后，倒序弹出堆顶
def sift(li, low, high):
i = low
j = 2 * i + 1
tmp = li[i]
while j <= high:
if j + 1 <= high and li[j] > li[j+1]:
j += 1
if tmp > li[j]:
li[i] = li[j]
i = j
j = 2 * i + 1
else:
break
li[i] = tmp
def topk(li, k):
heap = li[0:k]
for i in range((k-2)//2, -1, -1):
sift(heap, i, k-1)
for i in range(k, len(li)-1):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap, 0, k-1)
for i in range(k-1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
sift(heap, 0, i-1)
return heap
li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
print(topk(li, 10))
|