一篇博客搞定时间复杂度

算法在编写成可执行程序后，运行时要耗费时间和空间资源，因此衡量一个算法的好坏，一般是从时间和空间两个维度入手的，也就是时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要耗费的额外空间。
我们在学习算法的时候总是听到有人讨论时间复杂度，但却很少听到有人讲空间复杂度，这是因为在计算机发展的早期，计算机的容量很小，空间很金贵，所以当时对空间复杂度很在乎，但随着时代的快速发展，计算机的容量已经达到了很高的程度，所以我们今天不很在乎一个算法的空间复杂度。那么问题来了，什么是时间复杂度呢？

1、什么是时间复杂度？

在计算机科学中，算法的时间复杂度是一个函数式T(N)，一个算法花费的时间与算法中语句的执行次数成正比。
一般情况下，算法中基本操作重复执行的次数是问题规模n的函数，用T(N)表示，它定量描述了该算法的运行时间。如果有一个函数f(n)，使得当n趋于无穷大时，T(N)/f(n)的极限值是不为0的常数，那就称T(N)和f(n)是同数量级函数，记作T(N)=O(f(n))，称O(f(n))就是该算法的渐进时间复杂度，也就是时间复杂度。

注意：复杂度的表示通常使用大O的渐进表示法。

如上图，随着规模n的不断增大，代码的执行时间不断增大，它的执行效率就不断降低。

2、推导大O的规则

1、时间复杂度只保留函数式T(N)中最高阶项，去掉那些低阶项，因为当n不断变大时，低阶项对结果的影响越来越小，当n无穷大时，就可以忽略不计了。

2、如果高阶项的系数存在且不是1，就去除它的常数系数，因为当n 不断变大时，常数系数对结果的影响越来越小，当n无穷大时，就可以忽略不计了。

3、T(N)中如果没有N相关的项目，只有常数项，用常数1取代，即O(1)。

关于以上时间复杂度大O的推导规则还有以下补充，我们以代码形式讲解：

int func(const char* arr)
{
	int num = 0;
	while (*arr != '\0')
	{
		num++;
		arr++;
	}
	return num;
}

这是一段简单的计算字符个数的代码，当运行这段代码时我们可以分为三种情况：
假设字符串长度为n。

• arr数组中只有一个字符，此时T(N)=1
• arr数组中有很长一段字符，此时T(N)=N
• 平均情况下T(N)=N/2。

时间复杂度：
最好情况下：O(1)（下界）
最坏情况下：O(n)（上界）
平均情况下：O(n)

大O推导规则的补充：大O的渐进表示法在实际中一般情况下关注的是算法的上界，也就是最坏的运行情况。

3、时间复杂度的计算

3.1 基础题 1

求该算法的时间复杂度：

void func(int n)
{
	int count = 0;
	for (int i = 0;i < n;i++)
	{
		count++;
	}
}

T(N)=N，即时间复杂度为O(n)

3.2 基础题 2

void func(int n)
{
	int count = 0;
	for (int i = 0;i < 2*n;i++)
	{
		count++;
	}
	int m = 100;
	while (m--)
	{
		count++;
	}
}

T(N)=2*N+100，由规则1和规则2得，时间复杂度是O(n)

3.3基础题 3

void func(int n, int m)
{
	int count = 0;
	for (int i = 0;i < n;i++)
	{
		count++;
	}
	for (int j = 0;j < m;j++)
	{
		count++;
	}
}

T(N)=N+M，由于我们不知道N与M谁大谁小，分为3种情况
1：N近似等于M，此时T(N)=2*N 或 T(N)=2*M，根据规则2去除常数系数，时间复杂度为O(n)
2：N>>M，此时T(N)=N，时间复杂度为O(n)
3：M>>N，此时T(N)=M，时间复杂度为O(n)
综上，时间复杂度为O(n)

3.4进阶题 1

void func(int n)
{
	int count = 0;
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < n;j++)
		{
			count++;
		}
	}
	for (int k = 0;k < 2 * n;k++)
	{
		count++;
	}
	int m = 10;
	while (m--)
	{
		count++;
	}
}

由基本操作次数得知：T(N)=N²+2*N+10，由规则1保留最高阶项，又因为无常数系数得：时间复杂度为O(n²).

3.5进阶题 2

void func(int* a, int n)
{
	int count = 0;
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= i;j++)
		{
			count++;
		}
	}
}

遇到这种多重循环体，我们一般是从内层循环到外层循环依次分析：
当i=1时，内层循环执行1次
当i=2时，内层循环执行2次
当i=3时，内层循环执行3次
……
当i=n时，内层循环执行n次

通过观察i从1到n的整个过程，我们可以推导出T(N)=N*(N+1)/2，也就是我们所熟悉的等差数列求和，展开T(N)得T(N)=N²/2 + N/2，根据规则1保留最高项，根据规则2去除常数系数，得到时间复杂度为O(n²).

3.6 偏难题 1

void func(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(2)n，所以时间复杂度为O(logn)

注意：当n接近无穷大时，底数的大小对结果影响不大，因此一般情况下不管底数是多少都可以忽略不写，即O(logn)，所以上面将2忽略了。

3.7偏难题 2（递归）

long long func(int n)
{
	if (n == 0)
		return 1;
	return func(n - 1) * n;
}

递归算法的时间复杂度=单次递归的时间复杂度*递归次数。
在本题调用一次func函数的时间复杂度是O(1)，而在本题中调用了n次，即T(N)=N，因此时间复杂度为O(n)。

此时有人会有疑惑，说递归不是分为递推和回归吗？我们调用一共花了n次，而回归也要花费n次，那T(N）不该是2*N吗？这种思想在本题没有影响，因为我们一次函数调用的时间复杂度是O(1)，但当不是O(1)时会出错，注意我们调用过程创建了函数栈帧，并且执行了函数中的语句，而回归过程是函数栈帧销毁的过程，没有语句执行，所以不耗费时间。因此在本题中T(N)=N，时间复杂度为O(n)。

总结：
以上就是本期博客分享的全部内容啦！技术的探索永无止境。
道阻且长，行则将至！后续我会给大家带来更多博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～