计算下述给定代码对应算法的时间复杂度

原算法代码 #

count = 1
j = 0
for i = 1 to 100 do
    count += i
for k = 1 to n do
    count *= k
while j < n do
    count +=j
    j *= 2;
end while

注：原代码中j初始值为0会导致j *= 2后始终为0，while循环进入死循环，以下推导默认j初始值应为1，属于代码笔误修正。

分步推导过程 #

计算时间复杂度时仅保留随输入规模n增长的最高阶项，常数项和低阶项均可忽略，推导如下：

• 第一个for循环：循环上限固定为100，和输入规模n无关，执行次数是固定常数，时间复杂度为O(1)
• 第二个for循环：循环变量k从1遍历到n，共执行n次操作，时间复杂度为O(n)
• 第三个while循环：每次循环j都会翻倍，假设循环执行x次后满足退出条件j >=n，可得2^x >=n，即x=log₂n，执行次数为对数级，时间复杂度为O(log n)

最终结果 #

三个模块的时间复杂度累加为O(1) + O(n) + O(log n)，取最高阶项后，整体算法的时间复杂度为O(n)

内容的提问来源于stack exchange，提问作者Umar Mahmood