《算法导论》读书笔记

发布于 2020-02-20  665 次阅读


导师布置的任务,只能咬牙看完了

由于时间比较紧,有可能会漏掉书中一些较难的算法,十分抱歉QAQ。   

由C++实现的书中伪代码会同步至github代码仓库。传送门

第一部分:基础知识

第二章:算法基础

2.1插入排序 code

时间复杂度:O(n^2)

空间复杂度:O(n)

其思想是对于前k个数字都有序的情况下,只需要从后往前找到合适的位置,将第k+1位插入,便可以使前k+1位有序,从而实现了状态转移。由于使用了大量的赋值和比较操作

特别是插入操作中要将数组整体向后移一位,该算法的效率不高。也许可以使用二分法将查找的操作降到O(logn)。

vector<int> date;
void insert_sort()
{
    for (int i = 1; i < date.size(); i++)
    {
        int k = date[i];
        int j = i - 1;
        while (j >= 0 && date[j] > k)
        {
            date[j + 1] = date[j];
            j--;
        }
        date[j + 1] = k;
    }
    return;
}

测试题目 :luogu 【模板】快速排序

2.3.1归并排序 传送门

时间复杂度(nlogn)

空间复杂服(2n)(归并时要开辟临时数组)

其思想是将整个数组二分(对半划分)从而将问题的规模减小,由于是二分所以其递归深度不会超过logn 对于每层递归要处理n次所以此算法的效率较高(仅次于快排)而且稳定,其精妙之处在于对于两个已经排好的序列,只需将其头部的数字依次插入数组,就可以将两者合并为一个大的有效序列。

vector<int> date;
void merge(int left, int mid, int right)
{
    int l1 = mid - left + 1;
    int l2 = right - mid;
    vector<int> l, r;
    for (int i = 1; i <= l1; i++)
        l.push_back(date[left + i - 1]);
    for (int i = 1; i <= l2; i++)
        r.push_back(date[mid + i]);
    l.push_back(inf);
    r.push_back(inf);
    int i = 0;
    int j = 0;
    for (int k = left; k <= right; k++)
    {
        if (l[i] <= r[j])
        {
            date[k] = l[i];
            i++;
        }
        else
        {
            date[k] = r[j];
            j++;
        }
    }
    return;
}
void merge_sort(int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) >> 1;
        merge_sort(left, mid);
        merge_sort(mid + 1, right);
        merge(left, mid, right);
    }
}

测试题目 :luogu 【模板】快速排序

第四章:分治策略

4.1最大子数组问题(最大子段和)code

求一个数组中的其中元素和最大的子数组,一般我们会用动态规划来求解此类问题

但是书中给出了分治的解法,对于一个数组,其最大子段和就是其左边数组、右边数组和跨中线的数组的最大字段和,完全可以依照类似于归并排序的做法,先递归求解左右两个子问题,在合并处理。

时间复杂度O(nlogn)

空间复杂度O(n)

vector<int> date;
int find_cross_subarry(int left, int mid, int right)
{
    int left_max = -inf;
    int sum = 0;
    for (int i = mid; i >= left; i--)
    {
        sum += date[i];
        left_max = max(left_max, sum);
    }
    int right_max = -inf;
    sum = 0;
    for (int i = mid + 1; i <= right; i++)
    {
        sum += date[i];
        right_max = max(right_max, sum);
    }
    return max(right_max, max(left_max, left_max + right_max));
}
int find_subarry(int left, int right)
{
    if (left == right)
    {
        return date[left];
    }
    int mid = (left + right) >> 1;
    int ans = find_subarry(left, mid);
    ans = max(ans, find_subarry(mid + 1, right));
    ans = max(ans, find_cross_subarry(left, mid, right));
    return ans;
}

测试题目 luogu P1115 最大子段和

4.1矩阵乘法的Strassen算法

对于这部分内容,我想结合普通矩阵的乘法。

普通的矩阵乘法一般是使用三个for循环来枚举和行和和列和并将其相乘,然后赋值到输出矩阵的对应位置。(下面是自己用的矩阵结构体)

int n;
struct node
{
   // int n;
    int date[100][100];
    node operator*(node a){
        node x;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            int ans=0;
            for(int k=0;k<n;k++){
                ans=ans+date[i][k]*a.date[k][j];
                ans%=mod;
            }
            x.date[i][j]=ans;
        }
        return x;
    }
    node operator=(node a){
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        date[i][j]=a.date[i][j];
        return *this;
    }
}cst;

测试题目:hdoj 1575 Tr A 一道矩阵快速幂板子

由于数据较小,程序运行还是比较快的,但是还能不能更快呢? Strassen算法 用了分治的思想,先把每个矩阵分割为4份,然后创建如下10个中间矩阵:

S1 = B12 - B22
S2 = A11 + A12
S3 = A21 + A22
S4 = B21 - B11
S5 = A11 + A22
S6 = B11 + B22
S7 = A12 - A22
S8 = B21 + B22
S9 = A11 - A21
S10 = B11 + B12

接着,计算7次矩阵乘法:

P1 = A11 • S1
P2 = S2 • B22
P3 = S3 • B11
P4 = A22 • S4
P5 = S5 • S6
P6 = S7 • S8
P7 = S9 • S10

最后,根据这7个结果就可以计算出C矩阵:
C11 = P5 + P4 - P2 + P6
C12 = P1 + P2
C21 = P3 + P4
C22 = P5 + P1 - P3 - P7

最后合并即可得到结果

由于博客长度太大,可能会导致数据库崩溃,现在将此笔记分开。

第二部分:传送门

第三部分:传送门

第四部分:传送门

第六部分:传送门

后续会继续更新-----------------------------------


💭💭💭💭💭💭