算法时间复杂度（Big O、Omega）：求解给定伪代码最坏情况复杂度

待分析伪代码 #

for i= 0 to n−1:
    if A[i] < 0:
        b= 1
        while b < n:
           b=b×2
    end while
  end if
end for

推导过程 #

• 最坏情况触发条件：数组A中所有元素都小于0，此时每一轮外层循环都会完整执行内部的while循环。
• 外层循环迭代次数：i从0到n-1，总共执行n次，除while外的判断、赋值操作都是常量级*O(1)*开销。
• 内部while循环开销：每次进入循环时b从1开始，每次乘以2直到大于等于n，循环次数为⌈log₂n⌉，单次while循环的时间复杂度为O(log n)。
• 总开销计算：n次外层循环每次对应*O(log n)*的操作，总最坏情况时间复杂度为O(n log n)。

补充说明：如果数组A中没有负数，算法时间复杂度会退化为O(n)，但这不属于最坏情况范畴。

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