算法导论 第一部分：基础知识

循环不变式

插入排序

按照升序排序。将 arr[j] 视作待比较量，设左边的数组都已经排好序了，若 arr[j-1] 比 arr[j] 还大，那么加上 arr[j] 的数组也是排好序的，若 arr[j-1]比 arr[j] 还要小，那么我们先拿 key储存原来的 arr[j] 再将原来的 arr[j-1]向右移动一位，继续去比较 key 与 arr[j-2] 的大小，直到 key 比某个元素大，那么我们就将原来的元素放到了合适的位置。

template<typename T>void InsertionSort(std::vector<T>&arr) {
    size_t len = arr.size();
    for (size_t j = 1; j< len; j++) {
        T key = arr[j];
        __int128_t i = j - 1;
        while(i >= 0 && arr[i] > key ) {
                arr[i+1] = arr[i];
                i--;
        }
        arr[i+1] = key;
    }
}

循环不变式

初始化：循环第一次开始之前，算法为真。
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
终止：在循环终止时，不变式能够帮助我们证明算法是正确的。

下面我们来证明插入排序是正确的：
初始化：第一次迭代之前，arr[j]左侧只有一个元素，是排好序的。
保持：第 次迭代之前，左侧是排好序的，我们第 次迭代，使得 arr[j] 在适当的位置，使得插入后得到更大的左侧数组也是排好序的。
终止：导致算法终止的条件是 取到了 ，此时最后一轮迭代之后，保证了整个数组都是左侧数组，即排好序的数组。

分治法

归并排序

我们先想有两个已排序的数组，我们想要将两个数组合并到一起，使得合并后的数组也是排好序的，那么我们给出代码

void Merge(int a[], int left, int right, int mid) {
    int L_len = mid - left + 1;
    int R_len = right - mid;
    int* L = new int[L_len];
    int* R = new int[R_len];
    for(int i = 0; i < L_len; i++) {
        L[i] = a[left + i];
    }
    for(int i = 0; i < R_len; i++) {
        R[i] = a[right - R_len + i + 1];
    }
    int j=0,k=0;
    for(int i = left; i <= right; i++) {
        if(j >= L_len) {
            a[i] = R[k];
            k++;
        }
        else if(k >= R_len) {
            a[i] = L[j];
            j++;
        }
        else if (L[j] <= R[k]) {
            a[i] = L[j];
            j++;
        }
        else {
            a[i] = R[k];
            k++;
        }
    }
    delete[] L;
    delete[] R;
}

将左右两个数组分别写入 和 数组中，挨个比较从而合并。注意其中一个数组用完的情况。
我们可以看出，如果把数组分为一个，而合并的时候是两个元素相互比较，可以得出归并排序的代码

void MergeSort(int a[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        MergeSort(a, left, mid);
        MergeSort(a, mid+1, right);
        Merge(a, left, right, mid);
    }
}

---

分析分治算法

递归式

将一个问题分解为 个规模为 的子问题，则每个子问题需要 的时间来求解，总共需要 的时间来求解所有的子问题，若分解问题的时间为 ，合并问题的时间为 ，则我们可以得到递归式

下面我们使用递归式来分析归并排序，递归式为：

它的解是

函数的增长

渐进记号

• 记号：渐进紧确界
• 记号：渐进上界
• 记号：渐进下界
• 记号：非渐进紧确的上界
• 记号：非渐进紧确的下界

分治策略

在分治策略中，我们将一个大的问题先分解成小规模的子问题，再解决这些子问题，最后将子问题的解合并成原问题的解。子问题足够大时需要递归求解，我们称之为递归情况（recursive case）。当子问题足够小，已经不需要递归求解，说明递归已经触底，称为基本情况（base case）。
求解递归式可以有：代入法（猜测一个界然后代入验证）、递归树、主方法。

最大子数组问题

给定一个数组，找出它的和最大的连续的非空子数组。
考虑用分治策略：最大子数组要么在原数组中点两边，要么跨越了中点。
对于跨越中点的子数组，我们只需从中点开始分别向两边加和直到和达到最大。对于两边的子数组，只需不断分割直到只有一个元素。

