写在前面：

这篇文章是在公众号： 程序员小灰 中发布的。是我到目前为止所看到的关于时间复杂度介绍的最好的文章，清晰明了。

所以拿来po出来 仅供学习交流，如侵则删。

现已将此文收录至： 《数据结构》C语言版 (清华严蔚敏考研版） 全书知识梳理


同类好文： 8种方法优雅地利用C++编程从1乘到20

                   从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密

                   Facebook前身 哈佛“选美”网站 核心算法 --- ELO等级分制度(附源码)


正文： 













 



时间复杂度的意义

 

究竟什么是时间复杂度呢？让我们来想象一个场景：某一天，小灰和大黄同时加入了一个公司......



一天过后，小灰和大黄各自交付了代码，两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒，内存占用5MB。小灰的代码运行一次要花100秒，内存占用500MB。于是......





由此可见，衡量代码的好坏，包括两个非常重要的指标：

1.运行时间；

2.占用空间。





 



基本操作执行次数

 

关于代码的基本操作执行次数，我们用四个生活中的场景，来做一下比喻：

场景1：给小灰一条长10寸的面包，小灰每3天吃掉1寸，那么吃掉整个面包需要几天？



答案自然是 3 X 10 = 30天。

如果面包的长度是 N 寸呢？

此时吃掉整个面包，需要 3 X n = 3n 天。

如果用一个函数来表达这个相对时间，可以记作 T（n） = 3n。

场景2：给小灰一条长16寸的面包，小灰每5天吃掉面包剩余长度的一半，第一次吃掉8寸，第二次吃掉4寸，第三次吃掉2寸......那么小灰把面包吃得只剩下1寸，需要多少天呢？

这个问题翻译一下，就是数字16不断地除以2，除几次以后的结果等于1？这里要涉及到数学当中的对数，以2位底，16的对数，可以简写为log16。

因此，把面包吃得只剩下1寸，需要 5 X log16 = 5 X 4 = 20 天。

如果面包的长度是 N 寸呢？

需要 5 X logn = 5logn天，记作 T（n） = 5logn。

场景3：给小灰一条长10寸的面包和一个鸡腿，小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢？



答案自然是2天。因为只说是吃掉鸡腿，和10寸的面包没有关系 。

如果面包的长度是 N 寸呢？

无论面包有多长，吃掉鸡腿的时间仍然是2天，记作 T（n） = 2。

场景4：给小灰一条长10寸的面包，小灰吃掉第一个一寸需要1天时间，吃掉第二个一寸需要2天时间，吃掉第三个一寸需要3天时间.....每多吃一寸，所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢？

答案是从1累加到10的总和，也就是55天。

如果面包的长度是 N 寸呢？

此时吃掉整个面包，需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。

记作 T（n） = 0.5n^2 + 0.5n。



上面所讲的是吃东西所花费的相对时间，这一思想同样适用于对程序基本操作执行次数的统计。刚才的四个场景，分别对应了程序中最常见的四种执行方式：

场景1：T（n） = 3n，执行次数是线性的。

void eat1(int n){
    for(int i=0; i<n; i++){;
        System.out.println("等待一天");
        System.out.println("等待一天");
        System.out.println("吃一寸面包");
    }
}
vo


场景2：T（n） = 5logn，执行次数是对数的。

void eat2(int n){
   for(int i=1; i<n; i*=2){
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("吃一半面包");
   }
}


场景3：T（n） = 2，执行次数是常量的。

void eat3(int n){
   System.out.println("等待一天");
   System.out.println("吃一个鸡腿");
}


场景4：T（n） = 0.5n^2 + 0.5n，执行次数是一个多项式。

void eat4(int n){
   for(int i=0; i<n; i++){
       for(int j=0; j<i; j++){
           System.out.println("等待一天");
       }
       System.out.println("吃一寸面包");
   }
}


 



渐进时间复杂度

 

有了基本操作执行次数的函数 T（n），是否就可以分析和比较一段代码的运行时间了呢？还是有一定的困难。

比如算法A的相对时间是T（n）= 100n，算法B的相对时间是T（n）= 5n^2，这两个到底谁的运行时间更长一些？这就要看n的取值了。

所以，这时候有了渐进时间复杂度（asymptotic time complexity）的概念，官方的定义如下：

若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。

记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。

渐进时间复杂度用大写O来表示，所以也被称为大O表示法。





如何推导出时间复杂度呢？有如下几个原则：


	
如果运行时间是常数量级，用常数1表示；
	
	

	
只保留时间函数中的最高阶项；
	
	

	
如果最高阶项存在，则省去最高阶项前面的系数。
	
让我们回头看看刚才的四个场景。

场景1：

T（n） = 3n 

最高阶项为3n，省去系数3，转化的时间复杂度为：

T（n） =  O（n）



场景2：

T（n） = 5logn 

最高阶项为5logn，省去系数5，转化的时间复杂度为：

T（n） =  O（logn）



场景3：

T（n） = 2

只有常数量级，转化的时间复杂度为：

T（n） =  O（1）



场景4：

T（n） = 0.5n^2 + 0.5n

最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：

T（n） =  O（n^2）



这四种时间复杂度究竟谁用时更长，谁节省时间呢？稍微思考一下就可以得出结论：

O（1）< O（logn）< O（n）< O（n^2）

在编程的世界中有着各种各样的算法，除了上述的四个场景，还有许多不同形式的时间复杂度，比如：

O（nlogn）, O（n^3）, O（m*n），O（2^n），O（n！）

今后遨游在代码的海洋里，我们会陆续遇到上述时间复杂度的算法。



 



时间复杂度的巨大差异

 

 





我们来举过一个栗子：

算法A的相对时间规模是T（n）= 100n，时间复杂度是O(n)

算法B的相对时间规模是T（n）= 5n^2，时间复杂度是O(n^2)

算法A运行在小灰家里的老旧电脑上，算法B运行在某台超级计算机上，运行速度是老旧电脑的100倍。

那么，随着输入规模 n 的增长，两种算法谁运行更快呢？



从表格中可以看出，当n的值很小的时候，算法A的运行用时要远大于算法B；当n的值达到1000左右，算法A和算法B的运行时间已经接近；当n的值越来越大，达到十万、百万时，算法A的优势开始显现，算法B则越来越慢，差距越来越明显。

这就是不同时间复杂度带来的差距。



如果感觉还不错，点个赞↗ 支持一下吧 ~

随后还会不定期更新同类型文章，欢迎订阅关注我的博客 ~

下一篇：400+条实用C/C++框架、库、工具整理 ，你能想到的都在这里了

上一篇： Facebook前身 哈佛大学"选美"网站核心算法 -- ELO等级分制度(附源码)

时间复杂度的要点

时间复杂度的定义–随着数据规模变化程序所需执行时间的一个趋势
如何预估时间复杂度 （加法原则，乘法原则）
时间复杂度种类

最小时间复杂度
最坏时间复杂度
平均时间复杂度
均摊时间复杂度



掌握时间复杂度的分析是学好数据结构和算法的第一步。加油！！！

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

把今年很流行，淡淡的基佬紫送给各位看官，原谅绿就算了,怕被打死。

文章最后，举例使用二分查找和斐波那契的递归和迭代方法，分别说明时间和空间复杂度。
时间复杂度：

首先要说的是，时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。

当我们面前有多个算法时，我们可以通过计算时间复杂度，判断出哪一个算法在具体执行时花费时间最多和最少。
常见的时间复杂度有：

常数阶O(1),

对数阶O(log2 n),

线性阶O(n),

线性对数阶O(n log2 n),

平方阶O(n^2)，

立方阶O(n^3)

k次方阶O(n^K),

指数阶O(2^n)。

随着n的不断增大，时间复杂度不断增大，算法花费时间越多。
计算方法

①选取相对增长最高的项

②最高项系数是都化为1

③若是常数的话用O（1）表示

如f（n）=2*n3+2n+100则O（n）=n3。
通常我们计算时间复杂度都是计算最坏情况

时间复杂度的计算：

（1）如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
        int x=1;
	while (x <10)
	{
		x++;
	}


该算法执行次数是10，是一个常数，用时间复杂度表示是O(1)。

（2）当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			;
		}
	}


