【你真的了解时间复杂度吗】(一)

简介: 【你真的了解时间复杂度吗】(一)

不是看到了希望才去坚持,而是坚持了才看到了希望。

b26e8dc8970f4238ba0bf2732273a8e0.png

1.算法效率

1.1 如何衡量一个算法的好坏

给你一个代码,如何衡量其好坏呢?

long long Fib(int N)
{
 if(N < 3)
 return 1;
 return Fib(N-1) + Fib(N-2);
}

只是单纯的看代码的简洁性吗?

显然不可能只是这样。代码的优化往往是先考虑时间空间复杂度,再去考虑代码的简洁性。

那什么是复杂度呢?

1.2 算法的复杂度

算法在编写成可执行程序后,运行时需要耗费时间资源和空间 ( 内存 ) 资源 。因此 衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的 ,即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间 。在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

我们无论在力扣还是在牛客上刷题,有时候题目会明确要求时间空间复杂度,所以我们必须要明白什么是时间复杂度,什么是空间复杂度。


2.时间复杂度

2.1 时间复杂度的概念

时间复杂度的定义:在计算机科学中, 算法的时间复杂度是一个函数 ,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知 道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例, 算法中的 基本操作的执行次数 ,为算法 的时间复杂度。

即:找到某条基本语句与问题规模 N 之间的数学表达式,就是算出了该算法的时间复杂度。

我们可以来做个题来练练手:

// 请计算一下Func1中++count语句总共执行了多少次?
void Func1(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;
}

这道题通过计算我们可以得出++count总共执行的次数为:N^2+2N+M

我们用一些具体的N来计算下执行次数:

N = 10         F(N) = 130           N^2=100

N = 100       F(N) = 10210       N^2=10000

N = 1000     F(N) = 1002010   N^2=1000000

我们发现随着N越来越大,第二项与第三项越来越接近,也就是除去最高阶项外的其余项对最终结果的影响越来越小了。实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。

2.2 O的渐进表示法

大 O 符号( Big O notation ):是用于描述函数渐进行为的数学符号。

推导大 O 阶方法:

1 、用常数 1 取代运行时间中的所有加法常数。

2 、在修改后的运行次数函数中,只保留最高阶项。

3 、如果最高阶项存在且不是 1 ,则去除与这个项目相乘的常数。得到的结果就是大 O 阶。

使用大 O 的渐进表示法以后, Func1 的时间复杂度为: O(N^2)

通过上面我们会发现大 O 的渐进表示法 去掉了那些对结果影响不大的项 ,简洁明了的表示出了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况:

最坏情况:任意输入规模的最大运行次数 ( 上界 )

平均情况:任意输入规模的期望运行次数

最好情况:任意输入规模的最小运行次数 ( 下界 )

例如:在一个长度为 N 数组中搜索一个数据 x

最好情况: 1 次找到

最坏情况: N 次找到

平均情况: N/2 次找到

在实际中一般情况关注的是算法的最坏运行情况,所以上面题中搜索数据时间复杂度为 O(N)

为什么计算机敢用常数 1 取代运行时间中的所有加法常数?

因为cpu的运行速度很快,运行100次与运行100000000在速度方面差异并不明显,我们可以测试一下:

1bc436bc344d47a7ac25bd3cd9673485.png

91b160993ec347859bd041414a754c52.png

运行100次与运行100000000只相差了大概55毫秒(0.055秒),这还只是在Debug版本下,

在Release版本下的差异会更小


2.3常见时间复杂度计算举例

我们可以来做一些题目来帮助我们更好的理解大O的渐进表示法:

实例1

// 计算Func2的时间复杂度?
void Func2(int N)
{
 int count = 0;
 for (int k = 0; k < 2 * N ; ++ k)
 {
 ++count;
 }
 int M = 10;
 while (M--)
 {
 ++count;
 }
 printf("%d\n", count);
}

实例1基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N)

实例2:

// 计算Func3的时间复杂度?
void Func3(int N, int M)
{
 int count = 0;
 for (int k = 0; k < M; ++ k)
 {
 ++count;
 }
 for (int k = 0; k < N ; ++ k)
 {
 ++count;
 }
 printf("%d\n",count);
}

实例2基本操作执行了M+N次,有两个未知数MN,时间复杂度为O(N+M)

实例3:

// 计算Func4的时间复杂度?
void Func4(int N)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}

实例3基本操作执行了10次,通过推导大O阶方法,时间复杂度为O(1)

实例4:

// 计算BubbleSort的时间复杂度?
void BubbleSort(int* a, int n)
{
 assert(a);
 for (size_t end = n; end > 0; --end)
 {
 int exchange = 0;
 for (size_t i = 1; i < end; ++i)
 {
 if (a[i-1] > a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
}

实例4 基本操作执行最好 N 次,最坏执行了 (N*(N+1)/2) 次,通过推导大 O 阶方法 + 时间复杂度一般看最 坏,时间复杂度为 O(N^2)


目录
相关文章
|
7月前
|
机器学习/深度学习 算法 安全
用PyTorch从零构建 DeepSeek R1:模型架构和分步训练详解
本文详细介绍了DeepSeek R1模型的构建过程,涵盖从基础模型选型到多阶段训练流程,再到关键技术如强化学习、拒绝采样和知识蒸馏的应用。
671 3
用PyTorch从零构建 DeepSeek R1:模型架构和分步训练详解
|
Java 关系型数据库 MySQL
【Java Spring开源项目】新蜂(NeeBee)商城项目运行、分析、总结
【Java Spring开源项目】新蜂(NeeBee)商城项目运行、分析、总结
754 4
|
人工智能 前端开发 搜索推荐
详解基于百炼平台及函数计算快速上线网页AI助手
通过阿里云百炼平台,企业可在10分钟内为其网站添加智能客服系统,提升用户体验并降低成本。流程包括:创建大模型应用、配置参数(如温度系数以控制回复的随机性)、发布应用获取API密钥;使用函数计算快速搭建示例网站,并通过简单的代码更改启用AI助手功能;还可导入私有知识库增强助手的能力。前端基于NLUX开发,支持定制化需求如样式调整和历史会话管理。服务端代码提供了调用大模型获取答案的接口。借助百炼平台,企业能迅速部署即时且个性化的在线服务,适应数字化转型的需求。
仿美团饿了么程序,外卖人9.0外卖订餐源码(PC+微信)
仿美团饿了么程序,外卖人9.0商业版外卖订餐源码,PC+微信+WAP+短信宝,多城市多色版 非常不错的独立版外卖跑腿网站源码,喜欢的可以下载调试看看吧!!
269 0
|
Web App开发 前端开发
什么是移动端适配
【8月更文挑战第2天】
|
机器学习/深度学习 编解码 Unix
超分数据集概述和超分经典网络模型总结
超分数据集概述和超分经典网络模型总结
497 1
|
机器学习/深度学习
【阿旭机器学习实战】【21】通过SVM分类与回归实战案例,对比支持向量机(SVM)3种SVM不同核函数
【阿旭机器学习实战】【21】通过SVM分类与回归实战案例,对比支持向量机(SVM)3种SVM不同核函数
【阿旭机器学习实战】【21】通过SVM分类与回归实战案例,对比支持向量机(SVM)3种SVM不同核函数
|
弹性计算 大数据 测试技术
阿里云服务器租用费用_优惠价格表
2023年阿里云服务器租用费用,轻量应用服务器和云服务器ECS优惠价格表,阿里云轻量应用服务器2核2G3M带宽轻量服务器一年108元,2核4G4M带宽轻量服务器一年297.98元12个月,云服务器ECS包括通用算力型u1、ECS计算型c7、通用型g7和内存型r7均有活动,新手站长分享云服务器详细价格表如下
125 0
阿里云服务器租用费用_优惠价格表
|
传感器 计算机视觉
多级式多传感器信息融合中的状态估计(Matlab代码实现)
多级式多传感器信息融合中的状态估计(Matlab代码实现)
303 0