复杂度分析

news/2024/5/28 3:47:08/文章来源:https://blog.csdn.net/wozaibohaibian/article/details/133420339

文章目录

  • 如何分析、统计算法的执行效率和资源消耗?
    • 为什么需要复杂度分析?
      • 测试结果非常依赖测试环境
      • 测试结果受数据规模的影响很大
    • 大O复杂度表示法
    • 时间复杂度分析
      • 只关注循环次数最多的一段代码
      • 加法法则:总复杂度等于量级最大的那段代码的复杂度
      • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
    • 几种常见的复杂度分析实例
      • 1.O(1)
      • 2.O(logn) O(nlogn)
      • 3.O(m+n)、O(m*n)
    • 空间复杂度分析
    • 常见复杂度
    • 思考
    • 最好最坏时间复杂度
    • 平均情况时间复杂度
    • 均摊时间复杂度
    • 思考

如何分析、统计算法的执行效率和资源消耗?

为什么需要复杂度分析?

测试结果非常依赖测试环境

  1. 同样一段代码,用不同的处理器,执行时间不同
  2. 不同的代码在不同的机器上运行,执行时间不同

测试结果受数据规模的影响很大

  1. 测试数据规模太小,测试结果无法真实的反应算法的性能。
  2. 需要一个不用具体的测试数据来测试,就可以粗略地估计算法的执行效率,这就需要复杂度分析。

大O复杂度表示法

 int cal(int n) {int sum = 0;int i = 1;for (; i <= n; ++i) {sum = sum + i;}return sum;}
  • 如下代码表示1到n的累加和,估算这段代码的执行时间。
  • CPU的角度看,每行代码都执行类似的操作:读数据-运算-写数据
  • 假设每行代码执行的时间相同,都是unit_time,所以这段代码的执行时间就是(2n+2)*unit_time。
  • 所有代码的执行时间T(n)与每行代码的执行次数成正比。

所有代码的执行时间T(n)与每行代码的执行次数n成正比

image

  • T(n)代表代码执行的时间
  • n表示数据规模的大小
  • f(n)代表每行代码执行的次数总和
  • 大O时间复杂度实际上并不具体表示代码真正执行的时间
  • 表示代码执行时间随数据规模增长的变化趋势,也称渐进时间复杂度,简称时间复杂度
  • 当n很大时,公式中的低阶、常量、系数三部分并不左右增长趋势,都可以忽略

时间复杂度分析

只关注循环次数最多的一段代码

大O这种复杂度只是表示一种变化趋势。所以,我们在分析一个算法,一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的n的量级,就是整段要分析代码的时间复杂度。

加法法则:总复杂度等于量级最大的那段代码的复杂度

乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

int cal(int n){int ret = 0;int i = 1;for(;i<=n;++i){ret = ret+f(i);}
}
inf f(int n){int sum = 0;int i=1;for(;i<=n;++i){sum = sum+1;}return sum;
}

我们可以把乘法法则看成是嵌套循环。

几种常见的复杂度分析实例

  • 多项式量级
    • 常量阶O(1)
    • 对数阶O(logn)
    • 线性阶O(n)
    • 线性对数阶O(nlogn)
    • 平方阶O(n^2) 立方阶O(n^3) k次方阶O(n^k)
  • 非多项式量级
    • 指数阶O(2^n)
    • 阶乘阶O(n!)

1.O(1)

O(1)只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码。如下代码,即便有3行,时间复杂度也是O(1),而不是O(3)

int i = 8;
int j = 10;
int sum - i+j;

一般情况下,只要算法中不存在循环语句、递归语句,即便有成千上万行的代码,其时间复杂度也为O(1)

2.O(logn) O(nlogn)

对数时间复杂度非常常见,同时也是最难分析的一种时间复杂度。举例如下:

int i = 1
while(i <= n){i=i*2;
}

从代码中可以看出,变量 i 的值从 1 开始取,每循环一次就乘以 2。当大于n时,循环结束。实际上变量i的取值就是一个等比数列
image
所以这段代码的时间复杂度就是O(log2n),通过换底公式,我们忽略对数的“底”,统一表示为O(logn),根据乘法法则,可以很容易理解O(nlogn),比如归并排序、快速排序的时间复杂度都是O(nlogn)

3.O(m+n)、O(m*n)

代码的复杂度由两个数据的规模来决定,代码如下:

int cal(int m,int n){int sum_1 = 0;int i = 1;for(;i<m;++i){sum_1 = sum_1+i;}int sum_2 = 0;int j = 1;for(;j<n;++j){sum_2 = sum_2+j;}return sum_1+sum_2;
}

