算法设计与分析-第二章

二分检索（分治法）

矩阵乘法（分治法）

第 K 小元素（分治法）

二分检索（分治法）

题目大意

给定一个大小为 \(n\) 的递增整数序列 \(L\)，使用二分查找法查找任意元素 \(x\) 在序列中的位置 \(k\) （即序列中的第几个元素），若元素不存在则返回 -1。要求编写程序实现二分查找算法，并对其时间复杂度和空间复杂度进行分析，同时通过实验评估算法性能。

解法描述

1. 算法思想

   二分查找算法基于分治思想，适用于有序数组。其核心是将待查找区间不断二分，通过比较中间元素与目标元素的大小关系，确定目标元素可能存在的新区间，逐步缩小查找范围，直到找到目标元素或确定其不存在。

2. 实现方式

   程序中，先接收输入的序列大小 \(n\)、序列 \(L\) 以及要查找的元素 \(x\)。初始化左右指针 left = -1 和 right = n，在 left < right 的循环中，计算中间元素下标 mid = (left + right) / 2。若 a[mid] >= x，说明目标元素可能在左半部分，更新 right = mid；若 a[mid] < x，则目标元素在右半部分，更新 left = mid + 1。循环结束后，判断 a[left] 是否等于目标元素 x，若相等则返回 left，否则返回 -1。

3. 复杂度分析

   • 时间复杂度：每次迭代都将待查找区间减半，假设序列大小为 \(n\)，最多需要进行 \(\log n\) 次迭代就能找到目标元素或确定其不存在，所以时间复杂度为 \(O(\log n)\)。
   • 空间复杂度：算法执行过程中，除输入数据外，仅使用了几个辅助变量（如 left、right、mid），这些变量占用的空间不随输入规模 \(n\) 的变化而变化，因此空间复杂度为 \(O(1)\)。

#include <bits/stdc++.h>
using namespace std;
int n, x;
const int N = 100009;
int a[N];
int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> x;
    int l = -1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    cout << (a[l] == x ? l : -1);

    return 0;
}

矩阵乘法（分治法）

题目大意

给定两个矩阵 \(A\) 和 \(B\)，使用分治法实现矩阵乘法，并与朴素矩阵乘法算法进行比较。要求编写程序实现相关算法，分析算法的正确性、时间复杂度和空间复杂度，并通过实验测试评估算法性能。

解法描述

1. 算法思想

   • 朴素矩阵乘法：根据矩阵乘法定义，结果矩阵 \(C\) 的每个元素 \(C_{ij}\) 是矩阵 \(A\) 的第 \(i\) 行与矩阵 \(B\) 的第 \(j\) 列对应元素乘积之和。通过三重循环遍历实现，时间复杂度较高，为 \(O(n^3)\)。
   • Strassen 分治算法：基于分治策略，将大矩阵乘法问题分解为多个小规模子矩阵乘法问题。把输入矩阵 \(A\) 和 \(B\) 各划分为四个大小相等的子矩阵，通过特定的加减法和 7 次递归的子矩阵乘法，再进行线性组合得到结果矩阵。这种方法减少了乘法次数，理论上时间复杂度为 \(O(n^{2.7})\)。

2. 实现方式

   • 矩阵表示：使用二维向量 vector<vector<int>> 表示矩阵，方便对矩阵元素进行访问和操作。
   • 辅助函数：实现矩阵加法 matrixAdd 和减法 matrixSubtract 函数，用于 Strassen 算法中矩阵的加减运算；实现朴素矩阵乘法 matrixMultiply 函数，通过三重循环计算结果矩阵。
   • Strassen 算法实现：在 strassen 函数中，先处理矩阵规模为 2 的基本情况，直接调用朴素矩阵乘法。对于更大规模矩阵，将其分割为子矩阵，计算中间矩阵\(S_i\) ，递归计算 7 个乘积矩阵 \(M_i\) ，最后通过线性组合得到结果矩阵 \(C\) 的四个子矩阵 \(C_{11}\)、\(C_{12}\)、\(C_{21}\)、\(C_{22}\)，并组合成最终结果矩阵。

