计算时间复杂度需要三个前提
- 不考虑任何的软硬件环境
- 假设程序每一条语句的执行时间相同，均为
t - 只考虑最坏情况，即数据规模足够大，设为
n
所以，一定要注意这三个前提下，我们的分析才能正常进行也才有意义！所以我们这里的时间复杂度实际上指的是最坏时间复杂度!
这里有一个固定的公式来表示时间复杂度:
T(n) = O(f(n))其中n表示的是数据规模，f(n)是算法执行的总时间，其计算公式是:
f(n) = 算法执行语句的数量 * t即算法中语句的执行数量与单条语句执行时间t的积。
所以时间复杂度公式就是:
T(n) = O(算法运行总时间)这里我们把算法运行总时间放在了一个固定的格式中: O()。 我们成这种表达方式为大O表示法，大O表示法就是表达
最坏的情况的一中表示形式，后面我们会学习最坏空间复杂度，也是用大O表示法来表示！而且在时间复杂度扩展知识中我们还会了解表达最好情况的大Ω表示法和表达平均情况的大Θ表示法！
常见的时间复杂度
| 时间复杂度 | 非正式术语 |
|---|---|
| O（1） | 常数阶 |
| O（n） | 线性阶 |
| O（n^2） | 平方阶 |
| O（log n） | 对数阶 |
| O（n * log n） | n log n 阶 |
| O（n^3） | 立方阶 |
| O（2^n） | 指数阶 |
| O（n!） | 阶乘阶 |
| O（n^n） | n的n方阶 |
复杂度排名如下
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
时间复杂度知识扩展
1、最好情况下的算法时间复杂度
最好情况下的时间复杂度又叫做 最好时间复杂度，使用 大Ω 表示法表示！其实“最好时间复杂度”好理解，它描述了一个算法的最好的情况下花费的时间，也可以看做是一个算法花费时间的下限！就比如我们生活中要找一个东西，最好的情况是他就摆在你眼前，你一下就能找到它！在算法里呢，如果要设计一个搜索算法，比如要在一个包含100个元素的数据中搜索指定目标，最好的情况就是第一次就找到了！
但是“最好时间复杂度”的实际意义并不大，除非我们要求一个算法只要最好的状态能满足需求就可以使用，但是这样的要求并不多见，一般都是要求最坏的情况下如果能接受那算法就可以使用！所以我们主要研究的和使用的都是“最坏时间复杂度”！
2、平均情况下的算法时间复杂度
平均情况下的时间复杂度又叫作 平均时间复杂度, 使用大Θ表示法表示！“平均时间复杂度”也有一定的实用性，它描述了一个算法在处理数据过程中单个数据元素花费的平均时间！但是“平均时间复杂度”有一个问题就是并不好测量，因为平均时间是在真正运行过程中统计并且计算出来的！但也更贴合实际效果！所以这种表示方法很难通过直接评估得到结果！这个更加接近事后统计的一种方案。
不过我们可以举一个比较好统计的例子,仍然是搜索100个排好序的数据中的某个元素！我们就使用直接遍历对比并且找到就立刻停下的形式来搜索！那么最好情况下找到的第一个元素就是我们要找的，也就是1次就找到了！最坏情况呢？是第100次才找到！那么平均呢？如果每一个元素都要找一遍的话，按照从头到尾找并且找到就停下的算法你可以计算一下应该是
( 1+2+3+4+...100 ) / 100 = 50.5平均要找 50.5 次！
时间复杂度计算案例
计算 1+2+3+4+5.....+n 的和！第一种思想：
我们可以生成一个n个长度的数组，然后把数据存储到数组中，最后计算数组各项的和。
function sum( $n ){
// 设定返回结果
$res = 0; //{1}
// 生成数组[1,2,3,4,5...n]
$arr = range(1,$n); //{2}
// 计算数组中各项的和
for($i = 0; $i < $n; ++ $i){ //{3}
$res += $arr[$i]; //{4}
}
// 返回结果
return $res; //{5}
}时间复杂度计算
第一步：计算算法运行过程中运行的代码总的条数N
分析代码可知，其中{1}{2}{5}所标注的代码语句整个过程每条都只执行1次，而{3}{4}标注的语句执行过程中每一条都要执行n次！所以总条数N:
N = 2*n + 3第二步：计算算法总运行时间f(n):
前面我们已经制定了前提，以为每一条语句执行的时间实行同的，都是t，所以:
f(n) = N * t = (2*n + 3) * t第三步：计算时间复杂度T(n):
我们这里的时间复杂度指的是最坏的时间复杂度，使用大O表示法表示:
T(n) = O( f(n) ) = O( (2*n + 3) * t )
即
T(n) = O( (2*n + 3) * t )第四步：简化
实际上到这里我们已经成功的计算出了这个算法的时间复杂度，但是在实际的时间复杂度的表示中，对于上面的结果我们要做一定的简化，简化结果是:
T(n) = O(n)Tips：简化步骤
1, 去掉常数t:
因为t代表的是每一条语句的运行时间，而每一条语句的运行时间都相同，所以t实际上是个常数，并且不影响
分析结果T(n) = O( (2*n + 3) )2, 用常数1取代运行时间中的所有加法常数:
T(n) = O( 2*n + 1 )3, 在修改后的运行次数函数中，只保留最高阶项:
T(n) = O( 2*n + 1 )4, 如果最高阶项存在且不是1，则去除与这个项相乘的常数:
T(n) = O( n + 1 )5, 如果存在数据规模n, 去掉加法常数项:
T(n) = O(n)关于时间复杂度的计算，你会发现计算过程实际上变成了要数数整个程序一共会有多少条语句被执行的一年级数数问题！
哈！开个玩笑！但，时间复杂度计算的实际结果确实也如此！
所以以后有人问你某个算法的时间发复杂度是什么，如果是直接描述，你就直接告诉他是O(XX), 如果是写表达式的话就写我们上面演示的这种T(n)=O(XX)就可以啦！
第二种思想
直接循环计算数组各项的和
function sum( $n ){
// 设定返回结果
$res = 0; //{1}
// 计算数组中各项的和
for($i = 1; $i < $n; ++ $i){ //{2}
$res += $i; //{3}
}
// 返回结果
return $res; //{4}
}时间复杂度计算
第一步：计算算法运行过程中运行的代码总的条数N:
N = 2*n + 2第二步：计算算法总运行时间f(n):
f(n) = N * t = (2*n + 2) * t第三步：计算时间复杂度T(n):
T(n) = O( f(n) ) = O( (2*n + 2) * t )第四步：简化
T(n) = O(n)第三种思想
利用高斯公式，f(n) = (1+n)*n/2
function sum( $n ){
// 设定返回结果
$res = 0; //{1}
$res = ( 1 + $n ) * $n / 2; //{2}
// 返回结果
return $res; //{3}
}时间复杂度计算
第一步：计算算法运行过程中运行的代码总的条数N:
N = 3第二步：计算算法总运行时间f(n):
f(n) = N * t = 3 * t第三步：计算时间复杂度T(n):
T(n) = O( f(n) ) = O( 3 * t )第四步：简化。
T(n) = O(1)