算法分析与设计

第一章

1. 最大公约数算法：
   • gcd(m, n) = gcd(n, m mod n)
   • 结束条件是 m%n = 0

第二章

1. 算法时间效率度量 —— 基本操作的执行次数。
2. 渐进符号（可以按照复杂程度记忆，最简单的为上界，最复杂的为下界）
   
3. 斐波那契数列
   
   • 参数 α，β 可以通过 F(1)、F(2)联立方程组解出来

第三章

1. 选择排序
   

2. 冒泡排序
   

3. 幻方
   
   

第四章

1. 分治法
   

2. 合并排序
   
   
   
   
   

3. 快速排序
   
   
   
   
   

   #include
   using namespace std;
   int a[5], n;
   void quickSort(int left, int right){
       if (left >= right)
           return;
       int i, j, t, temp;
       i = left;
       j = right;
       temp = a[left];
       while (true){
           while (a[j] >= temp && i < j){
               j--;
           }
           while (a[i] <= temp="" &&="" i="" <="" j){="" i++;="" }="" if="" (i="" t="a[i];" a[i]="a[j];" a[j]="t;" else="" break;="" a[left]="a[j];" quicksort(left,="" -="" 1);="" quicksort(i="" +="" 1,="" right);="" int="" main()="" {="" for="" (int="" i++){="" cin="">> a[i];
       }
       quickSort(1, n);
       for (int i = 1; i <= 5;="" i++){="" cout="" <<="" a[i]="" "="" ";="" }="" endl;="" return="" 0;="" 

4. 大整数乘法
   
   

5. Strassen 矩阵乘法
   
   

第五章

1. 减治算法
   
   
   

第六章

1. 平衡二叉树

   这里的 LR 旋转是相对的概念, 意思是先变成左子树再向右旋转。

   

2. 2-3 树

   2-3 树是一种特殊的高度平衡树，允许结点最多包含两个关键字。
   ❑ 2-node:包含一个关键字，两个子节点
   ❑ 3-node:包含两个关键字，三个子节点

   

3. Horner 法则
   
   
   
   

第七章

1. 计数排序
   
   

2. 分布计数排序
   
   

   实现代码：

    #include
    using namespace std;
    int a[10], l, u, D[10], S[10];
   
    void DistributeSort(){
        for (int i = 0; i <= u="" -="" l;="" i++){="" d[i]="0;" }="" for="" (int="" i="0;" <="" 10;="" d[a[i]="" l]++;="" +="D[i" 1];="">= 0; i--){
            int j = a[i] - l;
            S[D[j] - 1] = a[i];
            D[j] -= 1;
        }
        for (int i = 0; i < 10; i++){
            cout << S[i] << " ";
        }
    }
    int main()
    {
        l = 1, u = 3;
        for (int i = 0; i < 10; i++){
            cin >> a[i]; // 1 2 3 1 2 3 1 2 3 1
        }
        DistributeSort();
        return 0;
    }