m和n表示两个数据规模,我们事先无法评论m和n谁的量级大,所以我们在表示复杂度的时候,就不能简单的用加法法则,省略掉其中一个。所以上面代码的时间复杂度就是O(m+n)。但是乘法法则继续有效。

空间复杂度分析

时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。 类比一下,空间复杂度就是渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系。

void pring(){int i = 0;int[] a = new int[n];for(;i<n;++i){a[i] = i*i;}for(i=n-1;i>=0;--i){print out a[j];}
}

第二行代码中,我们申请了一个空间存储变量i,但是它是常量级别的,跟数据规模n没有关系,所以可以忽略。第三行申请了一个大小为n的int类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度就是O(n)

常见复杂度

image

思考

有人说,我们项目之前都会进行性能测试,再做代码的时间、空间复杂度分析,是不是多此一举呢?每段代码都分析一下时间复杂度、空间复杂度,是不是很浪费时间呢?你怎么看待这个问题?

  1. 渐进时间、空间复杂度分析为我们提供了一个很好的理论分析方向,并且它是宿主平台无关的,能够让我们对我们程序或算法有一个大致的认识,让我们知道,比如在最坏下程序的执行效率如何,同时也为我们提供了一个不错的桥梁,我们可以说,算法1的时间复杂度是O(n),算法2的时间复杂度为O(logN),这样我们立刻就对不同的算法有了一个“效率”上的感性认识。
  2. 渐进时间、空间复杂度分析只是一个理论模型,只能提供给粗略的估计分析,我们不能直接断定就觉得O(logN)的算法一定优于O(n),针对不同的宿主环境,不同的数据集,不同的数据量的大小,在实际应用上面可能真正的性能会不同,个人觉得,针对不同的实际情况,进而进行一定的性能基准测试是很有必要的,比如在统一一批手机上(同样的硬件,系统等等)进行横向基准测试,进而选择适合特定应用场景下的最有算法。
  3. 渐进式时间,空间复杂度分析与性能基准测试并不冲突,而是相辅相成的,但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时间复杂度程序,所以在实际编程中,时刻关心理论时间,空间度模型是有助于产出效率高的程序的,同时,因为渐进式时间,空间复杂度分析只是提供一个粗略的分析模型,因此也不会浪费太多时间,重点在于在编程时,要具有这种复杂度分析的思维。

最好最坏时间复杂度

//n表示array数组的大小
int find(int[] array,int n,int x){int i = 0;int pos = -1;for(int i=0;i<n;++i){if(array[i] == x){pos = i;}}return pos;
}

你应该可以看出来,这段代码要实现的功能是,在一个无序的数组(array)中,查找变量x出现的位置。如果没有找到,就返回-1。这段代码的时间复杂度为O(n),我们在寻找的过程中如果提前找到了,可以提前结束,所以可以优化

int find(int[] array,int n;int x){int i = 0;int pos = -1;for(;i<n;++i){if(array[i] == x){pos = x;break;}}return pos;
}

那么问题就来了,优化后的代码时间复杂度还是O(n)吗?

  1. 如果数组中的第一个元素刚好是要查找的变量x,那就不需要继续遍历剩下的n-1个数据了,时间复杂度就是O(1)
  2. 如果数组中不存在变量x,那我们就需要把整个数组都遍历一遍,时间复杂度就变成O(n)

不同情况下,这段代码的时间复杂度是不一样的。
所以需要引入三个概念:最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度。
最好:最理想情况下,执行这段代码的时间复杂度。
最坏:最糟糕的情况下,执行这段代码的时间复杂度。

平均情况时间复杂度

  • 最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的的代码复杂度,发生的概率其实并不大。为了更好地表示平均情况下的复杂度,我们需要引入另一个概念:平均情况时间复杂度,后面我简称为平均时间复杂度。
  • 要查找的变量x在数组中的位置,有n+1种情况:在数组的0~n-1个位置和不在数组中。每种情况下,查找需要遍历的元素个数累加起来,然后再除以n+1,就可以得到需要遍历的元素个数的平均值。

image

平均时间复杂度为O(n)

这个结论是正确的,但是计算过程稍微有点问题,因为这n+1中情况,出现的概率并不是一样的。

假设在数组中与不在数组中的概率都为1/2,另外0n-1之间的概率一样,为1/n,所以根据概率乘法法则,要查找的数据出现在0n-1中任意位置的概率就是1/(2n)。

所以将每种情况发生的概率也考虑进去,那平均时间复杂度的计算过程就变成了这样:

image

这个值就是概率论中的加权平均,也叫作期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度期望时间复杂度

均摊时间复杂度

均摊时间复杂度对应的分析方法,摊还分析(或者叫平摊分析)。