3. 复杂度分析

   • 朴素矩阵乘法：
     • 时间复杂度：有三层嵌套循环，每层循环次数都为矩阵大小 \(n\)，所以时间复杂度为 \(O(n^3)\)。
     • 空间复杂度：仅使用一个结果矩阵存储最终乘积，空间复杂度为 \(O(n^2)\)。
   • Strassen 分治算法：
     • 时间复杂度：通过减少乘法次数，理论时间复杂度降为 \(O(n^{2.7})\)，但由于常数项较大，在小规模矩阵时效率可能不如朴素算法。
     • 空间复杂度：与朴素矩阵乘法相同，都需要一个结果矩阵存储最终结果，空间复杂度为 \(O(n^2)\)。

#include <bits/stdc++.h>
using namespace std;
int n, N;
typedef vector<vector<int>> VVI;
typedef vector<int> VI;
////将矩阵扩展为2的倍数
//VVI extendMatrix(const VVI& A) {
//    int originalSize = A.size();
//    int newSize = (originalSize % 2 == 0 ? originalSize : originalSize + 1);
//    VVI extendedMatrix(newSize, VI(newSize, 0));
//
//    for (int i = 0; i < originalSize; ++i)
//        for (int j = 0; j < originalSize; ++j)
//            extendedMatrix[i][j] = A[i][j];
//
//    return extendedMatrix;
//}

//// 截取矩阵大小到原始大小
//vector<vector<int>> truncateMatrix(const vector<vector<int>>& A, int originalSize) {
//    vector<vector<int>> truncatedMatrix(originalSize, vector<int>(originalSize, 0));
//
//    for (int i = 0; i < originalSize; ++i)
//        for (int j = 0; j < originalSize; ++j)
//            truncatedMatrix[i][j] = A[i][j];
//
//    return truncatedMatrix;
//}

