CSIT5500-1 算法基础

这是学校csit5500的一门课，听着名字就知道很经典。第一节课主要是算法评估，排序，搜索树，红黑树

算法评估

这一节就解释，为什么用O(n)来表示算法的复杂度。

• 不能简单用cpu的时间，因为不固定
• 不同级数之间差异大，同一个级数内差异不大

其他的点：

• 比复杂度的时候，只看最高阶；
• 对数的级数都是一样的；loga n = logb n/(logb a)

算法需要最差评估复杂度，一般不用证明，举例就行。

eg：Worst-Case Analysis of Binary Search
二分搜索最差的情况就是一直排除到最后一半只有一个元素的时候。
复杂度如下：

$$\begin{aligned} T(n) & \leq T(n / 2)+O(1) \\ & \leq T(n / 4)+O(1)+O(1) \\ & \leq T\left(n / 2^{k}\right)+k \cdot O(1) \end{aligned}$$

k可以人为指定成log2(n)

$$\begin{aligned} T(n) & \leq T(1)+\log _{2} n \cdot O(1) \\ &=O(1)+O(\log n) \\ &=O(\log n) \end{aligned}$$

排序

又到了经典的排序环节，直接引用我觉得写得最完整的两个博文十大排序动图演示
python十大排序

课上跳过了最简单的主要讲了O(nlogn)的三个，并归，快速，堆。

并归merge

简单的dc思路，先对数组分成两半，左右各自排序，然后用两个指针同时扫一遍，合起来。
这个过程递归到，两半只有一个元素的时候，就可以了。

• 最坏情况复杂度
  并归有两个过程，第一，遍历数组，统计长度，复杂度O(N).
  第二，merge.
  最好情况是，左：12345 右：6789，这样复杂度是O(N/2)=O(N).
  最差情况是，左：13579 右：2468，这样复杂度也是O(N).
  所以，两个过程加起来也是O(N)。

然后进入到递归的过程：与二分搜索相似

$$\begin{aligned} T(n) & \leq 2 T(n / 2)+O(n) \\ & \leq 2(2 T(n / 4)+O(n / 2))+O(n) \\ & \leq 4 T(n / 4)+O(n)+O(n) \\ & \leq 2^{k} T\left(n / 2^{k}\right)+k \cdot O(n) \end{aligned}$$

直接取k=log2n

$$\begin{aligned} T(n) & \leq 2^{\log _{2} n} T(1)+\log _{2} n \cdot O(n) \\ & \leq O(n)+O(n \log n) \\ & \leq O(n \log n) \end{aligned}$$

所以最坏情况也是这个，并归排序复杂度是稳定的。

def MergeSort(lists):
    if len(lists)<2:
        return lists
    mid = int(len(lists)/2)
    print(mid)
    left = MergeSort(lists[:mid])
    print(left)
    right = MergeSort(lists[mid:])
    l = r =0
    res = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            res.append(left[l])
            l+=1
        else:
            res.append(right[r])
            r+=1
    res +=left[l:]
    res +=right[r:]
    return res

快速

快排的思路是任选一个元素，然后把数组分成两半，再分别对两半进行这个过程。也是dc的思路。

	# @quickSort
def quickSort(array):
	if len(array) < 2:  # 基线条件（停止递归的条件）
		return array
	else:  # 递归条件
		baseValue = array[0]  # 选择基准# 由所有小于基准值的元素组成的子数组
		less = [m for m in array[1:] if m < baseValue]# 包括基准在内的同时和基准相等的元素，在上一个版本的百科当中，并没有考虑相等元素
		equal = [w for w in array if w ==baseValue]# 由所有大于基准值的元素组成的子数组
		greater = [n for n in array[1:] if n > baseValue]
	return quickSort(less) + equal + quickSort(greater)

快速排序vs堆排序

我们讨论的排序都是基于比较的，不基于比较的排序：计数排序(O(n)，内存够用的情况下)，基数排序（O(m*n)），桶排序(O(n)，输入数据分布均匀的情况下)

大数排序中，快排比堆排序好。

1. 堆排序需要用数组下标来回访问元素，对缓存不友好，但是快速排序是顺序访问，就可以顺着cpu的缓存进行遍历(内存访问（跳跃式还是连续方式）)
2. 堆排序做数据的交换要比快速排序交换的次数多，因为在建堆的过程，数据被打乱. 所以，虽然都是o(nlogn)但是堆排序前面的常数项是一般大于快速排序的

排序的上限为什么是o(nlogn)？

堆

堆排序就高端一点，用了根堆(heap)的结构。
巧妙的是，通过利用完全二叉树的结构，通过数组的位置，就实现了这个根堆的过程。

def heapSort(nums):
    def heapify(nums,n,i):
        large = i
        left = 2*i+1
        right = 2*i+2
        if left<n and nums[left]>nums[large]: large = left
        if right<n and nums[right]>nums[large]: large = right
        if large!=i:
            nums[i],nums[large]=nums[large],nums[i]
            heapify(nums,n,large)
            
    n = len(nums)
    for i in range(n/2,-1,-1):
        print(i)
        heapify(nums,n,i)
    for i in range(n-1,-1,-1):
        print(i)
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, i, 0)
    return nums

复习树🌲的知识：

• 二叉树：每一个节点最多两个孩子
• 满二叉树Full binary tree：每个子节点都有两个元素
• 完美二叉树Perfect binary tree：每一层都填满了
• 完全二叉树Complete binary tree：除了最后一层其他每一层都是完全填满的，而最后一层从左往右依次排列

堆排序的过程

• def: 小(大)根堆：完全二叉树 + 每个节点小于(大于)他的子节点。

  先把数组构造成最小根堆(最大或者最小都行)
  while 根堆还有元素:
  ——-弹出顶部最大值
  ——-重新构造最小根堆

所以堆排序的过程主要是构造(初始化)根堆，和弹出最小值之后再构建根堆(重新维持稳定)根堆。初始化等于一个一个元素插入，重新维持相当于从堆中删除元素。
所以，主要是两个步骤：插入和删除。

插入节点：

插入到完全二叉树的最后
如果有父节点&&父节点比自己小：
——-两个节点交换位置

移动次数=层数 所以插入的时间复杂度O(log n)

删除节点：

删除根节点，让末尾最大的值成为新的根节点
如果有子节点&&子节点比自己小：
——-选择子节点中小的那个，两个节点交换位置

移动次数=层数 所以删除的时间复杂度O(log n)

完全二叉树和数值的索引对应关系

父节点 i 找子节点：2i+1 , 2i+2
子节点找父节点： [(i-1)/2] 向下取整

二叉搜索树 BST博客

• Def: 任何一个节点，小于右子节点，大于左子节点
  条件不够苛刻，二叉搜索树不唯一。

节点的后继：

大于这个节点的最小的值。
分两种情况，如果这个节点x有右子树，那么这个继承者就是右子树的最小值。
如果没有右子树，那么就是这个节点一直往上，第一个向右走的父节点。
如图。

插入

插入很简单，就和查找一样，找到一个位置塞进去就好了。

删除

删除分情况

1. 如果0个孩子，直接删
2. 如果1个孩子，用孩子代替这个位置
3. 如果2个孩子，删除孩子的后继，用后继补充这个位置