for循环内嵌套if语句的时间复杂度分析:该算法时间复杂度是否为O(n)?
代码时间复杂度判定
待分析的代码片段如下:
for(int i = 0; i < Array.length; i++) { // 代码省略部分 if(s[i] > s[m]){ m = i; } }
针对这段代码的常见疑问:它的时间复杂度是多少?是不是O(n)?
判定逻辑
- 代码的主体是单层循环,循环边界是数组的实际长度,也就是说数组有多长,循环就会跑多少次,整体执行次数和数组规模n是线性对应关系
- 循环里可见的条件判断、变量赋值操作,不管触发多少次,都是固定常数时间的操作,不会随着n变大额外增加开销
- 在省略部分的逻辑是常数级操作的前提下,这段代码的时间复杂度确实是O(n)
常见误区:如果代码里省略的
...部分藏了嵌套循环、递归调用、数组排序这类会随n规模超线性增长的逻辑,那整体复杂度会被这部分拉高,就不能直接判定为O(n)。但从目前给出的可见代码结构来看,只要省略部分没有这类高开销逻辑,O(n)的结论完全成立。
内容的提问来源于stack exchange,提问作者ChuyMuy
相关产品推荐
相关产品推荐

