时间复杂度

￡神魔★判官ぃ 2022-09-17 12:26 221阅读 0赞

几种排序算法的思想很容易掌握，就是对应的时间复杂度，究其原因就是对时间复杂度是什么，如何定义计算还不知道，那么时间复杂度是如何计算的呢？请看下文。

在说时间复杂度之前要说一下算法，算法是为解决某问题而采取的**具体的**，**有限**的**操作步骤**，既然算法是操作步骤，那么步骤**占用计算机资源的多少**就决定了算法的效率。而计算机资源中有时间资源（处理器）和空间资源（存储器），因此时间复杂度是描述算法效率的标准中的一种。

# 什么是时间复杂度 #

算法中，操作重复执行的次数为算法的时间度量。

设f(n)为描述一个算法重复执行次数的函数，这个算法的时间复杂度即为O(f(n))。这里只需求的函数（f(n)）的增长率。

例题1：

f(n)=n^3+3n        O(f(n))=n^3

f(n)=2                 O(f(n))=1

f(n)=logn+n        O(f(n))=logn

# 如何求解 #

现在如果给定我们一个算法的函数，我们肯定可以特别轻松的写出时间复杂度，但是，函数往往不直接给我们，给我们的是一段代码，我们是否很容易的求出时间复杂度呢？

如下：

例题2.1：

for(i=1;i<=n;++i){ for(j=1;j<=n;++j){ ++x; s+=x; } }

分析： 1）第一个for循环重复的次数为n

2）第二个for重复的次数也为n

3）两个for是嵌套的，程序总的重复次数为n^2

4）时间复杂度即为n^2

例题2.2：

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

分析：1）设重复的次数为m

2）i=1 循环一次i的值都乘以2， m次循环后i的值就不满足小于等于n了，得函数i\*(2^m)>n （i=1）

3）求得重复次数m=log2(n/i)，即得时间复杂度

说明：上题中i如果不为1时，时间复杂度还是log2(n/i)，原因是求的是函数的增长率。

好了，现在我们知道了如何去求时间复杂度的函数及时间复杂度，单个的函数能求出来，那么多个函数在一块呢？就好比我们会算加法、减法和乘法，那么混合运算怎么算呢？ 复合的程序中就能写出多个时间复杂度的函数，整个函数的时间复杂度如何计算就好比混合运算的优先级，是有规则的，请继续看：

# 时间复杂度的表示法则 #

##    加法法则： ##

针对并列程序

O(f(n1))+O(f(n2))=O(  max(f(n1)，f(n2))  )

##    乘法法则： ##

针对嵌套程序

O(f(n1))\*O(f(n2))=O( f(n1)\*f(n2) )

特例：若其中有一个为常数c

f(n1)=c  O(f(n1))\*O(f(n2))=O( c\*f(n2) ) = O( f(n2) )

例3：

{ for ( int i = 0; i < m; i++ ) { sum[i] = 0; for ( int j = 0; j < n; j++ ) { sum[i] += x[i][j]; } } for ( i = 0; i < m; i++ ) { System.out.println(i); } }

分析： 1）嵌套的两个for循环，用乘法法则得：O(m\*n)

2）第三个for循环，时间复杂度为O(m)

3）利用加法法则得：时间复杂度为O(  max(O(m\*n)，O(m))  )

发表评论取消回复

表情：

评论列表（有 0 条评论，221人围观）

还没有评论，来说两句吧...

相关阅读

相关时间复杂度

**时间复杂度** **一、时间复杂度的定义** 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函...

以你之姓@/ 2024年04月18日 11:04/ 0 赞/ 93 阅读

相关搞懂时间复杂度、时间复杂度

文章目录写在前面 1、数学中的log什么意思？ 2、时间复杂度 2.1、用T(n)表示程序执行次数

末蓝、/ 2023年10月08日 12:48/ 0 赞/ 81 阅读

相关时间复杂度_空间复杂度

时间复杂度\_空间复杂度主要说明以下3点： 1.算法效率 2.时间复杂度 3.空间复杂度一、算法效率算法效率分析分为两种：第一种是时间效率，第二种

朱雀/ 2023年06月29日 15:59/ 0 赞/ 199 阅读

相关时间复杂度

转载自：[https://blog.csdn.net/itachi85/article/details/54882603][https_blog.csdn.net_itach

约定不等于承诺〃/ 2022年12月26日 08:10/ 0 赞/ 267 阅读

相关时间复杂度

常见的时间复杂度 <table> <thead> <tr> <th>复杂度名称</th> <th>具体表示</th> </tr> </

叁歲伎倆/ 2022年12月04日 01:11/ 0 赞/ 237 阅读

相关时间复杂度

几种排序算法的思想很容易掌握，就是对应的时间复杂度，究其原因就是对时间复杂度是什么，如何定义计算还不知道，那么时间复杂度是如何计算的呢？请看下文。在说

￡神魔★判官ぃ/ 2022年09月17日 12:26/ 0 赞/ 222 阅读

相关时间复杂度

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_

た入场券/ 2022年08月28日 13:55/ 0 赞/ 198 阅读

相关时间复杂度

时间复杂度 1. 概念用来表示一个算法的理论上的耗时时间 2. 时间频度一个算法中，语句执行的次数，被称为时间频度T(n) 3.时间复杂度存在

蔚落/ 2022年03月21日 09:31/ 0 赞/ 285 阅读

相关时间复杂度？？

O(1) < O(log n) < O(n) < O（nlog n）< O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) 时间复杂度

傷城~/ 2021年10月01日 04:02/ 0 赞/ 422 阅读

相关时间复杂度

什么是时间复杂度 > 算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函

喜欢ヅ旅行/ 2021年06月10日 20:40/ 0 赞/ 525 阅读