绪论

学什么

如何用程序代码把现实世界的问题信息化
如何用计算机高效地处理这些信息从而创造价值

基本概念

数据

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

数据元素、数据项

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。
一个数据元素可由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据结构、数据对象

结构是各个元素之间的关系
数据结构 是相互之间存在一种或者多种特定关系的数据元素的集合。
数据对象 是具有相同性质的数据元素的集合，是数据的一个子集。

数据结构的三要素

逻辑结构
- 集合
  - 各个元素同属一个集合，别无其他关系
- 线性结构
  - 数据元素之间是一对一的关系，除了第一个元素，所有元素都有唯一前驱，除了最后一个元素，所有元素都有唯一后继
- 树形结构
  - 数据元素之间是一对多的关系
- 图状结构（网状结构）
  - 数据元素之间是多对多的关系
物理结构（存储结构）
- 顺序存储
  - 存储位置相邻
- 链式存储
  - 借助元素存储地址的指针来辨识元素之间的逻辑关系
- 索引存储
  - 索引表，索引表中的每项称为索引项(关键字，地址)
- 散列存储
  - 通过元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储
数据的运算
- 运算的实现是针对存储结构的
若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。
数据的存储结构会影响存储空间分配的方便程度

数据类型、抽象数据类型：

数据类型 是一个值的集合和定义在此集合上的一组操作的总称。

原子类型。其值不可再分的数据类型。

结构类型。其值可以再分解为若干成分的数据类型。

抽象数据类型(Abstract Data Type, ADT) 是抽象数据组织与之相关的操作。

算法

算法的特性：

有穷性
- 必须在执行有穷步之后结束，且每一步都可以在有穷时间内完成。
- 算法必须是有穷的，而程序可以是无穷的
确定性
- 相同的输入只能得到相同的输出
可行性
- 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现
输入
- 一个算法有零个或者多个输入，这些输入取自于某个特定的对象的集合。
输出
- 一个算个有一个或者多个输出，这些输出是与输入有着某种特定关系的量。

“好”的算法的特性：

正确性
- 算法应能够正确地解决求解问题。
可读性
- 算法应具有良好的可读性，以帮助人们理解（无歧义）
健壮性
- 输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
高效率与低存储量需求
- 时、空间复杂度低

时间复杂度

无法运行结束统计运行时间来判断算法的时间开销，比如：导弹发射之类的。并且在结束之前你不知道他还要运行多久，因此希望算法复杂度能够在运行前计算出来

void print_point(int n){
    int i =1;
    while(i<=n){
        i++;
        std::cout<< i << std::endl;
    }
}

T(3000)=1+3001+3000*2=9000+2(3001 为比较的次数)
T(n)=3n+2
当 n 充分大时，我们只保留阶数最高的，且系数忽略，既
T(n)=O(n)，例如上面的程序 T(n)=O(n)
加法规则：
$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(\max(f(n), g(n)))$
乘法规则：
$T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$

e.g. $T_3(n)=n^3+n^2\log_2n=O(n^3)+O(n^2\log_2n)=O(n^3)$

数量级比较:
$O(1)<O(\log_2n)<O(n)<O(n^k)<O(2^n)<O(n!)<O(n^n)$
其中 $k$ 为大于1的整数.

顺序执行的代码只会影响常数项，可以忽略
只需挑循环中的一个基本操作分析他的执行次数与 $n$ 的关系即可
如果有多层嵌套循环，只需关注最深层循环循环了几次

void print_point(int n){
    int i=1;
    while(i<=n){
        i=i*2;
        std::cout<< i << std::endl;
    }
}

设最深层循环的语句执行 x 次，则由循环条件可知，循环结束时是满足 $2^x>n$ 的最小正整数 x，其中 $x=\lfloor\log_2n\rfloor+1$，因此 $T(n)=O(x)=O(\log_2n)$

int flag[n];//数组中乱序存放了1-n的正整数
void find_elem(int flag[], int n){
    for(int i =0; i<n; i++){
        if(flag[i]==n){
            std::cout<< "找到元素了" << std::endl;
            break;
        }
    }
}

最好情况：元素 n 在第一个位置
最坏情况：元素 n 在最后一个位置
平均情况：假设元素 n 在任意一个位置的概率相同为 $\dfrac{1}{n}$.
平均情况循环的次数 $x=(1+2+\cdots+n)\dfrac{1}{n}=\dfrac{1+n}{2}$
因此，最好时间复杂度 T(n)=O(1)
最坏时间复杂度 T(n)=O(n)
平均时间复杂度 T(n)=O(n)
一般不考虑最好时间复杂度.

空间复杂度

程序运行时需要的内存空间：

程序代码(与问题规模无关)
局部变量、参数

之前的算法，需要的空间与问题规模无关，因此空间复杂度为 O(1)，下面看看与空间复杂度相关的算法

void test(int n){
    int flag[n];
    int i;
    // ....
}

上面这个代码的空间复杂度 S(n)=O(n)

void test(int n){
    int flag[n][n];
    int other[n];
    int i;
    // ...
}

空间复杂度 $S(n)=O(n^2)+O(n)+O(1)=O(n^2)$
同样满足加法规则

函数调用同样会带来内存开销。

void test(int n){
    int a,b,c;
    if(n>1){
        test(n-1);
    }
    std::cout << n <<std::endl;
}

递归调用带来内存开销
注：与函数调用栈相关。
这个空间复杂为 S(n)=O(n)

void test(int n){
    int flag[n];
    if(n>1){
        test(n-1)
    }
    std::cout << n <<std::endl;
}

这个空间复杂度为 $1+2+\cdots+n=\dfrac{n(n+1)}{2}$
$S(n)=O(n^2)$

时间、空间复杂度主要考虑与问题规模相关的部分.