数据结构 算法时间复杂度和空间复杂度

一、算法好坏的度量

【事前分析法】
算法设计好后，根据算法的设计原理，只要问题规模确定，算法中基本语句执⾏次数和需求资源个数
基本也就确定了。
⽐如求1 + 2 + 3 + ... + n − 1 + n ，可以设计三种算法：

算法A：需要开辟⼀个⼤⼩为N 的空间。

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;
}

算法B：不需要开辟空间，直接求和。需要循环n 次，ret + = n 语句会执⾏n 次，⽽且随着问题规模的增⻓，执⾏次数也会增⻓。

int sum(int n)
{// 循环逐个数字相加 int ret = 0;for (int i = 1; i <= n; 
i++) {ret += i;}return ret;
}

算法C：不论问题规模为多少， 语句只会执⾏1 次。

int sum(int n)
{// 利⽤求和公式 return (1 + n) * n / 2;
}

综上所述，时间和空间的消耗情况就是我们度量⼀个算法好坏的标准，也就是时间复杂度和空间复杂度。

二、时间复杂度

时间复杂度
在计算机科学中，算法的时间复杂度是⼀个函数式 ，它定量描述了该算法的运⾏时间。这个函数式计算了程序中语句的执⾏次数。

案例：计算⼀下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
• 当N = 10 时，T (N) = 100 + 20 + 10 = 130
• 当N = 100 时，T (N) = 10000 + 200 + 10 = 10210
• 当N = 1000 时，T (N) = 1000000 + 2000 + 10 = 1002010
• 当N = 10000 时，T (N) = 100000000 + 20000 + 10 = 100020010

推导⼤O渐进时间复杂度的规则：
1. 时间复杂度函数式T (N)中，只保留最⾼阶项，去掉那些低阶项；
2. 如果最⾼阶项存在且不是1 ，则去除这个项⽬的常数系数；
3. T (N)中如果没有N 相关的项⽬，只有常数项，⽤常数1 取代所有加法常数。

相关案例：

void func1(int N)
{int count = 0;for(int k = 0; k < 2 * N; k++){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

基本语句++count 关于问题规模n 总执⾏次数的数学表达式为:f(n) = n × 2 + 10 ；
保留最⾼阶项，省略最⾼阶项的系数后的⼤O渐进表⽰法为：O(n) 。

void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

// ⽤递归计算 N 的阶乘 
long long fac(int N)
{if(N == 0) return 1;return fac(N - 1) * N;
}

递归算法时间复杂度求解⽅式为，单次递归时间×总的递归次数。
注意，这⾥只是简易的估算⽅式。递归算法的时间复杂度严谨的计算⽅法是利⽤主定理(Master
Theorem)来求得递归算法的时间复杂度。
但是，我们往后学习更加深⼊会发现，⼤多是情况下，我们并不需要计算出准确⽆误的时间复杂度，
只需要根据做题经验，简单估算⼀下即可。所以，这⾥为了不增加⼤家负担，对于递归算法，我们仅
需掌握这样简易的计算⽅式即可。
单次递归没有循环之类，所以时间复杂度为常数。总的递归次数就是递归过程中， 递归调⽤了多
少次。
F ac
F ac(5) 需要递归6 次，则F ac(n)就需要递归n + 1 次，故递归求阶乘的时间复杂度为O(n) 。