struct SubArray{
    int left;
    int right;
    int sum;
};
SubArray FindCrossingMaxArray(int a[], int low, int mid, int high) {
    int left_sum = INT_MIN, right_sum = INT_MIN;
    int sum = 0;
    int max_left,max_right;
    for (int i = mid; i >= low; i--) {
        sum = sum + a[i];
        if (sum > left_sum) {
            left_sum = sum;
            max_left = i;
        }
    }
    sum = 0;
    for (int i = mid + 1; i <= high; i++) {
        sum = sum + a[i];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = i;
        }
    }
    SubArray res {max_left, max_right, left_sum+right_sum};
    return res;
}
SubArray FindMaxSubArray(int a[], int low, int high) {
    if (high == low) {
        SubArray res {low,high,a[low]};
        return res;
    }
    else {
        int mid = (high + low) / 2;
        SubArray left_arr = FindMaxSubArray(a, low, mid);
        SubArray right_arr = FindMaxSubArray(a, mid + 1, high);
        SubArray mid_arr = FindCrossingMaxArray(a, low, mid, high);
        if (left_arr.sum > right_arr.sum && left_arr.sum > mid_arr.sum) return left_arr;
        else if (right_arr.sum > left_arr.sum && right_arr.sum > mid_arr.sum) return right_arr;
        else return mid_arr;
    }
}

它的时间复杂度也是
值得注意的是，最大子数组问题还有一个更快的算法。有时分治并不是最快的方法。

矩阵乘法的 Strassen 算法

普通乘法

普通的 矩阵乘法定义是

代码实现为

