知道自己写的程序的时间复杂度，有利于我们写出能够高效运行的程序。
程序是由一个个函数组成的，有些简单的由几个基础运算组成的函数大家一眼就能看出来它的时间复杂度，但是大部分函数没那么简单，只要函数里面涉及到了循环、外部函数调用甚至递归的时候它的时间复杂度就没那么容易分析啦。
这篇文章的内容，可以帮你快速推导出程序代码的时间复杂度。
要分析程序的时间复杂度，首先还是要确定时间复杂度的度量标准— —英文文档里通常会用 metric 这个单词来表示，这个标准规定了在函数中平铺展开的代码、循环中的代码、有函数调用的代码、以及递归调用的代码的时间复杂度的测量方式。
如何计算程序的时间复杂度呢？最常用的度量方式叫做 Big O Notations 翻译过来叫大O标记法。
使用大O标记法前要先了解它的几个要点：
在大O标记法中，常见的时间复杂度有一下几类。
它们的关系如下：
图片
从上面的图我们可以看到，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) ，所以在平时写代码时在你不确定程序能执行多少次的时候，最好不要轻易使用递归调用。
这篇内容我们梳理了一下不同的时间复杂对大概对应什么样的代码，让我们能更正确地估算自己写的程序的时间复杂度。
本文链接：//www.dmpip.com//www.dmpip.com/showinfo-26-89409-0.html怎么计算我们自己程序的时间复杂度
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号