该算法for循环，最外层循环每执行一次，内层循环都要执行n次，执行次数是根据n所决定的，时间复杂度是O（n^2）。

（3）循环不仅与n有关，还与执行循环所满足的判断条件有关。
int i=0;
while (i < n && arr[i]!=1)
	{
		i++;
	}


在此循环，如果arr[i]不等于1的话，时间复杂度是O（n）。如果arr[i]等于1的话，则循环执行一次判断跳出，时间复杂度是O(1)。

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

计算方法：

①忽略常数，用O(1)表示

②递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间

③对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。
如：
int a;
int b;
int c;
printf("%d %d %d \n",a,b,c);

它的空间复杂度O（n）=O（1）；
int fun(int n,)
{
int k=10;
if（n==k)
return n;
else
return fun(++n);
}

递归实现，调用fun函数，每次都创建1个变量k。调用n次，空间复杂度O（n*1）=O（n)。
#举例说明
1：实现二分查找算法的递归及非递归。（分析时间复杂度及空间复杂度）
迭代算法
#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<string.h>
#include<assert.h>

int BinarySearch(int arr[], int len, int num)
{
	assert(arr);

	int left = 0;
	int right = len - 1;
	int mid;

	while (left <= right)
	{
		mid = left + (right - left) / 2;

		if (num > arr[mid])
		{
			left = mid + 1;
		}
		else if (num < arr[mid])
		{
			right = mid - 1;
		}
		else
		{
			return mid;
		}
	}

	return -1;
}



