MIT6.046算法设计 L2 学习笔记

导入

给一堆非三点共线的点,如何选一个最少点围成的圈,将所有点包围?

image-20231010101024967

点比较少,我们可以直接看出来,并将形成的圈用双向链表表示,记为CH(S)

image-20231010101320617

问题来了,如何找到围成CH(S)的线段呢

选择两点,并用直线将其连接,若剩余的所有点都在同一侧,就表示他是CH(S)中的一条线段

image-20231010101422634

时间复杂度?

O(n^2)找边,O(n)测试是否在同一侧

合并,时间复杂度为O(n^3)

大事化小 -> Merge

如何合并?

image-20231010101711728

现在有左侧的CH(s1)和右侧的CH(s2),如何合并?

将左侧的点,从x最大的点开始顺时针编号,记为a1,a2,a3,a4,a5

右侧的点反之,记为b1,b2,b3

将ai,bj连线与中间直线L的交点y大小记为y(i,j)

下面开始查找最佳线段(上檐部分)

  1. 连接a1,b1,交点记为y(1,1)
  2. 对右侧点进行顺时针替换,即连接a1b2,发现y(1,2)>y(1,1)
  3. 重复2,发现y(1,3)<y(1,2),回退右侧点到b2
  4. 对左侧点进行逆时针替换,发现y(5,2)>y(1,2)
  5. 重复4,y(4,2)>y(5,2)
  6. 继续替换,发现y(3,2)<y(4,2),此时最佳线段确定为(a4,b2)

下檐部分同理,不过是找最小y(i,j)

确定新的最佳上下檐为(a4,b2),(a3,b3)

现在确定合并后新的CH(s)

从新的上檐开始

a4->b2(继续顺时针)->b3[与新的下檐(a3,b3)对应]->a3->a4(至此,新的CH形成)

原理

image-20231010102850566

中值查找

这里没太看懂…看6046总是看着看着就不知道老师在研究什么问题了

这里大概的问题就是给定n个数字,求较低的中值和较高的中值

image-20231010103124691

显然我们可以直接先排序,再直接用索引找到,这样的时间复杂度为nlogn

我们能在复杂度n的情况下实现吗?

改进

image-20231010104012341

图上的Select(S,i)表示查找S中第i大的数字

首先研究在有序数列中的查找

对于一组不重复的有序数列S,设计算法Select(S,i)

  1. 选择一个x进行划分(要cleverly的,尽量选中间值,这样能让左右平衡,让merge更具效率)
  2. 将小于x的数记为集合B,大于x的数记为集合C
    假设集合B中有k-1个元素,集合C中有n-k个元素
  3. 如果k=i,则i就是x
  4. 如果k>i,则在B部分进行查找,Select(B,i)
  5. 如果k<i,则在C部分查找,Select(C,i-k)
这个算法好吗?

在最坏状态,即x取的很烂的情况下,他的时间复杂度是n^2,且我们更偏向于寻找时间复杂度确定的方法

再改进

上面的算法问题在于x的选择

现在,如何Pick X cleverly?

image-20231010105801229

  • 将x分为若干长度为5的数列

  • 对每个数列进行排序

  • 找到每个数列的中值,再找到中值中的中值,将其作为「X」
    对于每个数组,从左往右,按中值递增排序

    这里的5不是固定的,可以换为其他的适当的整数

image-20231010110055280

有多少个数是确信严格大于x的?

下面的这段英文推理我真有点看不懂了,只能知道个大概,就是说至少有若干个大小为5的列能提供大于x的元素,然后那个不足5的数列需要特殊处理

image-20231010111647335

最后,改进后的时间复杂度

image-20231010111704925

总时间复杂度= 找中值的中值的时间+递归处理的时长(不会算..)+对每个数列的排序时间

课上是这样推递归时间的

image-20231010111951227