你还在为时间复杂度不懂而担心吗？？？赶紧进来，这里手把手教你计算时间复杂度！！！_时间复杂度怎么算

作者：低调
作者宣言：写好每一篇博客

---

前言

时间复杂度是数据结构最开始学的一章，我相信大部分人和我一样，刚开始学，或者已经学完这一章，都还不理解这个是什么意思，怎么计算时间复杂度，接下来，我将为大家进行详细的介绍，看看我能不能把你们讲懂：

---

以下是本篇文章正文内容，下面案例可供参考

一、什么是时间复杂度？

我们通常说时间复杂度是建立在算法效率上的，所以也叫算法的时间复杂度。

什么是算法效率？

算法效率分析的目的是看算法实际是否可行，并在同一个问题存在多个算法时，可进行时间和空间性能上的比较，以便从中挑选出较优的算法

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间（由于现在计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度，此文也就不在讲解空间复杂度了）

1.1时间复杂度的概念

注：在计算机科学中，算法的时间复杂度是一个函数，需要把程序放到计算机上运行才能得出结果，很显然这样是非常麻烦的。

所以我们才有了时间复杂度这个分析方式，一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

1.2复杂度计算在算法的意义

虽然我们现在写的程序很快运行出来了，但在今后工作中，我们会面临几十万行代码，这个时候就体现到算法效率的意义，和计算时间复杂度的重要性了。在以后面试过程中，也需要掌握怎么计算，才能顺利通过面试。

1.3如何计算常见算法的时间复杂度？

大O的渐进表示法

我们先来看一个简单的代码：

