单选题
适中
#16055
解决下列问题时,时间复杂度最大的是?( )
解决下列问题时,时间复杂度最大的是?( )
答案与解析
正确答案:C
解析
逐个分析时间复杂度
设数据规模 n=100
A 打印 100 个已知整数
循环遍历 100 个数依次输出,执行次数固定为 n,时间复杂度 O(n)。
B 在 100 个数据里查找 25
最坏情况需要遍历全部 100 个元素,最多执行 n 次,时间复杂度 O(n)。
C 冒泡排序对 100 个数据排序
冒泡排序最坏情况下需要外层 n 轮、内层每轮依次少 1 次比较,属于平方级,时间复杂度 O(n2)。
D 计算 1−2+3−4+⋯−100
可以直接用数学公式一步算出结果,无需循环遍历 100 次也能求解;即便循环累加也只是 n 次运算,时间复杂度 O(n)。
结论
O(n2)>O(n),时间复杂度最大的是 C。