数据结构学习笔记——第一章：绪论（上）

一、目标：计算

整个计算机科学的目的，都是为了实现高效和低耗的计算。为了理解什么是计算，我们首先来看几个实例。

Fig. 1 实例：绳索计算

Fig. 2 实例：尺规计算机

1.1 定义算法

计算，就是借助某种工具，遵照一定规则，以明确而机械的形式进行。计算模型（计算机）就是计算中使用的工具。
算法，即在特定计算模型下，旨在解决特定问题的指令序列。

特点：

①输入、输出明确
②正确性（可解决问题）
③确定性（任意算法都可描述为一个由基本操作注组成的序列）
④可行性（每一基本操作都可实现）
⑤有穷性（对于任何输入，经过有穷次计算后终止）

如何理解”有穷性“？

Fig. 3 Hailstone序列

例子:
$Hailstone(42) = \{42, 21, 64, 32, ..., 1 \rbrace$
Hailstone序列一定会呈现出整体下降的趋势，尽管中间可能会飘忽不定。

#include<iostream>

int len_hailstone(int n){
    int length = 0;
    std::cout<<n<<", ";
    while(n>1){(n%2) ? n=n*3+1 : n/=2;std::cout<<n<<", "; length++;}
    std::cout<<std::endl;
    return length;
}

int main(int argc, char* argv[]){
    auto n = atoi(argv[1]);
    std::cout<<"length of hailstone("<<n<<"): "<<len_hailstone(n)<<std::endl;
    return 0;
}

➜  Chapter1 ./hailstone 27     
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 
length of hailstone{27}: 111

问题：对于任意n，序列的长度是否是有穷的？
答案：不确定。这个序列的长度未必是有限的。因此上面的程序未必可以称为一个“算法”。

什么是好算法
对算法来说最重要的特征：效率
$Algorithms + Data Structures (DSA) = Programs$

1.2 计算模型

如何评价不同DSA的效率: 度量。 ( If you cannot measure it, you can not improve it. )

测度：

Fig. 5 用某个实例的计算成本来评价DSA的效率是不现实的
分析：问题实例的规模，往往是决定计算成本的主要因素（正相关）
最坏情况分析原则：对于规模为n的所有实例中，只关注最坏（成本最高）者

1.2.1 图灵机模型

Fig. 6 图灵机概念

实例：通过图灵机完成非负整数加一的功能。

Fig. 7

1.2.2 RAM模型

Fig. 8. RAM模型及其指令集

重点：这些模型将算法的运行时间转换为基本操作的次数来评价，从而将DSA的评价和单次实验的各种环境因素分离开。具体来说，每个算法的流程应该是清晰、可罗列，且没有歧义的。这就为评价算法提供了基础。

二、复杂度分析

2.1 大 $O$ 记号

大 $O$ 记号可以看做评价DSA的一把直尺，其刻度并不精细，而是主要用于评价DSA的“潜力”，比如它在求解大规模问题时的性能。更确切的说，大 $O$ 记号关注的是随着n的增长(n>>2)，算法成本的增长趋势。

Fig. 9. 大O记号

大 $O$ 记号的处理手法:

常系数可忽略
低次项可忽略

2.1.1 常数复杂度 $O(1)$

$2 = 2013 = 2013^{2013} = O(1)$ 。这类算法的效率最高。

2.1.2 对数复杂度 $O(log^n)$

常底数和常数次幂无所谓：
① $log_a^n = log_a^b * log_b^n = O(log^n)$
② ${logn}^c = c*log^n = O(log^n)$

这类算法无限接近于 $O(1 )$ ，非常令人满意。

2.1.3 多项式复杂度 $O(n^c)$

多项式的最高此项即为复杂度 $O(n^k)$

线性复杂度: $O(n)$ ：代表线性函数。很多编程题复杂度都介乎 $O(n)-O(n^2)$ 。

2.1.4 指数复杂度 $O(2^n)$

这类算法的计算成本增长的极快，通常认为是不可忍受的。
$对任意c > 1, n^c = O(2^n)$ $//证明: e^n = 1 + n + n^2/2! + n^3/3!$
$n^{1000}=O(1.0000001^n) = O(2^n)$

Fig. 10. 从多项式复杂度到指数复杂度

2.2 实例: Subset

Fig. 11 实例：Subset问题

这个问题如果没有其他约束条件，最优的算法就是逐一枚举所有可能的子集，再统计其中元素的和。其复杂度为 $2^n$
Subset问题是一个NP-complete问题。

三、算法分析

两个主要任务: 正确性 + 复杂度。

Fig. 12 算法分析：前提与方法

3.1 级数

算数级数: $T(n) = 1 + 2 + ... + n = O(n^2)$
幂方级数: $1^k + 2^k + 3^k + ... + n^k = O(n^{k+1})$ # 比幂次高一级
几何级数: $a^0 + a^1 + a^2 + ... + a^n = O(a^n)$
常用: $2^0 + 2^1 + 2^2 + ... + 2^n = O(2a^n)$
收敛级数
其他常见级数:
①调和级数 $h(n) = 1 + 1/2 + ... + 1/n = O(logn)$
②对数级数: $log 1 + log2 + ... + logn = O(nlogn)$

3.1 循环 vs. 级数

二重循环：
①两个控制变量之间没有耦合: 复杂度为 $O(n^2)$

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        O(1)_Operation(i, j)

②两个控制变量之间存在耦合: 复杂度也是 $O(n^2)$

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        O(1)_Operation(i, j)

Fig. 13 二重循环复杂度

③注意下面的循环复杂度为

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j+=j)
        O(1)_Operation(i, j)

3.2 实例：非极端排序

