算法课第六章

Posted on

记录

分治

分治算法的优缺：

考虑的细节比循环迭代要少，写起来简单，理解起来也容易，通常是一些递归算法

但当有大量返回值时，会增加系统开销

分治范式：1. 划分； 2. 治理； 3. 组合

递归算法和迭代算法的转换 自己找资料掌握

二分法

二分搜索

递归方法实现，循环方法实现

二分搜索的扩展

扩展一：如果有序数组中有重复元素，1. 要寻找第一个等于k的；2. 也可以寻找第一个大于k的；3. 或者等于k的范围；

类似思路的问题：木棒切割问题

扩展二：一些数学问题的求解

例一： 通过f(x)=x^2在[1,2]范围内的二分求解 根号2 的值

例二：装水问题

1
const double eps = le-5; // 这里精度设置为10^-5，可以根据题目要求来

扩展三**：寻找旋转数组中的最大值，要求：时间复杂度为log(n)

对于一个升序的数组A[1…n]，对其变换，为[Ak+1, Ak+2, …, An, A1, A2…Ak]，这样一个数组被称为原数组A的一个k旋转

合并排序

算法复杂度nlog(n)，将小范围的数组进行排序，最后得到有序数组

寻找第k小元素

最简单方法，对数组进行排序，然后易得第k小元素。虽然方法简单，但我们知道排序算法时间复杂度最低也需要nlog(n)

如果要求设计一个时间复杂度为O(n)的算法，应该怎么办呢？
在分析二分法之前，先来了解一下其他的几种解法：(这里参考了博文)

  1. 排序，然后找出第k小元素；时间复杂度O(nlog(n)+K)
  2. 用大小为K的数组存前K个数，然后找出这K个数中最大的数设为kmax，用时O(K)。遍历后面的N-K个数，如果有小于kmax的数，则将其替换kmax，并从新的K个数中重新选取最大的值kmax，更新用时O(K)。所以总的时间为O(NK)
  3. 利用堆的性质
  4. 利用分治思想，类似快排，随机选择第k小值的候选值，将数组进行分割，A[1-m]小于等于k，A[(m+1)-n]大于k，然后根据两部分数组的大小，继续在相应的部分里继续寻找
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 伪代码
    RAND-SELECT(A, l, u, k) ⊳ k th smallest of A[l .. u] 
      if  l = u  then return A[l]      // 若数组大小为1
      p ← RAND-PARTITION(A, l, u)      // 划分两个区域
      i ← p – l + 1 ⊳ k = rank(A[p])   // 求第一个区域的最后一个元素下标
      if  i = k  then return A[p]      // 比较，返回或递归
      if  i < k  
          then return RAND-SELECT(A, p+1, u, k-i )
      else return RAND-SELECT(A, l, p-1, k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int random_partition(int a[], int l, int u)
{
    swap(a, l, randint(l, u));
    int i = l;
    int j = u+1;
    int t = a[l];
    while (1) {
        do {
            i++;
        } while (a[i] < t && i <= u);
        do {
            j--;
        } while (a[j] > t);
        if (i > j) break;
        swap(a, i, j);
    }
    swap(a, l, j);
    return j;
}
 
int random_select(int a[], int l, int u, int k) 
{
    assert(l <= u && k>=1 && k <= u-l+1); //确保选择的第k小的数范围不超过数组大小
    if (l == u) return a[l];   //如果只有1个元素，可以直接返回
    int p = random_partition(a, l, u); //划分
    int i = p - l + 1;
    if (i == k)  //左边数目等于k，返回a[p]
        return a[p];
    else if (i < k) //左边数目小于k，从右边选择k-i小的元素
        return random_select(a, p+1, u, k-i);
    else  //左边数目大于k，从左边选择第k小的元素
        return random_select(a, l, p-1, k);
}

一些概念的区别

动态规划

一个问题必须拥有重叠子问题和最优子问题，才能使用动态规划去解决

分治和动态规划

相同点：分治和动态规划都是将问题分解为子问题，然后合并子问题得到原问题的解

不同点：分治法分解出的子问题是不重叠的；而动态规划解决的问题拥有重叠子问题。另外，分治法解决的问题不一定是最优化问题，但动态规划解决的问题一定是最优化问题

贪心和动态规划

相同点：两者都要求原问题必须拥有最优子结构。

不同点：

贪心采用的方法类似于动态规划中”自顶向下“的求解，但它不等待子问题求解完毕再选择使用哪一个求解，而是通过一种策略直接选择一个子问题进行求解。也就是说，他只是根据某策略在上一步基础上继续选择。动态规划会考虑所有的子问题，并选择继承能得到最有结果的那个，对暂时没有继承的子问题，由于重叠子问题的存在，后期可能会再次考虑他们，因此还有机会成为全局最优的一部分。