嵌套循环中调用Linear_search的算法时间复杂度是多少？

算法时间复杂度分析 #

首先给出原算法代码（注意代码缩进存在歧义，以下分析默认J=J*2是内层循环的步长更新语句，属于内层循环体的一部分，即内层循环逻辑为J从1开始倍增直到超过n）：

For I=1 to n
    For J=1 to n 
        k = b[I]
        F = Linear_search(a,k)
        Print F
        J=J*2

逐层拆解耗时：

• 外层I循环：从1遍历到n，步长为1，总执行次数为n，对应复杂度O(n)
• 内层J循环：J初始值为1，每次循环后值翻倍，直到大于n时终止，单轮外层循环对应内层执行次数为log₂n，对应复杂度O(logn)
• 循环体内部操作：核心耗时为线性查找Linear_search，该算法时间复杂度为O(n)，其余赋值、打印操作均为常数级耗时可忽略

三层复杂度相乘得到总时间复杂度：O(n) * O(logn) * O(n) = O(n²logn)
你之前算出的O(nlogn)是漏算了线性查找的O(n)耗时，所以最终正确结果为O(n²logn)。

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