基本概念
- 数据结构：一组数据的存储结构，它是静态的，是组织数据的一种方式；
- 算法：操作数据的一组方法；
- 复杂度分析方法：包括时间、空间复杂度分析方法，不需要具体的测试数据，就可以粗略地估计算法的执行效率（算法代码的执行时间）的方法。
- 概括：数据结构与算法着眼于如何更省、更快地存储和处理数据，即如何让代码运行得更快，如何让代码更省存储空间。因此，就需要一个考量算法执行效率和资源消耗的方法，这就是时间、空间复杂度分析方法。
数据结构是为算法服务的，算法要作用在特定的数据结构之上，无法单独孤立数据结构和算法，我们应该在数据结构的基础上操作、构建算法。
- 常用的数据结构与算法：
10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树；
10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
时间复杂度的概念
公式：
- 其中：
表示代码总执行时间；
表示数据规模大小；
表示代码总的执行次数；
表示
- 大O时间复杂度表示方法，表示的并不是代码的真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度（asymptotic time complexity，简称时间复杂度）。
举例：
int cal(int n)
{
int sum = 0;
int i = 1;
int j = 1;
for ( ; i <= n; ++i)
{
j = 1;
for (; j <= n; ++j)
{
sum = sum + i * j;
}
}
}
- 假设每行代码是执行时间都为SingleTime，之后，观察代码，第3、4、5行分别执行了1次，第6、8行执行了
次，所以总共就需要
的执行时间，因为大O时间复杂度表示的是代码执行时间的变化趋势，所以不需要关心SingleTime的具体值。
- 当
的影响可以忽略，只记录最大的量级，即上述代码的时间复杂度可记为：
。
时间复杂度分析方法
1、只取循环执行次数最多的一段代码
大O时间复杂度表示方法表示的是一种变化趋势，通常忽略低阶，系数和常量，只取最大阶的量级。所以在分析一段代码的时间复杂度的时候，也只关注循环执行次数最多的一行代码。
2、加法法则
总复杂度等于量级最大的那段代码的复杂度。
举例：
int cal(int n) {
int sum_1 = 0;
int p = 1;
for ( ; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for ( ; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
- 这段代码分为三部分sum_1，sum_2，sum_3，分别求每一部分的时间复杂度，然后再取量级最大的作为整段代码的复杂度。
- 第一段代码循环执行了100次，与n的规模无关，是个常量执行时间，则
补充：只要循环的次数是一个常数，与n无关，都属于常量级的执行时间，当n很大时都可以忽略。因为时间复杂度表示一个算法执行效率，与数据规模增长的变化趋势，常量次数的执行时间对增长趋势是没有影响的，所以不管常量执行时间多大，都可以忽略；
- 第二、三段代码的时间复杂度分别为
和
- 整段代码的时间复杂度为
- 抽象公式：
，
那么:
3、乘法法则（嵌套循环）
用于嵌套执行的代码，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
举例：
int cal(int n) {
int ret = 0;
int i = 1;
for ( ; i < n; ++i) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for ( ; i < n; ++i) {
sum = sum + i;
}
return sum;
}
- 先假设函数f是一行普通的代码，则第4~6行的代码复杂度为
，但函数f不是一行简单的代码，它的时间复杂度为
- 所以整段代码的时间复杂度为
。
- 公式抽象：
；那么：
。
常见的时间复杂度
复杂度量级
- 常量阶：
- 对数阶：
- 线性阶：
- 线性对数阶：
- 平方阶：
- 立方阶：
- k次方阶：
- 指数阶：
- 阶乘阶：
上述复杂度量级按数量级递增，粗略分为多项式量级和非多项式量级，非多项式量级只有两个：和
，把时间复杂度为非多项式量级的算法问题叫做NP（Non-Deterministic Polynomical，非确定多项式）问题。
当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，所以非多项式量级时间复杂度算法的执行效率很低。
O(1)
表示常量级时间复杂度，程序无论执行了多少行代码，只要是常数个次数，时间复杂度就是O(1)，即只要代码的执行时间不随n的增大而增长，这样的代码时间复杂度就是O(1)。
O(logn)、O(nlogn)
举例：
i = 1;
while (i <= n) {
i = i * 2;
}
第三行代码执行次数最多，依此计算整段代码的复杂度。
易得：
当的值大于
，所以这段代码的时间复杂度就是
，因为在时间复杂度里忽略对数的底，所以统一表示为
（，所以
，其中
是个常量，忽略系数对复杂度的影响）。
表示时间复杂度为
的代码执行
O(m+n)、O(m*n)
表示代码的复杂度由两个数据的规模决定，这种情况下，加法规则不再适用，但乘法规则仍适用：
；
举例：
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for ( ; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for ( ; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
m、n为两个数据规模，无法评估哪个更大，所以就不能用加法规则省略其中一个，则时间复杂度为：。
空间复杂度概念
类比时间复杂度，全称为渐进时间复杂度，表示的是算法执行时间与数据规模之间的增长关系；则空间复杂度，全称为渐进空间复杂度（Asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
空间复杂度分析方法
举例：
void print(int n) {
int j = 2;
int *a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = i * j;
}
for (i = n-1; i >= 0; --i) {
//print out a[i]
}
}
上述代码中，第二行申请了一个空间存储变量j，属于常量阶，和没有关系，可以忽略。第三行申请了一个大小为
的int型数组，除此之外，剩下的代码都没有占用其他空间，所以整段代码的空间复杂度为
。
常见的空间复杂度
，
，
，像
，
一般用不到，空间复杂度的分析要比时间复杂度简单得多。
小结
复杂度全称叫渐进复杂度，包括渐进时间复杂度（时间复杂度）和渐进空间复杂度（空间复杂度），作用是分析算法执行效率和数据规模之间的增长关系。一般越高阶的复杂度的算法，其执行效率也就越低，但在部分情况下，也有例外。
常见的复杂度从低阶到高阶：，
，
，
，
。如图所示复杂度阶级。
