文章目录
- 一、数据结构和算法简介
- 二、算法复杂度
- 1. 时间复杂度
- 2. 空间复杂度
一、数据结构和算法简介
数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以我们要学习各种各样的数据结构，比如线性表、树、图、哈希等等。
算法，是定义良好的计算过程。简单来说，算法就是一系列的计算步骤，用来将输入数据转换成输出结果。衡量一个算法的好坏，需要从算法的复杂度来分析。
二、算法复杂度
算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源，因此衡量一个算法的好坏，一般是从时间和空间两个维度来看，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，空间复杂度主要衡量一个算法运行所需要的额外空间。
1. 时间复杂度
在计算机科学中，T(N)描述了该算法的指令执行次数，并不是计算程序的运行时间。因为一个程序的运行时间不仅关乎算法本身，还有编译器版本、机器配置新旧等等因素。
T(N)计算了程序的执行次数，假设每句指令执行时间基本一样（实际有差别但是微乎其微），那么执行次数和运行时间就成等比关系，执行次数就能代表程序运行时间效率的优劣。比如对于同一个问题，算法a的T(N)=N，算法b的T(N)=N2，那么算法a的时间效率优于算法b。
计算时间复杂度要注意：由于CPU一秒可以处理上亿条代码指令，所以变量的单次定义语句可以忽略，时间复杂度只计算循环语句。而我们计算时间复杂度只是想比较算法程序的增长量级，也就是N不断变大时T(N)的差别，而**常数项和低阶项对结果的影响很小，甚至最高项的系数也可以忽略影响，所以我们只保留最高项，并且它的系数视作1。如果T(N)中没有任何关于N的项，时间复杂度就是1。复杂度的最终表示通常使用O的渐进表示法。**
例如：
T(N)=3N2+2N+10，则时间复杂度为O(N2)
T(N)=5N3+N2+5N，则时间复杂度为O(N3)
T(N)=6，则时间复杂度为O(1)
来几个例子分析就懂了：
void Func1(int N)
{
int count = 0; //忽略
for (int i = 0; i < N ; ++i)
{
for (int j = 0; j < N ; ++j)
{
++count; //N^2次
}
}
for(int k = 0; k < 2*N ; ++k)
{
++count; //2N次
}
int M = 10; //忽略
while(M--)
{
++count; //10次
}
}
//T(N)=N^2+2N+10 时间复杂度为O(N^2)
void Func2(int N)
{
int count = 0;
for(int k=0; k<100; k++)
{
++count; //100次
}
printf("%d",count);
}
//T(N)=100 时间复杂度为O(1)
void func3(int n)
{
int cnt = 1;
while(cnt < n)
cnt *= 2;
}
//n=2时，执行次数为1。n=4时，执行次数为2。n=16时，执行次数为4 ......
//假设执行次数为x，则2^x=n。x=log n，时间复杂度为O(logN)
//（对数的底数对结果的影响也可以忽略，因此不管底数是多少都可以省略不写，都表示为log n）
long long func4(size_t N)
{
if(N==0)
return 1;
return func4(N-1)*N;
}
//递归也是一种循环，递归算法的时间复杂度是单次递归的时间复杂度乘递归次数
//时间复杂度为O(1)×N = O(N)
void func5(int N, int M)
{
int count = 0;
for(int k = 0; k<N; k++)
count++; //N次
for(int k = 0; k<M; k++)
count++; //M次
printf("%d", count);
}
//T(N)=N+M
//若N=M，则时间复杂度为O(N)。若M远大于N，则为O(M)。若N远大于M，则为O(N)
除此之外，有些算法的时间复杂度还存在最好、平均、最坏情况。最好情况是任意输入规模的最小运行次数（下界），最坏情况是任意输入规模的最大运行次数（上界）。一般情况下，我们都关注算法的最坏运行情况。比如冒泡排序算法，就存在这样的情况：
最好情况是数组已经有序，时间复杂度就是O(N)；最坏情况是数组完全逆序，时间复杂度是O(N2)，因此冒泡排序的时间复杂度取最差情况O(N2)
2. 空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中需要额外临时开辟的空间。空间复杂度并不是程序运行所占用的内存大小，计算的是变量的个数。大多数算法使用的是有限个变量，所以空间复杂度为O(1)。但对于递归算法，递归的空间复杂度等于单词递归的空间复杂度乘以递归次数，即O(1)×N=O(N)
在实际算法题目中，我们尤其关注时间复杂度，空间复杂度就不是特别重要了。
本篇完，感谢阅读