// 请计算一下Func1基本操作执行了多少次？
void Func1(int N) {
 int count = 0;
 for (int i = 0; i < N ; ++ i)//执行N次
 {
 for (int j = 0; j < N ; ++ j)//执行N次，并且这个for在另一个for内部
 {
 ++count;
 }
 }
 for (int k = 0; k < 2 * N ; ++ k)//执行2N次
 {
 ++count;
 }
 int M = 10;
 while (M--)//执行十次；
 {
 ++count;
 }
 printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Func1 执行的基本操作次数：F（N）=N×N+2*N+10
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
*实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
*大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后，Func1的时间复杂度为：
O（N*N）
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执
行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

相信大家也会计算出O（2*N）
当N特别大的时候，N和2N差距也是特别大，这就有人会说不应该把2去掉。
这里给大家举个例子：大家可以去网上搜搜，现在腾讯市值大约值 4 5万亿，而百度市值大约值五千亿，两个集体的老总同时买最贵的别墅，是不是都买得起。所以这个不是影响。当N特别大的时候，这种差距也就不约而同了。这个你们也可以将给你们的同学听听。

二、常见时间复杂度计算举例

话不多说直接上代码：
1.

// 计算Func2的时间复杂度？
void Func2(int N, int M) {
 int count = 0;
 for (int k = 0; k < M; ++ k)//执行M次
 {
 ++count;
 }
 for (int k = 0; k < N ; ++ k)//执行N次
 {
 ++count;
 }
 printf("%d\n", count);
 }
1
2
3
4
5
6
7
8
9
10
11
12
13

F（N）=M+N;
时间复杂度O（M+N）；

// 计算Func3的时间复杂度？
void Func3(int N) {
 int count = 0;
 for (int k = 0; k < 100; ++ k)//执行100次
 {
 ++count;
 }
 printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9

F（N）=100；
时间复杂度为O（1）；

3.冒泡排序

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n) {
 assert(a);
 for (int end = n; end > 0; --end)
 {
 int exchange = 0;
 for (int i = 1; i < end; ++i)
 {
 if (a[i-1] > a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

当end=n时，第二个for执行n-1次
当end=n-1时, 第二个for执行n-2次
……
当end=2时，第二个for执行1次
F（N）=1+2+…+n-1;
这是一个等差数列求和，最高次方为N×N；
时间复杂度为O（N*N）

注：当是有序的时候，时间复杂度为O（N）；
因为这个代码做了优化，当end=n时，当第二个for循环走完后，因为是有序的，不会进入if语句，所以exchange不会发生改变，就会进入第二个if语句，直接退出循环，所以当有序的时候第一个for只执行了一次，第二个for执行了n-1次，所以是时间复杂度为O（N）；

4.二分查找

// 计算BinarySearch的时间复杂度？
//也叫二分查找（折半查找算法）
int BinarySearch(int* a, int n, int x) {
 assert(a);//断言,如果数组a为空，就直接断言出去
 int begin = 0;
 int end = n;
 while (begin < end)
 {
 int mid = begin + ((end-begin)>>1);//这是位移操作符>>1//右移一个比特位，相当于除了2
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid;
 else
 return mid;
 }
 return -1;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

设X为要查找的次数，大家可以想象将一张纸对折对折在对折，就类似折半查找
举个例子：当N=16时，第一次循环没找到，N=8，第二次循环没找到，N=4，第三次循环没找到，N=2；第四次要么找到了，要么没有找到。
F（N）=2的X次方；（这里次方符合不太好打出来，望读者见谅）
X=logN；（通常2可省略不写）
时间复杂度O（logN）；

注：希望读者仔细看着代码去理解。

5.阶乘的递归

// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N) {
 return N < 2 ? N : Factorial(N-1)*N; }
1
2
3

我们以N=4为例

大家可以看到，递归了四次就完成了计算
F（N）：递归次数*每次递归函数的次数；
时间复杂度O(N)；

不理解的可以自己在下去画画递归展开图

6.斐波那契数列

long long Fibonacci(int n){
return n<2?n:Fibonacci(n-1)
+Fibonacci(n-2);}
1
2
3

注：1 1 2 3 5 8 13……后一个数是前两位数的和，叫做斐波那契数列。

我们以求第四个斐波那契数为例
大家应该可以清晰的看到第一层只有一次递归，第二层优两次递归。第三层就四次递归；
F（N）=2的0次方+2的1次方+……+2的n-1次方=2的n次方-1
时间复杂度O（2的n次方）

达到2的n次方，可以说效率非常低了，当求第50个的数时，就要运算2的50次方次，cpu的运行大约只有上亿次，出现这种效率低的原因是因为每一次递归需要建立栈帧，递归需要消耗空间，说白了就是以空间换取时间。

接下来我给大家弄一个优化版

int Fib(int n){
int a,b,c=1;
while(n>2)
{  c=a+b;
	a=b;
	b=c;
	n--;}
	return c;
1
2
3
4
5
6
7
8

这样时间复杂度O（N），这样大大提高了运行效率。

我们还有常见的还有O（N*logN），快速排序，希尔排序都是符合这样的时间复杂度。大家可以自己下去了解一下。

注：效率依次从高倒低是：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)

三、oj练习题

这一题最基本的思想就是就是一个一个数的遍历，先遍历一次找到一个数，在遍历一遍找到第二个消失的数，这样时间复杂度就是O（N*N），但题目要求时间复杂度是O（N），
所以我们有必须环一种思路，先看代码，我在来给大家解释：

int missingNumber(int* nums, int numsSize){
    int x=0;
for(size_t i=0;i<numsSize;i++)
{
    x^=nums[i];
}
for(size_t i=0;i<=numsSize;i++)
{
    x^=i;
}
return x;
}
1
2
3
4
5
6
7
8
9
10
11
12

我们利用了异或的特性，相同为0，相异为一，X同时异或两个数就为0，0与任何数异或等于任何数，题目说是0-n的数，举个例子：
0 1 2 3 4 5 6 8 9
我们所要找的数字是7，我们让X与上面这个数组先疑惑，
在与完整0 1 2 3 4 5 6 7 8 9进行疑惑，大家可以看到除了7，所有数都和X异或了两次，变成了0，所有我们找到了消失的数字。如果大家不明白X与一个数异或两次为什么为0的话，我在给大家画个图，来进一步的理解：

相信大家看到这里应该理解了吧！

总结

上述是我总结一些关于时间复杂度的概念，计算和习题，让我们对时间复杂度不在感到陌生，也让我们明白了时间复杂度的重要性，希望读者看完这篇文章再去看看之前学的，不会计算的时间复杂度，现在会了没有，对于刚接触的也是可以去尝试看一下，如果我写的有不对的地方，也希望你们指出来。让我们一起学习进步吧!