问题：给定整数子集S，|S| = n>=3，找出元素a，确保a既不是S的最大值也不是最小值。
解：只需要从S中任取三个元素，然后找出这三个元素中的非极端元素即可。
说明: 某些情况下无论问题的规模多大，算法需要执行的时间不变：

Fig. 14 非极端排序复杂度

3.3 实例：冒泡排序

Fig. 15 冒泡排序

vector<int> bubble_naive(vector<int> vec){
    int steps=0;
    int n = vec.size();
    for (int i=0; i<n; ++i){
            // No out of range error will be reported in cpp.
            for (int j=0; j<n-1; ++j){
                if (vec[j] > vec[j+1]){
                    swap(vec[j], vec[j+1]);
                }
                ++steps;
            }

        }
    cout<< "Steps: "<<steps<<endl;
    return vec;
}

vector<int> bubble_optimized(vector<int> vec){
    int steps=0;
    int n = vec.size();
    for (int i=n; i>0; --i){
            for (int j=0; j<i-1; ++j){
                if (vec[j] > vec[j+1]){
                    swap(vec[j], vec[j+1]);
                }
                ++steps;
            }
        }
    cout<< "Steps: "<<steps<<endl;
    return vec;
}

vector<int> bubble_optimized2(vector<int> vec){
    int steps=0;
    int n = vec.size();
    for (int i=n; i>0; --i){
        bool swapped = false;
        for (int j=0; j<i-1; ++j){
            if (vec[j] > vec[j+1]){
                swap(vec[j], vec[j+1]);
                swapped = true;
            }
            ++steps;
        }
        if (!swapped){
            cout<< "Break! Steps: "<<steps<<endl;
            return vec;
        }

    }
    cout<< "Steps: "<<steps<<endl;
    return vec;
}
// =======================

void main(){
    //vector<int> vec = {1,4,2,3,5,8,9,7,0};
    vector<int> vec = {1,2,4,3,5,6,7,8,9,22,0,11,12,3};
    print(vec);
    cout<<endl;
    auto vec1=bubble_naive(vec);
    auto vec2=bubble_optimized(vec);
    auto vec3=bubble_optimized2(vec);
    print(vec1);
    print(vec2);
    print(vec3);
}

Output:

Steps: 182
Steps: 91
Break! Steps: 88
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,

四、迭代与递推

4.1 减而治之

所谓“减而治之”，就是讲一个复杂的问题划分成两部分，其中一部分是

Fig. 16 减而治之

4.2 Max2问题

Fig. 16 迭代解法一

迭代解法二：初始化两个指针（下标索引）并确定其顺序。从第三个元素开始扫描，每次扫描先将当前下标元素和x2位置数值（较小的元素）进行比较，若大于x2，则x2的下标更新为当前下标，同时和x1进行比较。

Fig. 17. 迭代解法二
迭代解法二的最好情况需要n-1次比较；最坏情况需要2n-3次比较，并没有实质性的改善。
这个算法体现出分而治之思想的优点。下面使用二分法，每次将数组均分成两段，分别找出第一段(L)的max2元素X1L, X2L和第二段(R)的max2元素X1R, X2R，然后操作为：将X1L于X1R进行比较确定全局最大值（如X1L > X1R），那么再将X2L和X1R进行比较确定次大值。

Fig. 18 二分递归

#include<iostream>
#include<vector>
using namespace std;

//vector A: [lo, lo+1, lo+2, ..., hi)
void max2(vector<int> A, int lo, int hi, int &x1, int& x2){
    if (hi - lo == 3) {
        if (A[lo] < A[lo+1]){
            if (A[lo+1]<A[lo+2]) {
                x1=lo+2;
                x2=A[lo+1]>A[lo]?lo+1:lo;
            } else {
                x1=lo+1;
                x2=A[lo+2]>A[lo]?lo+2:lo;};
        }
        else { // lo > lo+1
            if (A[lo]>A[lo+2]) {
                x1=lo;
                x2=A[lo+1]>A[lo+2] ? lo+1:lo+2;
            } else {
                x1=lo+2;x2=A[lo+1]>A[lo]?lo+1:lo;
            }
        }
        return;
    }  //T(3)<=3;

    if (hi - lo == 2) {
        if (A[lo]>A[hi-1]){
            x1 = lo;
            x2 = hi-1;
        } else {
            x1 = hi-1;
            x2 = lo;
        }
        return;
    }
    int mi = (lo + hi) / 2;
    int X1L, X2L; max2(A, lo, mi, X1L, X2L);
    int X1R, X2R; max2(A, mi, hi, X1R, X2R);
    if (A[X1L] > A[X1R]){
        x1 = X1L;
        x2 = A[X2L] > A[X1R] ? X2L : X1R;
    }
    else{
        x1 = X1R;
        x2 = A[X2R] > A[X1L] ? X2R : X1L;
    }
}

int main(){
    vector<int> A={1,3,4,0,9,-2,8,11};
    //vector<int> A={5,6};
    int lo = 0;
    int hi = A.size();
    int x1, x2;
    max2(A, lo, hi, x1, x2);
    cout<<"Max 2 number: "<< A[x1]<<", "<<A[x2]<<endl;
}

龙哥系统组常用面试题目：

连续子数组的和（动态规划）
二维数组向右或者向下走，选择和最大的路径（动态规划）
立方体八个顶点，一个点给一个数，问能否实现每个面四个顶点和相等 (动态规划/全排列，了解下)
求一个数组中最大的K个数（堆排序 /c++ map 平衡二叉树）
背包问题
长度为n-1的数组中存放了1-n之间的n-1个数。找到缺失的数
二维数组从左往右从上往下递增，判断给定的数是否在数组中，若在则返回位置（时间复杂度要求M+N）
找出链表中环的位置/链表的删除和插入
字符串处理: 将字符串中的某个字符替换为指定字符串（不含目标字符）