//矩阵加法A+B
VVI matrixAdd(const VVI& A, const VVI& B) {
    int n = A.size();
    VVI result(n, VI(n, 0));

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            result[i][j] = A[i][j] + B[i][j];

    return result;
}
//矩阵减法A-B
VVI matrixSubtract( const VVI& A, const VVI& B) {
    int n = A.size();
    VVI result(n, VI(n, 0));

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            result[i][j] = A[i][j] - B[i][j];

    return result;
}
//矩阵乘法
VVI matrixMultiply(const VVI& A, const VVI& B) {
    int n = A.size();
    VVI result(n, VI(n, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            for (int k = 0 ; k < n; k++)
                result[i][j] += A[i][k] * B[k][j];

    return result;
}
// Strassen算法
VVI strassen(VVI A, VVI B) {
    int n = A.size();
    VVI result(n, VI(n, 0));
    if (n == 2) {
        result = matrixMultiply(A, B);
        return result;
    }

    // 将矩阵分割成四个子矩阵
    int newSize = n / 2;

    VVI A11(newSize, VI(newSize, 0));
    VVI A12(newSize, VI(newSize, 0));
    VVI A21(newSize, VI(newSize, 0));
    VVI A22(newSize, VI(newSize, 0));

    VVI B11(newSize, VI(newSize, 0));
    VVI B12(newSize, VI(newSize, 0));
    VVI B21(newSize, VI(newSize, 0));
    VVI B22(newSize, VI(newSize, 0));

    // 将原始矩阵拆分成四个子矩阵
    for (int i = 0; i < newSize; ++i) {
        for (int j = 0; j < newSize; ++j) {
            A11[i][j] = A[i][j];
            A12[i][j] = A[i][j + newSize];
            A21[i][j] = A[i + newSize][j];
            A22[i][j] = A[i + newSize][j + newSize];

            B11[i][j] = B[i][j];
            B12[i][j] = B[i][j + newSize];
            B21[i][j] = B[i + newSize][j];
            B22[i][j] = B[i + newSize][j + newSize];
        }
    }

    VVI S1(newSize, VI(newSize, 0));
    VVI S2(newSize, VI(newSize, 0));
    VVI S3(newSize, VI(newSize, 0));
    VVI S4(newSize, VI(newSize, 0));
    VVI S5(newSize, VI(newSize, 0));
    VVI S6(newSize, VI(newSize, 0));
    VVI S7(newSize, VI(newSize, 0));
    VVI S8(newSize, VI(newSize, 0));
    VVI S9(newSize, VI(newSize, 0));
    VVI S10(newSize, VI(newSize, 0));

    //用加减法计算这10个过程矩阵

    S1 = matrixSubtract(A12, A22);
    S2 = matrixAdd( B21, B22);
    S3 = matrixAdd( A11, A22);
    S4 = matrixAdd(B11, B22);
    S5 = matrixSubtract( A11, A21);
    S6 = matrixAdd( B11, B12);
    S7 = matrixAdd(A11, A12);
    S8 = matrixSubtract( B12, B22);
    S9 = matrixSubtract( B21, B11);
    S10 = matrixAdd(A21, A22);

    //计算7次乘法

    VVI M1 = strassen(S1, S2);
    VVI M2 = strassen(S3, S4);
    VVI M3 = strassen(S5, S6);
    VVI M4 = strassen(S7, B22);
    VVI M5 = strassen(A11, S8);
    VVI M6 = strassen(A22, S9);
    VVI M7 = strassen(S10, B11);

    //线性组合乘积矩阵
    VVI C11 = matrixAdd(M1, M2);
    C11 = matrixSubtract(C11, M4);
    C11 = matrixAdd(C11, M6);

    VVI C12 = matrixAdd(M4, M5);
    VVI C21 = matrixAdd(M6, M7);

    VVI C22 = matrixSubtract(M2, M3);
    C22 = matrixAdd(C22, M5);
    C22 = matrixSubtract(C22, M7);


    // 构建结果矩阵


    for (int i = 0; i < newSize; ++i) {
        for (int j = 0; j < newSize; ++j) {
            result[i][j] = C11[i][j];
            result[i][j + newSize] = C12[i][j];
            result[i + newSize][j] = C21[i][j];
            result[i + newSize][j + newSize] = C22[i][j];
        }
    }

    return result;
}

int pow_2(int n) {
    if ((n & (n - 1)) == 0) return n;//等于零说明只有一个1，即最高位为1
    else {
        while ((n & (n - 1)) != 0) {
            n = n & (n - 1);
        }
        return n << 1;
    }
}

int main() {
    cin >> n;
    //将n转化2的倍数
    if (n <= 2) {
        N = 2;
    } else {
        N = pow_2(n);
    }

    // 随机生成1000阶方阵 a 和 b
    VVI a(N, VI(N)), b(N, VI(N)), c(N, VI(N)), result(N, VI(N));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            a[i][j] = rand() % 100; // 生成范围为 0 到 99 的随机数
            b[i][j] = rand() % 100;
//            if (i == N || j == N) a[i][j] = b[i][j] = 0;//补零
        }
    }


//    //初始化二维向量
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
//            cin >> a[i][j];
//        }
//    }
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
//            cin >> b[i][j];
//        }
//    }

//    cout << n << endl;
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
//            cout << a[i][j] << " ";
//        }
//        puts("");
//    }
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
//            cout << b[i][j] << " ";
//        }
//        puts("");
//    }

    clock_t start_t = clock();
    //朴素乘法，时间复杂度为O(n^3)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
//    puts("");

//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
//            cout << c[i][j] << " ";
//        }
//    }

    /**
     Strassen算法：
      对任意两个2*n阶的矩阵a和b相乘（不足偶数阶的矩阵可以补零扩展），可以将它们各划分为4个小矩阵
      然后将这8个矩阵使用特定的算法求7次乘积，最后将7个临时矩阵M通过加减组合得到最后的第8个结果矩阵
      再将这8个结果矩阵组合为目标矩阵c。
      优点：只有7次乘法，时间复杂度降低为O(n^2.7)
    */
    clock_t tmp_t = clock();
    result = strassen(a, b);
    clock_t end_t = clock();
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
////            if (i > n - 1 || j > n - 1) continue;
//            cout << result[i][j] << " ";
//        }
//    }
//    puts("");
    double time1 = (double)(tmp_t - start_t) / CLOCKS_PER_SEC * 1000;
    double time2 = (double)(end_t - tmp_t) / CLOCKS_PER_SEC * 1000;
    cout << "朴素解法耗时为" << (time1) << "ms\n";
    cout << "strassen分治法耗时为" << (time2) << "ms";
    return 0;
}
/*
5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/

第 K 小元素（分治法）

题目大意

给定一个长度为 \(n\) 的整数序列，找出其中第 \(k\) 小的元素。要求运用分治法思想，编写程序实现该功能，并对算法的正确性、时间复杂度和空间复杂度进行分析，通过实验测试验证算法。

解法描述

1. 算法思想

   借鉴快速排序的分区思想，将序列划分为两部分。通过不断递归，在合适的子序列中查找第 \(k\) 小的元素。对于长度较小（小于等于 5）的子序列，直接排序后获取第 \(k\) 小元素；对于长度大于 5 的子序列，先划分为多个大小为 5 的子序列，找到这些子序列中位数的中位数作为分界点，根据分界点与\(k\)的关系，确定下一步搜索的子序列。

2. 实现方式

   程序中，paration 函数实现类似快速排序的分区操作，以给定元素 k（这里是中位数）为基准，将数组分为两部分，使得左边元素小于 k，右边元素大于 k，并返回分界点位置。select 函数用于递归查找第\(k\)小的元素，当子序列长度小于等于 5 时，直接排序返回第\(k\)小元素；否则，将子序列划分为大小为 5 的子序列，排序后将中位数置于数组前部分，递归找到中位数的中位数 x，以 x为基准分区，根据 k 与分区点位置的关系，在左半部分或右半部分继续递归查找。

3. 复杂度分析

   • 时间复杂度：每次递归都能将搜索范围缩小，虽然每次递归处理的子序列规模不同，但总体上递归深度不超过 \(\log n\)，且每次分区操作时间复杂度为线性 \(O(n)\)，所以算法时间复杂度为 \(O(n)\)。
   • 空间复杂度：主要取决于递归调用栈的深度，由于每次递归序列规模减半，递归栈深度为 \(O(\log n)\)，且没有使用其他额外数据结构，所以空间复杂度为 \(O(\log n)\)。

#include <iostream>
#include <algorithm>

using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e7 + 10;
int n, a[N], pos, k;
int paration(int a[], int l, int r, int k) { //快排
    for (int i = l; i <= r; i++)
        if (a[i] == k) {//k是中位数
            swap(a[i], a[l]);//把这个数放到最左端
            break;
        }
    int i = l, j = r + 1;//中位数作为基准，不用排
    while (i < j) {
        do i++;
        while (a[i] < k);
        do j--;
        while (a[j] > k);
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[l], a[j]);//把中位数放回去，此时j的左边都比a[j]即k要小
    return j;
}
int select(int a[], int l, int r, int k) {
    //在数组a[l...r]中选择第k小的元素返回
    if (r - l < 5) {
        sort(a + l, a + r + 1);
        return a[l + k - 1];
    }
    int pos = (r - l + 1) / 5;
    //每组排序后，将中位数序列置于整个数组的前部分
    for (int i = 0; i < pos; i++) {//选取每段的中位数
        int s = l + 5 * i;
        int t = s + 4;
        sort(a + s, a + t + 1);
        swap(a[l + i], a[s + 2]);//将第i组的中位数放置在原数组的第(l + i)位置
    }
    // for(int i = l;i <= pos;i++) printf("%d ", a[i]);
    //选取中位数序列的中位数
    int x = select(a, l, l + pos - 1, (pos + 1) / 2);//这个select一定进入if判断
    int i = paration(a, l, r, x);//x就是中位数的中位数，排列完后可以保证i的左右两侧的元素个数相对一致
    int j = i - l + 1;//计算此时区间长度
    if (k == j) return a[i];//因为在if中已经sort了，所以直接就是有序的
    if (k < j) return select(a, l, i, k);//对左段排序
    else return select(a, i + 1, r, k - j);//对右段排序
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    printf("%d", select(a, 1, n, k));
    return 0;
}