当前位置：首页 > 科技 > 软件

怎么计算我们自己程序的时间复杂度

来源：责编：时间：2024-05-20 17:55:17 89观看

导读知道自己写的程序的时间复杂度，有利于我们写出能够高效运行的程序。程序是由一个个函数组成的，有些简单的由几个基础运算组成的函数大家一眼就能看出来它的时间复杂度，但是大部分函数没那么简单，只要函数里面涉及到了循环

知道自己写的程序的时间复杂度，有利于我们写出能够高效运行的程序。

程序是由一个个函数组成的，有些简单的由几个基础运算组成的函数大家一眼就能看出来它的时间复杂度，但是大部分函数没那么简单，只要函数里面涉及到了循环、外部函数调用甚至递归的时候它的时间复杂度就没那么容易分析啦。

这篇文章的内容，可以帮你快速推导出程序代码的时间复杂度。

要分析程序的时间复杂度，首先还是要确定时间复杂度的度量标准— —英文文档里通常会用 metric 这个单词来表示，这个标准规定了在函数中平铺展开的代码、循环中的代码、有函数调用的代码、以及递归调用的代码的时间复杂度的测量方式。

Big O Notations

如何计算程序的时间复杂度呢？最常用的度量方式叫做 Big O Notations 翻译过来叫大O标记法。

使用大O标记法前要先了解它的几个要点：

相同配置的计算机进行一次基本运算的时间是一定的，因此我们将程序基本运算的执行次数作为时间复杂度的衡量标准。
时间复杂度是对运行次数的错略估计，在计算时可以只考虑对运行时间贡献大的语句而忽略运行次数少的语句。比如 O(3 * n2 + 10n + 10) 会被统计成 O(n2)。
比如有些涉及到排序的程序，执行时间往往依赖于程序的输入，可以分为最好、最坏、平均情况的时间复杂度，这种时候使用大 O 标记法时我们只用关注最坏的情况，因为最坏情况对衡量程序效率的好坏具有实际意义。

在大O标记法中，常见的时间复杂度有一下几类。

常数阶:常数阶的复杂度通常用O(1)表示，不是说程序只有一行基础代码运行，它的意思是不管程序的输入是什么程序都会运行一个固定数量的运算，这个数可以是任何常数5、100、200都行，重点是他不会随输入的增长才被统计称 O(1)
多项式阶：很多算法的时间复杂度是 O(n)、O(n2)、O(n3)这样的多项式。
指数阶：指数阶的时间复杂度用O(2n) 、 O(nn) 等表示，这种程序运行效率极差，是程序员写代码一定要避开的大坑。
对数阶：对数阶的程序运行效率较高，通常用O(logn)、 O(n log n) 等表示。

它们的关系如下：

图片

从上面的图我们可以看到，O(1)是最高效最稳定的，完全不受输入数据尺寸增长的影响，指数阶随着输入的增加而爆增，而对数阶则增长缓慢。

按照时间复杂度从低到高排序：

O(1) < O(logn) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

在写程序时，我们要注意时间复杂度增量的问题，尽量避免爆炸级增长。

了解完时间复杂度的大O标记法后，接下来我们看下怎么把我们平时接触的代码转化为其对应的时间复杂度。

顺序语句的复杂度

这是最简单的代码结构，比如说我们有一个下面的计算3个数字的平方和的函数。

function squareSum(a, b, c) {  const sa = a * a;  const sb = b * b;  const sc = c * c;  const sum = sa + sb + sc;  return sum;}

函数中的每个语句都是一个基本运算。每行的时间复杂度为 O(1)。我们把所有语句的时间加起来，它仍然是 O(1)，记住昂，不是O(3)。

O(1)表示程序时常数级的时间复杂度，不管程序的输入是什么程序都会运行数量固定的操作。

注意如果顺序排列的代码中有对函数的调用，复杂度就不是O(1)了，你想知道是多少？

条件语句的复杂度

很少有会有程序代码没有任何条件语句。因为大 O 标记法关注程序运行的的最坏情况，所以对一个类似这样的条件语句：

if (isValid) {  statement1;  statement2;} else {  statement3;}

它的时间复杂度可以按下面这个公式推导出来：

T(n) = Math.max([t(statement1) + t(statement2)], [time(statement3)])

比如说下面这个代码：

if (isValid) {  array.sort();  return true;} else {  return false;}

if代码块中的时间复杂度为O( n log n) — 常用编程语言内置排序算法的时间复杂度，else代码块的时间复杂度为O(1)，那么整个代码的时间复杂度为：

O([n log n] + [n]) => O(n log n)

循环语句的复杂度

线性循环

for (let i = 0; i < array.length; i++) {  statement1;  statement2;}

对于这个例子，循环执行 array.length次，所有与输入数据增长而成比例增长的循环都具有线性—常数阶的时间复杂度 O(n)。

对数循环

观察下面的程序：

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