int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9 };
	int length = sizeof(arr) / sizeof(arr[0]);
	int aim = 9;
	int result;

	result = BinarySearch(arr, length, aim);

	if (result == -1)
	{
		printf("Can't find %d\n", aim);
	}
	else
	{
		printf("%d at %d postion\n", aim,result + 1);
	}
	

	return 0;
}

二分查找时，每次都在原有查找内容进行二分，所以时间复杂度为O（log2 n）

因为变量值创建一次，所以空间复杂度为O（1）
 递归算法
int BinarySearchRecursion(int arr[5], int lef, int rig,int aim)
{
	int mid = lef + (rig - lef) / 2;

	
	if (lef <= rig)
	{
		if (aim < arr[mid])
		{
			rig = mid - 1;
			BinarySearchRecursion(arr, lef, rig, aim);
		}
		else if (arr[mid] < aim)
		{
			lef = mid + 1;
			BinarySearchRecursion(arr, lef, rig, aim);
		} 
		else if (aim == arr[mid])
		{
			return mid;
		}
		
	}
	else
		return -1;
	
}


int main()
{
	int arr[] = { 1,2,3,5,6, };
	int sz = sizeof(arr)/sizeof(arr[0]);
	int result;

	result = BinarySearchRecursion(arr, 0, sz - 1, 4);

	if (-1 == result)
	{
		printf("Can't find it.\n");
	}
	else
		printf("Aim at %d location\n", result+1);
}

时间复杂度为O（log2 n）

每进行一次递归都会创建变量，所以空间复杂度为O（log2 n）
2：实现斐波那契数列的递归及非递归。（分析时间复杂度及空间复杂度）
迭代算法
int FeiBoNaCciInteration(int a,int b,int num)
{
	int c;

	if (num <= 0)
		return -1;
	else if (num == 1)
		return a;
	else if (num == 2)
		return b;
	else
	{
		while (num - 2)
		{
			c = a + b;
			a = b;
			b = c;
			num--;
		}
		return c;
	}
	
}

int main()
{
	int n;
	int result;

	printf("Input n\n");
	scanf("%d", &n);

	result = FeiBoNaCciInteration(2, 3, n);//可自定义输入第一个数和第二个数
	if (result == -1)
	{
		printf("Input Error!\n");
	}
	else
	{
		printf("n is %d\n", result);
	}

	return 0;
}

时间复杂度O（n)

