什么是时间复杂度-程序员宅基地

技术标签: 数据结构  

开门见山 解决问题

算法的时间复杂度,是一个用于度量一个算法的运算时间的一个描述,本质是一个函数,根据这个函数能在不用具体的测试数据来测试的情况下,粗略地估计算法的执行效率,换句话讲时间复杂度表示的只是代码执行时间随数据规模增长的变化趋势。

常用大O来表述,这个函数描述了算法执行所要时间的增长速度,记作f(n)。算法需要执行的运算次数(用函数表示)记作T(n)。存在常数 c 和函数 f(n),使得当 n >= c 时 T(n) <= f(n),记作 T(n) = O(f(n)),其中,n代表数据规模也就是输入的数据。常见排序复杂度如图:在这里插入图片描述

大O表示法

大O符号,又叫做道朗符号,是数学中用另一个较为简单的函数去描述函数渐进行为的一个符号,用来刻画被截断的无穷级数尤其是渐近级数的剩余项。

常见复杂度量级
分类 记作
常量阶 O(1)
对数阶 O(logn)
线性阶 O(n)
线性对数阶 O(nlogn)
n方阶 O(nⁿ)
指数阶 O(2ⁿ)
阶乘阶 O(n!)

时间复杂度如何计算

  1. 常量阶:只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度都记作 O(1)。或者说,一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。
  2. 对数阶:
 i=1;
 while (i <= n)  {
    
   i = i * 2;
 }

分析上段代码,i的取值是一个首项为1,公差为2的等比数列:
2º·2¹·2²·2³····2ⁿⁿ = n,其中nn即为项数,求对数即 nn=log₂n。时间复杂度为O(log₂n)。

  1. 线性阶、n方阶:一般情况下,如果循环体内循环控制变量为线性增长,那么包含该循环的算法的时间复杂度为O(n),线性阶嵌套线性阶的算法时间复杂度为O(nⁿ),涉及下文乘法法则。
  2. 线性对数阶:当一个线性阶代码段法嵌套一个对数阶代码段,该算法的时间复杂度为O(nlogn)
  3. 指数阶和阶乘阶:根据函数,随着n的增加,运行时间会无限急剧增加,因此效率非常低下。

3个分析时间复杂度的方法

  1. 最大阶法则:忽略式子中的常量,低阶,系数,只计算最大阶的量级。
    说白了就只关注循环次数最多的代码段。

 int fun(int n) {
    
   int sum1 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
    
     sum = sum + i;
   }
   for (; i <= n; ++i) {
    
        for (; i <= n; ++i) {
    
		     sum + = i+j;
  		 }
   }
   return sum;
 }

代码本身没有意义,只是为了举例,上述代码的时间复杂度为O(n²)。

  1. 加法法则:总复杂度等于量级最大代码段的复杂度,公式:

T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))


int fun(int n) {
    
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
    
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
    
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
    
     j = 1; 
     for (; j <= n; ++j) {
    
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

三段代码的复杂度分别是O(1)、O(n)、O(n²),根据法则:T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))。即为O(n²)。

  1. 乘法法则:嵌套代码复杂度等于嵌套内外代码复杂度之积。公式:

T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))。


int fun1(int n) {
    
   int ret = 0; 
   int i = 1;**加粗样式**
   for (; i < n; ++i) {
    
     ret = ret + fun2(i);
   } 
 } 
 
 int fun2(int n) {
    
  int sum = 0;
  int i = 1;
  for (; i < n; ++i) {
    
    sum = sum + i;
  } 
  return sum;
 }

fun1方法中,忽略掉fun2()的调用复杂度为O(n)。fun2方法的时间复杂度是O(n),根据法则,T(n) = T1(n) * T2(n) = O(n*n) = O(n²)。

其中比较特殊的一种不符合上述3个法则:

int fun(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 确定,加法法则应更正为:T1(m) + T2(n) = O(f(m) + g(n)),即时间复杂度为O(m+n)。


时间复杂度的最好、最坏、平均和均摊

最好时间复杂度:在最理想的情况下,执行这段代码的时间复杂度。

最坏时间复杂度:在最糟糕的情况下,执行这段代码的时间复杂度。

平均时间复杂度:考虑各种情况及其发生的概率,得到的时间复杂度。

均摊时间复杂度:均摊时间复杂度是一种特殊的平均复杂度,把耗时多的复杂度均摊到耗时低的复杂度,得到的时间复杂度。

快速排序最好时间复杂度计算

快速排序最优的情况就是每一次取到的元素都刚好平分整个数组。 此时的时间复杂度公式则为:

T[n] = 2T[n/2] + f(n);

T[n/2]为平分后的子数组的时间复杂度,f[n] 为平分这个数组时所花的时间;下面来推算下,在最优的情况下快速排序时间复杂度的计算(用迭代法):

** T[n] = 2T[n/2] + n ——————————————— 第一次递归,令:n = n
T[n] = 2 { 2 T[n/4] + (n/2) } + n ———————————第二次递归,令:n = n/2= = 2^2 T[ n/ (2^2) ] + 2n
T[n] = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} + 2n ———————第三次递归 ,令:n = n/(2^2)= 2^3 T[ n/ (2^3) ] + 3n
T[n] = 2^m T[1] + mn ———————————————第m次递归(m次后结束), 令:n = n/( 2^(m-1) )**

当最后平分的不能再平分时,也就是说把公式一直往下跌倒,到最后得到T[1]时,说明这个公式已经迭代完了(T[1]是常量了)。

得到:

T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn;
T[n] = 2^m T[1] + mn ;其中m = logn;
T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ;

其中n为元素个数,又因为当n >= 2时:nlogn >= n (也就是logn > 1),所以取后面的 nlogn;

综上所述:快速排序最优的情况下时间复杂度为:O( nlogn )

摊还分析法

通过摊还分析法得到的时间复杂度为均摊时间复杂度。

大致思路:每一次O(n)都会跟着n次O(1),所以把耗时多的复杂度均摊到耗时低的复杂度。得到的均摊时间复杂度为O(1)。

应用场景:均摊时间复杂度和摊还分析应用场景较为特殊,对一个数据进行连续操作,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度较高。而这组操作其存在前后连贯的时序关系。

这个时候我们将这一组操作放在一起分析,将高复杂度均摊到其余低复杂度上,所以一般均摊时间复杂度就等于最好情况时间复杂度。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41297896/article/details/104223612

智能推荐

回溯法:最优装载问题_回溯法最优装载问题-程序员宅基地

