下述partition分区函数的时间复杂度是否为线性O(n)？

别被两层嵌套循环的表象骗了，嵌套循环不等于平方复杂度，核心要看实际执行的操作总量。

推导逻辑 #

• 前置初始化步骤：calculateNumOfPackets计算总包数、packetQueue初始化、indexOfNextItem赋值都是常数时间*O(1)*操作，和输入列表长度无关。
• 两层循环的总操作数：你观察到的「缓存内层循环中断索引、不回溯遍历」是最核心的判定依据。内层循环每次的起始位置都是上一次处理到的元素下标，从来不会回头重新遍历已经处理过的元素：每填满一个数据包就跳出内层循环，下一次内层循环直接从上次停下的位置继续。不管外层循环跑多少轮，整个流程里itemList里的每个元素只会被访问1次、被add进数据包1次，这部分的总操作数刚好等于输入列表的总长度n。
• 其余固定开销：每次创建固定大小的Packet、把封装好的Packet加入队列，单次操作都是常数时间，总执行次数等于总包数ceil(n / packetSize)。结合代码注释里提到的「Packet是预定义固定容量」的前提，packetSize是固定常量，这部分开销的量级也是O(n)，和前面的元素遍历开销合并后，整体复杂度仍然是线性的。

常见误区：看到两层for循环就直接判定为*O(n²)*是典型的经验主义错误。*O(n²)*的成立前提是两层循环都独立遍历完整的输入集合，只要内层遍历的指针是单向前进、从不回溯，哪怕套了多层循环，总遍历次数也只会和输入规模呈线性关系。

参考实现代码：

partition(itemList) {
    numPackets = calculateNumOfPackets(listSize, packetSize); 
    indexOfNextItem = 0; 
    packetQueue = initialize(numPackets); 
    for (i = 0; < numPackets; i++) {
        // Initialized as a fixed-size list 
        Packet p = createNew(packetSize); 
        for (j = indexOfNextItem; j < itemList.length; j++) {
           // hasRoom() returns false when packet is at capacity
            if (p.hasRoom()) 
                // Guaranteed to run in constant time due to predefined capacity
                p.add(item[j]); 
            else {
                indexOfNextItem = j; // keep track of next index for inner loop
                break; 
            }   
        } // end inner
        packetQueue.add(p); 
    } // end outer
    return packetQueue; 
}

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