空间复杂度为O（1）
递归算法
int FeiBoNaCciRecursion(int num)
{
	if (num < 0)
		return -1;
	if (num <= 2 && num > 0)
		return 1;
	else
		return FeiBoNaCciRecursion(num - 1) + FeiBoNaCciRecursion(num - 2);
	
}

int main()
{
	int n;
	int result;

	printf("Input n\n");
	scanf("%d", &n);

	result = FeiBoNaCciRecursion(n);

	if (result == -1)
		printf("Input Error!\n");
	else
		printf("Result is %d\n", result);

	return 0;
}

时间复杂度为O（2^n）

空间复杂度为O（n）
欢迎在评论区留言提问，谢谢！
另外,如果觉得文章对你有用,下边点个打赏吧!
你们的支持，是我坚持的动力。

相信很多小伙伴刷题的时候面对力扣上近两千到题目，感觉无从下手，我花费半年时间整理了leetcode刷题指南，不仅有详细经典题目刷题顺序而且对应题解来排好了，难点还有视频讲解，按照list一道一道刷就可以了，绝对是最强攻略！

文章目录
什么是时间复杂度
什么是大O
如何描述时间复杂度
你所不知道的O(logn)
如果时间复杂度是一个复杂的表达式，我们如何简化
举例说明时间复杂度要怎么算

什么是时间复杂度
时间复杂度就是用来方便开发者估算出程序的运行时间
我们该如何估计程序运行时间呢，我们通常会估计算法的操作单元数量，来代表程序消耗的时间， 这里我们默认CPU的每个单元运行消耗的时间都是相同的。
假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示
随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))
什么是大O
这里就要说一下这个大O，什么是大O呢，很多同学说时间复杂度的时候都知道O(n)，O(n^2)，但说不清什么是大O
算法导论给出的解释：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。
同样算法导论给出了例子：拿插入排序来说，插入排序的时间复杂度我们都说是O(n^2),  但是在数据本来有序的情况下时间复杂度是O(n)，也就对于所有输入情况来说，最坏是O(n^2) 的时间复杂度，所以称插入排序的时间复杂度为O(n^2)
同样的同理我们在看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)
但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，我们这里说的O 代表的就是一般情况，不是严格的上界

所以这里大家知道这么一回事就好了
面试中面试官绝对不会针对快速排序的时间复杂度问题来讨论O的定义， 大家知道讨论的时间复杂度就是指一般情况下的时间复杂度就好了。
大家要对算法的时间复杂度有这样的一个概念
就是同一个算法的时间复杂度不是一成不变的，和输入的数据形式依然有关系
我们主要关心的还是一般情况下的数据形式。
面试中说道算法的时间复杂度是多少指的都是一般情况
但是如果面试官和我们深入探讨一个算法的实现以及性能的时候 我们就要时刻想着 数据用例的不一样 时间复杂度也是不同的，这一点同学们要注意
如何描述时间复杂度
这个图中我们可以看出 不同算法的时间复杂度 在不同数据输入规模下的差异。


我们在决定使用那些算法的时候 ，不是时间复杂越低的越好，要考虑数据规模，如果数据规模很小 甚至可以用O(n^2)的算法比 O(n)的更合适
就像上图中图中 O(5n^2) 和 O(100n) 在n为20之前 很明显 O(5n^2)是更优的，所花费的时间也是最少的。
那我们为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，O(5n^2) 就是O(n^2)的时间复杂度
而且要默认O(n) 优于O(n^2) 呢 ？
这里就又涉及到大O的定义
因为大O其实就是数据量级突破一个点且数据量级非常大的情况下 所表现出的时间复杂度，这个点也就是 常数项系数已经不起决定性作用的点。
例如上图中 20 就是那个点 ，n只要大于20 常数项系数已经不起决定性作用了。
所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下我们都是默认数据规模足够的大，基于这样的事实 我们给出的算法时间复杂的的一个排行如下所示：
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)  


你所不知道的O(logn)
我们平时说这个算法的时间复杂度是logn的，一定是log 以2为底n的对数么？
其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，但我们统一说 logn，也就是忽略底数的描述。
为什么可以这么做呢？
如下图所示


