当前位置: 首页 > article >正文

一篇博客搞定时间复杂度

时间复杂度

  • 1、什么是时间复杂度?
  • 2、推导大O的规则
  • 3、时间复杂度的计算
    • 3.1 基础题 1
    • 3.2 基础题 2
    • 3.3基础题 3
    • 3.4进阶题 1
    • 3.5进阶题 2
    • 3.6 偏难题 1
    • 3.7偏难题 2(递归)

前言:

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

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)=N2+2*N+10,由规则1保留最高阶项,又因为无常数系数得:时间复杂度为O(n2).

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)=N2/2 + N/2,根据规则1保留最高项,根据规则2去除常数系数,得到时间复杂度为O(n2).

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,则2x=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账号,我们一同成长!
(~ ̄▽ ̄)~


http://www.kler.cn/a/585338.html

相关文章:

  • Pytorch的入门
  • Java 8 + Tomcat 9.0.102 的稳定环境搭建方案,适用于生产环境
  • 使用curl随机间隔访问URL-使用curl每秒访问一次URL-nginx
  • Vue配置和安装教程(2025最新)
  • CGI程序处理每一帧VDEC视频数据并输出到HTML页面
  • 【Unity】TextMesh Pro显示中文部分字体异常
  • Cascadeur-3D关键帧动画软件
  • Redis--zset类型
  • 信号处理抽取多项滤波的数学推导与仿真
  • 警惕!Ollama大模型工具的安全风险及应对策略
  • Webpack 和 Vite 的主要区别
  • C# net deepseek RAG AI开发 全流程 介绍
  • flinkOracleCdc源码介绍
  • Python 与 sklearn 库:轻松构建 KNN 算法双版本
  • 如何撰写一份清晰专业的软件功能测试报告
  • Vue项目搜索引擎优化(SEO)终极指南:从原理到实战
  • JVM 垃圾回收器的选择
  • 海量数据查询加速:Presto、Trino、Apache Arrow
  • 在Vue3中集成XGPlayer视频播放器的完整指南
  • Unity打包Android平台调用sherpa-onnx