三元表达式嵌套三元表达式解析

3.3. 平均情况时间复杂度(加权平均时间复杂度或者期望时间复杂度)

最好和最坏情况时间复杂度都是极端情况发生的时间复杂度，并不常见。因此可以使用平均情况时间复杂度来表示。比如上面这段代码中查找 x 在数组中的位置有两种情况，一种是在数组中，另一种是不在数组中。在数组中又可以在数组中的 0~n-1 位置。假设在数组中和不在数组中的概率分别为 1/2，在数组中的 0~n-1 的位置概率都一样，为 1/(2 *n)。因此，上述这段的平均情况时间复杂度(或者叫加权平均时间复杂度、期望时间复杂度)为
 

从这段代码中可以看出m 和 n 是两个数据规模，无法评估 m 和 n 的量级大小。因此，不能省略其中任何一个，所以就是 O(m+n) 了。

4.O(2^n)、O(n!)

在上述表格中列出的复杂度量级，可以粗略的分为两类：多项式量级和非多项式量级。其中非多项式量级只有这两个。非多项式量级的算法问题也叫做 NP(Non-Deterministic Ploynomial，非确定多项式)问题。当 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间也会无限增长，所以是种很低效的算法。

3.2. 最好、最坏情况时间复杂度

比如下面这段代码中，是在数组中查找一个数据，但是并不是把整个数组都遍历一遍，因为有可能中途找到了就可以提前退出循环。那么，最好的情况是如果数组中第一个元素正好是要查找的变量 x ，时间复杂度就是 O(1)。最坏的情况是遍历了整个数组都没有找到想要的 x，那么时间复杂就成了 O(n)。因此 O(1) 就是这段代码的最好情况时间复杂度，也就是在最好的情况下，执行这段代码的时间复杂度。O(n) 就是这段代码的最坏情况时间复杂度。
 

下面针对上述的若干种时间复杂度进行阐述：

1.O(1)

O(1)是常量级时间复杂度的一种表示，只要代码的时间不随 n 的增大而增大，那么它的时间复杂也是 O(1)。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是 O(1)。

2.O(logn)、O(nlogn)

对数时间复杂度往往比较难分析，比如下面这段代码中
 

• 加法法则：总复杂度等于量级最大的那段代码复杂度

这个主要是省略掉大 O 复杂度中的低阶项。个人感觉这个方法跟上面的方法有些重合。比如下面这段代码中，可以按照循环分为三个段，第一个段中有个循环，但是循环次数是个常数项，对增长趋势无任何影响，因此时间复杂度是 O(1)，第二段代码的时间复杂度是 O(n)，第三个段代码的时间复杂度是 O(n^2)。这三个段中量级最大的那个时间复杂度也就是整段代码的时间复杂度。
 

3. 时间复杂度分析

如何对一段代码的时间复杂度进行分析呢?可以采用以下几种方法

• 只关注循环次数最多的一段代码

因为大 O 复杂度表示法只是表示一种趋势，所以可以忽略掉公式中的常数项、低阶、系数等，只记录一个最大的量级就可以了。因此在分析一个算法、一段代码的复杂度的时候，只需要关注循环次数最多的那一段代码就行了。比如下面这段代码，时间复杂度是 O(n)

（编辑：信阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!