对于这个程序，我们无法确定while 以及 i = i*2 语句运行了多少次，这时可以假设运行了x次，每次运行后i的值为2、22、23… 当while 语句的条件不满足即i = n时结束，也就是2x = n ， x = log2n ，它的时间复杂度近似于O(logn )。

固定次数循环

for (let i = 0; i < 4; i++) {  statement1;  statement2;}

针对固定条件的循环，像上面这个程序一样，无聊时固定循环4次还是 100 次时间复杂度都是 O(1)。

嵌套循环

for (let i = 0; i < n; i++) {  statement1;  for (let j = 0; j < m; j++) {    statement2;    statement3;  }}

假设循环中的语句都是基础操作，没有对函数的调用，那么这个代码有两层嵌套循环，时间复杂度为O(n2)。

循环中有函数调用的时间复杂度

假如我们有这样一个程序：

for (let i = 0; i < n; i++) {  fn1();  for (let j = 0; j < n; j++) {    fn2();    for (let k = 0; k < n; k++) {      fn3();    }  }}

根据 fn1、fn2 和 fn3 函数自身的时间复杂度，整个程序将拥有不同的运行时间。

如果这三个函数它们都是常数阶 O(1)，那么最终的运行时间将为 O(n3)。但是如果只有 fn1 和 fn2 是常数介， fn3 的时间复杂度为 O(n2)，则该程序的运行时间将为 O(n5)。

一般来说，循环中有函数调用，时间复杂度可以用下面这个公式计算：

T(n) = n * [ t(fn1()) + n * [ t(fn2()) + n * [ t(fn3()) ] ] ]

函数递归调用的时间复杂度

function fn(n) { if (n == 1 || n == 2) {   return 1; } return fn(n - 1) + fn(n - 2);}

以上是学算法都学过的斐波那切数列的递归调用实现版本，它的时间复杂度为O(2n) ，所以在平时写代码时在你不确定程序能执行多少次的时候，最好不要轻易使用递归调用。

总结

这篇内容我们梳理了一下不同的时间复杂对大概对应什么样的代码，让我们能更正确地估算自己写的程序的时间复杂度。

本文链接：http://www.28at.com/showinfo-26-89409-0.html怎么计算我们自己程序的时间复杂度

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇：基于Puppeteer实现前端SSR完美接入方案

下一篇： Java引用类型解析：掌握强引用、软引用、弱引用和幻象引用的妙用

标签：

热门焦点

印度登月最关键一步！月船三号今晚进入环月轨道

8月5日消息，据印度官方消息，月船三号将于北京时间今晚21时30分左右开始近月制动进入环月轨道。这是该探测器能够成功的最关键步骤之一，如果成功将开始围
CSS单标签实现转转logo

转转品牌升级后更新了全新的Logo，今天我们用纯CSS来实现转转的新Logo，为了有一定的挑战性，这里我们只使用一个标签实现，将最大化的使用CSS能力完成Logo的绘制与动画效果。新logo
一篇聊聊Go错误封装机制

%w 是用于错误包装（Error Wrapping）的格式化动词。它是用于 fmt.Errorf 和 fmt.Sprintf 函数中的一个特殊格式化动词，用于将一个错误（或其他可打印的值）包装在一个新的错误中。使
Python异步IO编程的进程/线程通信实现

这篇文章再讲3种方式，同时讲4中进程间通信的方式一、 Python 中线程间通信的实现方式共享变量共享变量是多个线程可以共同访问的变量。在Python中，可以使用threading模块中的L
得物宠物生意「狂飙」，发力“它经济”

作者｜花花小萌主近日，得物宣布正式上线宠物鉴别，通过得物App内的“在线鉴别”，可找到鉴别宠物的选项。通过上传自家宠物的部位细节，就能收获拥有专业资质认证的得物鉴
猿辅导与新东方的两种“归途”

作者｜卓心月出品｜零态LT（ID：LingTai_LT）如何成为一家伟大企业？答案一定是对“势”的把握，这其中最关键的当属对企业战略的制定，且能够站在未来看现在，即使这其中的
新电商三兄弟，“抖快红”成团！

来源：价值研究所作者：Hernanderz 随着内容电商的概念兴起，抖音、快手、小红书组成的“新电商三兄弟”成为业内一股不可忽视的势力，给阿里、京东、拼多多带去了巨大压
华为HarmonyOS 4升级计划公布：首批34款机型今日开启公测

8月4日消息，今天下午华为正式发布了HarmonyOS 4系统，在更流畅的前提下，还带来了不少新功能，UI设计也有变化，会让手机焕然一新。华为宣布，首批机型将会在
利用职权私自解除被封帐号 Meta开除20多名员工

11月18日消息，据外媒援引知情人士表示，过去一年时间内，Facebook母公司Meta解雇或处罚了20多名员工以及合同工，指控这些人通过内部系统以不当方式重置用户帐号，其