终其一生,我们只不过在寻找自己

0%

CSIT5500-1 算法基础

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

算法评估

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

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

其他的点:

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

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

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

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

排序

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

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

并归merge

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

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

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

直接取k=log2n

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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的思路。

1
2
3
4
5
6
7
8
9
10
	# @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)的结构。
巧妙的是,通过利用完全二叉树的结构,通过数组的位置,就实现了这个根堆的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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个孩子,删除孩子的后继,用后继补充这个位置
-------------    你的留言  是我更新的动力😊    -------------