假如我们有两个算法的时间复杂度 分别是log以2为底n的对数 和 log 以10为底n的对数
那么这里如果大家还记得我们高中数学的话，应该不难理解 以2为底n的对数 = 以2为底10的对数 乘以 以10为底n的对数
那这里以2为底10的对数 是一个常数，而我在上面已经讲述了我们计算时间复杂度是忽略常数项系数的
抽象一下 log 以i为底n的对数 等于 log 以j为底n的对数，所以我们忽略了i，直接说是logn，正式因为logij 是就一个常数
所以，这样就应该不难理解了 我们为什么忽略底数了
如果时间复杂度是一个复杂的表达式，我们如何简化
有时候，我们去计算时间复杂度的时候 发现不是一个 简单的O(n) 或者O(n^2)， 而是一个复杂的表达式，例如：
O(2*n^2 + 10*n + 1000) 

那这里我们通常如何描述这个算法的时间复杂度呢，一种方法就是简化法
去掉运行时间中的加法常数项 （因为常数项并不会因为n的增大而增加计算机的操作次数）
O(2*n^2 + 10*n)

去掉常数系数  （我们刚刚已经详细讲过为什么可以去掉常数项的原因了）
O(n^2 + n)

只保留保留最高项  去掉数量级小一级的n （因为n^2 的数据规模远大于 n），最终简化为：
O(n^2) 

如果这一步同学们理解有困难，那也可以做提取n的操作，变成O(n(n+1)) ，省略加法常数项后  也别变成了
O(n^2) 

所以最后我们说：我们这个算法的算法时间复杂度是 O(n^2)
也可以用另一种简化的思路，当n大于40的时候 ， 这个复杂度 会一直小于O(3*n^2)
O(2*n^2 + 10*n + 1000)  < O(3*n^2)

所以说 最后我们省略掉常数项系数最终时间复杂度也是O(n^2)
举例说明时间复杂度要怎么算
我们通过一道题目，来看一下具体时间复杂度应该怎么算
题目描述：找出n个字符串中相同的两个字符串（假设这里只有两个相同的字符串）
一些同学可能以为解决这道题目可以采用枚举遍历的解法，时间复杂度是O(n^2)
这个时间复杂度其实是不对的
这里一些同学忽略了字符串比较的时间消耗，这里并不像int 型数字做比较那么简单，除了n^2 次的遍历次数外，字符串比较依然要消耗m次操作（m也就是字母串的长度），所以时间复杂度是O(m*n*n)
那么我们再想一下其他解题思路
我们先排对n个字符串按字典序来排序，排序后n个字符串就是有序的，意味着两个相同的字符串就是挨在一起
然后在遍历一遍n个字符串，这样就找到两个相同的字符串了
那我们来看看这种算法的时间复杂度
快速排序时间复杂度 为O(nlogn)，依然要考虑字符串的长度是m，那么快速排序每次的比较都要有m次的字符比较的操作，就是O(mnlogn)
之后我们还要遍历一遍这n个字符串找出两个相同的字符串，别忘了遍历的时候依然要比较字符串，所以总共的时间复杂度是 O(m*n*logn + n*m)
我们对O(m*n*logn + n*m) 进行简化操作，把m*n提取出来变成O(m*n*(logn + 1))，
在省略常数项最后的时间复杂度是 O(m*n*logn)， 那我们比较一下时间效率O(m*n*logn) 是不是比第一种方法O(m*n*n)更快一些呢
很明显O(m*n*logn) 要优于O(m*n*n)
所以 先把字符串集合排序在遍历一遍找到两个相同字符串的方式要比直接暴力枚举的方式更快。
通过这个例子 希望大家对时间复杂的是怎么算的有一个初步的理解和认识。

我是程序员Carl，可以找我组队刷题，也可以在B站上找到我，本文leetcode刷题攻略已收录，更多精彩算法文章尽在公众号：代码随想录，关注后就会发现和「代码随想录」相见恨晚！


如果感觉对你有帮助，不要吝啬给一个👍吧！