均摊时间复杂度应用的场景更加特殊,更加有限。

int[] array = new int[n];
int count = 0;void insert(int val){if(count == array.length){int sum = 0;for(int i=0;i<array.length;++1){sum = sum+1;}array[0] = sum;count = 1;}array[count] = val;++count;
}
  • 最好情况时间复杂度O(1)
  • 最坏情况下,数组中没有空闲空间,需要先做一遍数组的遍历求和,然后将数据插入,所以最坏情况时间复杂度为O(n)
  • 平均时间复杂度为O(1)

概率论方法分析:
假设数组长度为n,可以分为n种情况,每种情况的时间复杂度为O(1),除此之外还有一种额外的情况,就是在数组没有空闲空间时插入一个数据,这个时候的时间复杂度为O(n)。而且这n中情况发生的概率是一样的,都是1/(n+1),所以根据加权平均的计算方法,所以平均时间复杂度为:

image

如何使用摊还分析来分析均摊时间复杂度呢?

每一次O(n)的插入操作,都会跟着n-1次O(1)的插入操作,所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上,均摊下来,这一组连续的操作的均摊时间复杂度就是O(1)。这就是均摊分析的大致思路。

均摊时间复杂度就是一种特殊的平均时间复杂度。

思考

int[] array = new int[10];
int len = 10;
int i = 0;void add(int element){if(i>= len){int[] new_array = new int[len*2];for(int j=0;j<len;++j){new_array[j] = array[j]; }array = new_array;len = len*2;}array[i] = element;++i;
}
  • 最好:O(1)
  • 最坏:O(n)
  • 平均:O(1)
  • 均摊:O(1)

文章来源于极客时间前google工程师−王争专栏。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ldbm.cn/p/138265.html

如若内容造成侵权/违法违规/事实不符,请联系编程新知网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

分布式网络在移动医疗场景中的应用

随着医疗信息化建设实践的深入&#xff0c;越来越多的医疗机构开始借助网络信息技术改善其运营及管理模式&#xff0c;为患者提供更高质量、更高效率、更加安全体贴的医疗服务。移动医疗便是在此背景下产生的新业务需求。 常见的移动医疗场景 住院部&#xff1a;移动查房、智…

