复杂度讲解
1、算法好坏的度量
【事前分析法】
算法设计好后，根据算法的设计原理，只要问题规模确定，算法中基本语句执⾏次数和需求资源个数
基本也就确定了。
比如求 1 + 2 + 3 + ... + n − 1 + n ，可以设计三种算法：
算法A：
const int N = 1e5 + 10;
int a[N];
int sum(int n)
{// 先把 1 ~ n 存起来for(int i = 1; i <= n; i++){a[i] = i;}// 循环逐个数字相加int ret = 0;for(int i = 1; i <= n; i++){ret += a[i];}return ret;
} 需要开辟⼀个大小为 N 的空间。
算法B:
int sum(int n)
{// 循环逐个数字相加int ret = 0;for (int i = 1; i <= n;
i++) {ret += i;}return ret;
}不需要开辟空间，直接求和。
需要循环 n 次， ret + = n 语句会执行 n 次 ，而且随着问题规模的增长，执行次数也会增长。
算法执行所需资源的个数与问题规模有关。因此可以根据算法执行过程中对空间的消耗来衡量算法
的好坏，这就是空间复杂度。
算法C：
int sum(int n)
{// 利⽤求和公式return (1 + n) * n / 2;
} 不论问题规模为多少， 语句只会执行1次。
算法中基本语句总的执行次数与问题规模有关。因此可以根据算法执行过程中，所有语句被执行的
次数之和来衡量算法的好坏，这就是时间复杂度。
综上所述，时间和空间的消耗情况就是我们度量⼀个算法好坏的标准，也就是时间复杂度和空间复杂度。
2、时间复杂度
在计算机科学中，算法的时间复杂度是⼀个函数式T ( N ) ，它定量描述了该算法的运行时间。这个
T ( N )函数式计算了程序中语句的执行次数。
案例：计算⼀下 fun 中 ++count 语句总共执行了多少次？
void fun(int N)
{ int count = 0; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { ++count; // 执⾏次数是 n*n，也就是 n^2} } for(int k = 0; k < 2 * N; k++) {++count; // 执⾏次数是 2*n} int M = 10; while(M--) { ++count; // 执⾏次数 10}
} fun 函数 ++count 语句的总执行次数：
T ( N ) = N 2 + 2 × N + 10
大O表示法
在上述案例中，对取值进行分析，随着N的增大，对结果影响最大的⼀项是N^2 ，2N和10
可以忽略不计，算法执行时间的增长率与T ( N )中的 N^2的增长率基本⼀致。
因此，在计算时间复杂度的时候，⼀般会把T ( N ) 中对结果影响不大的项忽略掉，该种表示时间复杂度的方式称为大O渐进时间复杂度 - 这是一种粗略的估计方式，只看影响时间开销最大的⼀项。
O ( T ( N )) = O ( N ^2 + 2 N + 10）
所以对于上述 fun 函数，其时间复杂度为 O ( T ( N )) = O ( N ^2 + 2 N + 10) ，取最高阶项最终为：
O ( N ^ 2 )
推导大O渐进时间复杂度的规则
1. 时间复杂度函数式 T ( N ) 中，只保留最高阶项，去掉那些低阶项；
2. 如果最高阶项存在且不是 1 ，则去除这个项目的常数系数；
3. T ( N ) 中如果没有 N 相关的项目，只有常数项，用常数 1 取代所有加法常数。
最优、平均和最差时间复杂度
案例：在 n 个整形元素数组中，检测 x 是否存在，若存在返回其在数组中的下标，否则返回 −1 。
int find (int a[], int n, int x)
{for (int i = 0; i < n; i++){if (a[i] == x) return i;}return -1;
}
在查找过程中，需用 x 与数组中元素依次比较，因此总的比较次数就是该算法的时间复杂度。则：
• 若待查找元素 x 为 21 ，只需要比较 1 次，为算法的最优(好)情况。
• 若带查找元素 x 为 17 ，或者是不存在的元素，需要比较 n 次，为算法的最坏(差)情况。
• 所有情况的比较次数之和，除以总情况，为算法的平均情况。
查找第⼀个元素需比较1次，查找第2个元素需比较2次，...，查找第n个元素需比较n次，假
设每个元素查找的概率相同，则平均比较次数为
1+2+3+...+n=(1+n)/2。
• 最好时间复杂度为 O (1) ；
• 最坏时间复杂度为 O ( n ) ；
• 平均时间复杂度为 
，也就是O ( n ) 。
，也就是O ( n ) 。 但是，无论是在竞赛还是工程中，算法的时间复杂度⼀般为最差情况。因为最差情况是人对⼀件事情所能承受的底线，因此 find 算法的时间复杂度为 O ( n ) 。
3、空间复杂度
有了时间复杂度的铺垫，空间复杂度的计算就比较容易了。
在算法竞赛中，空间复杂度就是整个程序在解决这个问题时，⼀共使用了多少空间。
案例一：冒泡排序
#include <iostream>
using namespace std;
const int N = 20;
int arr[N];
int main()
{int n = 0;cin >> n;int i = 0;//输⼊for(i=0; i < n; i++)cin >> arr[i];//排序for(i = 0; i < n-1; i++){int j = 0;for(j = 0; j <= n-1-i; j++){if(arr[j] < arr[j+1]){int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp; }}} //输出for(i=0; i < n; i++){cout << arr[i] << endl;}return 0;
} 空间复杂度：需要⼀个和问题规模⼀致的数组来存数据。因此空间复杂度为 O ( N ) 。