template<int N>
void multiply(const int (&A)[N][N], const int (&B)[N][N], int (&C)[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            C[i][j] = 0;
            for (int k = 0; k < N; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

它的时间复杂度为

递归算法

下面介绍一个运行时间在 的递归算法
我们先假设 是2的次幂。设 、 和 是三个矩阵，将它们分块，有

可以写为

基本情况是 时，乘积就是元素本身

Strassen 方法

具体步骤为：

1. 将矩阵分为 的子矩阵
2. 创建如下 个矩阵：

3. 递归地计算 次 矩阵乘法如下：

4. 对上一步的 矩阵进行加减计算，得出

5. 合并 子矩阵就得到乘积结果
   给出代码

using ll = long long;
using Matrix = vector<vector<ll>>;

// 普通 O(n^3) 乘法：用于小规模/递归终止
static Matrix multiply_plain(const Matrix& A, const Matrix& B) {
    ll n = (int)A.size();
    Matrix C(n, vector<ll>(n, 0));
    for (ll i = 0; i < n; ++i) {
        for (ll k = 0; k < n; ++k) {
            ll aik = A[i][k];
            for (ll j = 0; j < n; ++j) {
                C[i][j] += aik * B[k][j];
            }
        }
    }
    return C;
}

static Matrix add(const Matrix& A, const Matrix& B) {
    int n = (int)A.size();
    Matrix C(n, vector<ll>(n, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            C[i][j] = A[i][j] + B[i][j];
    return C;
}

static Matrix sub(const Matrix& A, const Matrix& B) {
    int n = (int)A.size();
    Matrix C(n, vector<ll>(n, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            C[i][j] = A[i][j] - B[i][j];
    return C;
}

// 拆分成四块：A11, A12, A21, A22
static void split(const Matrix& A, Matrix& A11, Matrix& A12, Matrix& A21, Matrix& A22) {
    int n = (int)A.size();
    int m = n / 2;
    A11.assign(m, vector<ll>(m));
    A12.assign(m, vector<ll>(m));
    A21.assign(m, vector<ll>(m));
    A22.assign(m, vector<ll>(m));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            A11[i][j] = A[i][j];
            A12[i][j] = A[i][j + m];
            A21[i][j] = A[i + m][j];
            A22[i][j] = A[i + m][j + m];
        }
    }
}

// 合并四块回一个矩阵
static Matrix join(const Matrix& C11, const Matrix& C12, const Matrix& C21, const Matrix& C22) {
    int m = (int)C11.size();
    int n = m * 2;
    Matrix C(n, vector<ll>(n, 0));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            C[i][j] = C11[i][j];
            C[i][j + m] = C12[i][j];
            C[i + m][j] = C21[i][j];
            C[i + m][j + m] = C22[i][j];
        }
    }
    return C;
}

// 计算 >=n 的最小 2 的幂
static int next_pow2(int n) {
    int p = 1;
    while (p < n) p <<= 1;
    return p;
}

// 将矩阵 padding 到 size x size
static Matrix pad(const Matrix& A, int size) {
    int n = (int)A.size();
    Matrix P(size, vector<ll>(size, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            P[i][j] = A[i][j];
    return P;
}

// 裁剪回 n x n
static Matrix unpad(const Matrix& A, int n) {
    Matrix R(n, vector<ll>(n, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            R[i][j] = A[i][j];
    return R;
}

// Strassen 递归
static Matrix strassen_rec(const Matrix& A, const Matrix& B, int threshold) {
    int n = (int)A.size();
    if (n <= threshold) return multiply_plain(A, B);
    if (n == 1) {
        Matrix C(1, vector<ll>(1, A[0][0] * B[0][0]));
        return C;
    }

    Matrix A11, A12, A21, A22;
    Matrix B11, B12, B21, B22;
    split(A, A11, A12, A21, A22);
    split(B, B11, B12, B21, B22);

    // Strassen 7 个乘法
    // M1 = (A11 + A22) * (B11 + B22)
    Matrix M1 = strassen_rec(add(A11, A22), add(B11, B22), threshold);
    // M2 = (A21 + A22) * B11
    Matrix M2 = strassen_rec(add(A21, A22), B11, threshold);
    // M3 = A11 * (B12 - B22)
    Matrix M3 = strassen_rec(A11, sub(B12, B22), threshold);
    // M4 = A22 * (B21 - B11)
    Matrix M4 = strassen_rec(A22, sub(B21, B11), threshold);
    // M5 = (A11 + A12) * B22
    Matrix M5 = strassen_rec(add(A11, A12), B22, threshold);
    // M6 = (A21 - A11) * (B11 + B12)
    Matrix M6 = strassen_rec(sub(A21, A11), add(B11, B12), threshold);
    // M7 = (A12 - A22) * (B21 + B22)
    Matrix M7 = strassen_rec(sub(A12, A22), add(B21, B22), threshold);

    // 组合结果块
    // C11 = M1 + M4 - M5 + M7
    Matrix C11 = add(sub(add(M1, M4), M5), M7);
    // C12 = M3 + M5
    Matrix C12 = add(M3, M5);
    // C21 = M2 + M4
    Matrix C21 = add(M2, M4);
    // C22 = M1 - M2 + M3 + M6
    Matrix C22 = add(add(sub(M1, M2), M3), M6);

    return join(C11, C12, C21, C22);
}

// 外部接口：支持任意 n，自动 padding
Matrix strassen_multiply(const Matrix& A, const Matrix& B, int threshold = 64) {
    int n = (int)A.size();
    if (n == 0 || (int)B.size() != n) throw runtime_error("Size mismatch");
    for (int i = 0; i < n; ++i) {
        if ((int)A[i].size() != n || (int)B[i].size() != n) throw runtime_error("Not square");
    }

    int m = next_pow2(n);
    Matrix Ap = (m == n) ? A : pad(A, m);
    Matrix Bp = (m == n) ? B : pad(B, m);

    Matrix Cp = strassen_rec(Ap, Bp, threshold);
    return (m == n) ? Cp : unpad(Cp, n);
}

该算法的运行时间是

主定理

令 和 是常数， 是一个函数， 是定义在非负整数上的递归式：

将 看作 或 ，那么 有如下渐进界：

1. 若对某个常数 有 ，则
2. 若 ，则
3. 若对某个常数 有 ，且对于某个常数 和所有足够大的 有 ，则
   例 Strassen 方法的递归式为

在这里 ，，注意到当令 时有 ，符合情况，解为

概率分析和随机算法

随机算法

如果一个算法的行为不仅由输入决定，而且也由随机数生成器产生的数值决定，则称这个算法是随机的（randomized）。我们将一个随机算法的运行时间成为期望运行时间。一般而言，当概率分布是在算法输入上时，我们讨论的是平均情况运行时间，当算法本身做出随机选择时，我们讨论其期望运行时间。

雇佣问题

void hire_assistant(int candidcate_quality[], int size){
    int best = 0;
    for (int i = 0; i < size; i++) {
	    interview(i);
        if (candidcate_quality[i] > candidcate_quality[best]) {
            best = i;
            hire(best);
        }
    }
}

指示器随机变量分析雇佣问题

我们假设应聘者以随机的顺序出现，每次应聘，第 个应聘者被雇佣的概率是 ，所以第 个应聘者被雇佣的期望是 ，总期望为

随机算法

在上个问题，我们可以先对输入的数据进行随机排列，注意随机化的过程是发生在算法里面的，此时这个算法是一个随机算法，其表现与输入的顺序无关了。

随机排列数组

我们讨论两种随机化方法，一种是按照随机生成的优先级数组 来排序，随机化原数组，另外一种是将 与 交换，时间是 的。
一个具有 个元素的k排列是包含这 个元素中的 个元素的序列，并且不重复，一共有 种可能的 排列。
可以用循环不定式证明可以得到一个均匀随机排列。