力扣 -- 44. 通配符匹配

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:bool isMatch(string s, string p) {int ms.size();int np.size();//为了调整映射关系s s;p p;//多开一行多开一列vector<vector<bool>> dp(m1,vector<bool>(n1,false));//初始化//dp[0]…

【GDB】使用 GDB 自动画红黑树

阅读本文前需要的基础知识 用 python 扩展 gdb python 绘制 graphviz 使用 GDB 画红黑树 前面几节中介绍了 gdb 的 python 扩展&#xff0c;参考 用 python 扩展 gdb 并且 python 有 graphviz 模块&#xff0c;那么可以用 gdb 调用 python&#xff0c;在 python 中使用 grap…

数据结构--双链表

今天我们来用数组来模拟双链表 为什么要数组模拟呢&#xff1f; 因为用数组模拟的双链表&#xff0c;运行速度更快&#xff0c;做算法题更加舒服 用数组模拟双链表的内容 1、同样也有首尾结点 2、相邻的两个节点是相互指向的 3、可以看成两个方向相反的单链表相互连接在一起 …

【项目】Http服务器

【项目】Http服务器 项目简介 背景&#xff1a; http协议被广泛使用&#xff0c;从移动端&#xff0c;pc端浏览器&#xff0c;http协议无疑是打开互联网应用窗口的重要协议&#xff0c;http在网络应用层中的地位不可撼动&#xff0c;是能准确区分前后台的重要协议。 描述&a…

Android Studio插件版本与Gradle 版本对应关系

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 目录 一、导读二、概览三、Gradle各版本对应关系3.1 Gradle 版…

26663-2011 大型液压安全联轴器 课堂随笔

声明 本文是学习GB-T 26663-2011 大型液压安全联轴器. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 本标准规定了大型液压安全联轴器的分类、技术要求、试验方法及检验规则等。 本标准适用于联接两同轴线的传动轴系&#xff0c;可起到限制…

【AntDesign】封装全局异常处理-全局拦截器

[toc] 场景 本文前端用的是阿里的Ant-Design框架&#xff0c;其他框架也有全局拦截器&#xff0c;思路是相同&#xff0c;具体实现自行百度下吧 因为每次都需要调接口&#xff0c;都需要单独处理异常情况&#xff08;code !0&#xff09;&#xff0c;因此前端需要对后端返回的…

问题记录 springboot 事务方法中使用this调用其它方法

原因: 因为代理对象中调用了原始对象的toString()方法,所以两个不同的对象打印出的引用是相同的

解决Linux服务器中docker访问报127.0.0.1:2375拒绝连接 (Connection refused)的问题

解决问题&#xff1a; org.apache.hc.client5.http.HttpHostConnectException: Connect to http://127.0.0.1:2375 [/127.0.0.1] failed: 拒绝连接 (Connection refused) 解决思路&#xff1a; 在Linux服务器中&#xff0c;Docker是远程访问的&#xff0c;因此需要开放2375端口…

Java 基于 SpringBoot 的在线学习平台

1 简介 基于SpringBoot的Java学习平台&#xff0c;通过这个系统能够满足学习信息的管理及学生和教师的学习管理功能。系统的主要功能包括首页&#xff0c;个人中心&#xff0c;学生管理&#xff0c;教师管理&#xff0c;课程信息管理&#xff0c;类型管理&#xff0c;作业信息…

时序分解 | Matlab实现SSA-VMD麻雀算法优化变分模态分解时间序列信号分解

时序分解 | Matlab实现SSA-VMD麻雀算法优化变分模态分解时间序列信号分解 目录 时序分解 | Matlab实现SSA-VMD麻雀算法优化变分模态分解时间序列信号分解效果一览基本介绍程序设计参考资料 效果一览 基本介绍 SSA-VMD麻雀搜索算法SSA优化VMD变分模态分解 可直接运行 分解效果好…

华为云云耀云服务器L实例评测 | 实例评测使用之体验评测:华为云云耀云服务器安全加固/防范黑客攻击

华为云云耀云服务器L实例评测 &#xff5c; 实例评测使用之体验评测&#xff1a;华为云云耀云服务器安全加固/防范黑客攻击 介绍华为云云耀云服务器 华为云云耀云服务器 &#xff08;目前已经全新升级为 华为云云耀云服务器L实例&#xff09; 华为云云耀云服务器是什么华为云云…

【项目】在线音乐播放器测试报告

目录 项目背景 项目功能 测试计划 功能测试 登录页面的测试 测试用例 测试结果 注册页面的测试 测试用例 测试结果 音乐列表页面的测试 测试用例 测试结果 出现的bug 搜索功能的bug 问题解决 删除功能的bug 问题解决 喜欢列表页面的测试 测试用例 测试结果…

stc8H驱动并控制三相无刷电机综合项目技术资料综合篇

stc8H驱动并控制三相无刷电机综合项目技术资料综合篇 🌿相关项目介绍《基于stc8H驱动三相无刷电机开源项目技术专题概要》 🔨停机状态,才能进入设置状态,可以设置调速模式,以及转动方向。 ✨所有的功能基本已经完成调试,目前所想到的功能基本已经都添加和实现。引脚利…

python进制转换

""" 基数:有几个数 0b 2进制: 0、1 基数是:2 0o 8进制: 0、1、2、3、4、5、6、7 基数是:8 0d 10进制: 0到9 基数是:10 0x 16进制: 0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F 基数是:16十进制转二进制: bin() 十进制转八进…

安卓玩机-----给app加注册码 app加弹窗 云注入弹窗

在对接很多工作室业务中有些客户需要在他们自带的有些app中加注册码或者验证码的需求。其实操作起来也很简单。很多反编译软件有自带的注入功能。例如注入弹窗。这个是需要对应的注册码来启动应用。而且是随机id。重新安装app后需要重新注册才可以继续使用&#xff0c;原则上可…

仿真数据检查器如何比较数据

可以定制仿真数据检查器比较过程&#xff0c;以多种方式满足您的需求。在比较各运行时&#xff0c;仿真数据检查器会执行以下操作&#xff1a; 根据对齐设置&#xff0c;对齐基线运行和比较项运行中的信号对组。 仿真数据检查器不会比较无法对齐的信号。 根据指定的同步方法同…

前端开发如何更好的避免样式冲突?级联层(CSS@layer)

本文主要讲述了CSS中的级联层&#xff08;CSSlayer&#xff09;&#xff0c;讨论了级联以及级联层的创建、嵌套、排序和浏览器支持情况。级联层可以用于避免样式冲突&#xff0c;提高代码可读性和可维护性。 一、什么是级联层(Cascade Layers)&#xff1f; 1.1 级联层的官方定…

网络子网划分练习

网络子网划分练习 1.背景&#xff1a; 在一个仓储企业网络拓朴结构如图1-所示&#xff0c;该企业占地500亩。有五层办公楼1栋&#xff0c;大型仓库10栋。每栋仓库内、外部配置视频监控16台&#xff0c;共计安装视频监控160台&#xff0c;Switch A、服务器、防火墙、管理机、Rou…