文章浏览阅读1.1w次。回溯法对解空间进行深度优先搜索,在一般情况下可用递归方法实现回溯法。 空间树理解: 假设装载的集装箱n=3,则空间树可以表示为上图,就是1表示装入该集装箱,0表示不装入该集装箱,最优装载问题就是在这些空间树里,寻找最优子结构。我想看到此处应该不难理解。集体测试代码:public class bestLoading { static int n;//集装箱数量 static i_回溯法最优装载问题

2019年开源年会,大学生体验心得【附图】_大学生做开源项目感想-程序员宅基地

文章浏览阅读3.5k次。2019年开源年会,大学生心得Day One上午大会下午分会场李辉老师开源大学大妈的演讲Deepin的小结Day Two主要讲一下 大会心得以及分场心得(内容为:我喜欢的话题)下面可能会出现大佬的照片,侵删Day One上午大会2019年中国开源年会在上海华东师范大学召开,9.20大会开始了大会致辞时,最喜欢的是庄表伟老师对开源的解释我们的原则:贡献,共识,共享我们的使命:开源治..._大学生做开源项目感想

为什么 unity 中正方体网格的顶点数量为 24?_unity 立方体为什么有24个顶点-程序员宅基地

文章浏览阅读2.1k次,点赞5次,收藏5次。unity 中正方体网格的顶点数量为 24, 面片为 12:1.首先看下在 3Dmax 中的顶点数量为 8,面片(四角面片)为 6(图中显示三角形数量是为了方便我们计算):2.模型导入unity 之后,会对四边形(或多边形)进行处理,转成三角面片。因此,对于上述栗子来说,面数 = 原面数 * 2 = 12;3.unity 中显示的顶点数和面片数是实际传递给 GPU 的数量。由..._unity 立方体为什么有24个顶点

java swing 外观框架_【GUI】一、Swing外观框架BeautyEye使用-程序员宅基地

文章浏览阅读635次。一、Swing外观框架BeautyEye使用1.1 导包1.2 使用BeautyEye L&Fpublic static void main(String[] args) {EventQueue.invokeLater(new Runnable() {public void run() {// 国人牛逼主题,值得学习// 初始化字体InitGlobalFont(new Font("微软雅黑..._java swing漂亮界面框架

如何实现WebView和js页面的交互_document.getelementsbytagname('html')[0].innerhtml-程序员宅基地

文章浏览阅读6.9k次。WebView默认是不支持js的,要支持js,必须要添加如下设置: WebSettings settings = webView.getSettings(); settings.setJavaScriptEnabled(true);1.如何实现js页面通过WebView调用Android app写好的代码呢?通过webView.addJavascriptInterface(O_document.getelementsbytagname('html')[0].innerhtml)

容灾数据复制技术的比较_caxp-程序员宅基地

文章浏览阅读3.4k次,点赞2次,收藏6次。容灾数据复制技术的比较 一、概述近几年来,容灾已经成为信息数据中心建设的热门课题。很多容灾技术也快速发展起来,对用户来说也有很广阔的选择余地。但由于容灾方案的技术复杂性和多样性,一般用户很难搞清其中的优劣以确定如何选择最适合自己状况的容灾解决方案。本文我们就容灾建设中的备份及复制技术做一个初步探讨,希望能对客户的数据中心容灾建设提供一些参考。目前有很多种容灾技术,分类也比较复杂_caxp

随便推点

自己拥有一台服务器可以做哪些很酷的事情?_自架服务器 可以干什么-程序员宅基地

文章浏览阅读8.2k次,点赞34次,收藏101次。自己拥有一台服务器可以做哪些很酷的事情?为什么选择云服务器如何选择云服务器可以做哪些很酷的事情**个人博客****个人网盘****云桌面*.._自架服务器 可以干什么

scala,实现case class类的时候 业务字段过多导致的异常。不能超过22个字段_case class 字段数量-程序员宅基地

文章浏览阅读1.9k次。一、背景1、在scala-2.10.x版本种,case class的元素超过22个以后即会编译报错2、有些业务场景下,需要超过22个元素的值我们项目当中日志一共有105个字段,在对原始日志进行处理转换成parquet文件的过程中,我们使用的方法是定义一个case class类,将这105个字段封装到这个对象里面,基于这种方式构建的DataFrame。结果运行的时候报错了,之后我们..._case class 字段数量

日志审计系统的基本原理与部署方式-程序员宅基地

文章浏览阅读2.6k次。来源 |http://rrd.me/g6P3V日志审计系统简介什么是日志审计?综合日志审计平台,通过集中采集信息系统中的系统安全事件、用户访问记录、系统运行日志、系统运行状态等各类信息,..._日志审计的原理功能部署方式

用JavaScript中的计时事件制做一个时钟_用js写一个时间-程序员宅基地

文章浏览阅读948次。1:首先创建一个div盒子用来显示时钟,然后给它设置一些简单的样式:2:然后来写js:首先封装一个方法,随便命个名,比如:startTime(),然后在方法中写代码:获取当前时间,也就是new Date(),然后获取当前时间的小时,分钟,毫秒,因为获取到的小时,分钟,毫秒都是数字,并不会在前面自动补0,比如8分,那显示的就是8分,并不会跟我们看到的时钟一样是08分,所以要再封装一个方法,这个..._用js写一个时间

使用curl测试websocket服务是否能正常连入_curl websocket-程序员宅基地

文章浏览阅读2.7w次。部分场景,需要从后台验证websocket服务是否能连入,判断防火墙是否开通,反向代理是否配置正确参考https://gist.github.com/htp/fbce19069187ec1cc486b594104f01d0 curl --include \ --no-buffer \ --header "Connection: Upgrade_curl websocket

发烧友实测 | 用飞凌OKA40i-C开发板玩转FFmpeg_oka40i调用qcamera-程序员宅基地

文章浏览阅读483次。FFmpeg可以支持实时视频流的发送和接收,从而可以把OKA40i-C开发板上的视频实时发送到PC上,由PC上的软件实时接收并显示。我们使用了两种型号的USB摄像头,按照手册说明使用内置的uvccamera程序进行测试,不过都没有成功,得到的错误信息如下图所示。飞凌嵌入式OKA40i-C开发板可以对于1080P的视频压缩达到45fps,所以对USB摄像头的视频压缩应该没有什么压力。前面演示了将MP4文件转换为视频流,我们也可以将USB摄像头采集的内容实时转发到PC上,使用下面的命令行即可。_oka40i调用qcamera