如何求解方法的最坏情况Big-O渐近运行时间？求参考资料

通用分析步骤 #

• 拆分代码为基本操作单元：将方法拆解为赋值、比较、算术运算、方法调用等独立操作，这类基础操作的时间复杂度均为O(1)。
• 定位复杂度敏感分支：找出会随数据量变化而改变执行时间的逻辑，比如数组扩容、循环、递归调用等。
• 锁定最坏场景：找到能触发最多操作次数的输入条件，比如数组已满、循环执行最大次数等。
• 叠加分支复杂度：按最坏场景下的执行路径，累加各操作的复杂度，取主导项作为最终结果。

实例代码分析 #

先看你提供的代码：

public void addEnd(double element)
{
    
    if (data.length == manyItems)
    ensureCapacity(manyItems*2 + 1);
    
    
    data[manyItems] = element;              
    currentIndex = manyItems;               
    manyItems++;                        
}

逐段拆解分析 #

1. 条件判断 data.length == manyItems：属于基础比较操作，时间复杂度O(1)。
2. 扩容分支 ensureCapacity(manyItems*2 + 1)：这个方法的核心逻辑是创建新数组，并将原数组的所有元素复制到新数组中。假设当前数组已有n个元素（即manyItems = n），复制n个元素的操作耗时与n成正比，因此该方法的时间复杂度为O(n)。
3. 后续赋值与自增操作：data[manyItems] = element、currentIndex = manyItems、manyItems++均为基础操作，总时间复杂度仍为O(1)。

最坏情况复杂度结论 #

当数组已满（data.length == manyItems）时，会触发扩容逻辑，此时整个addEnd方法的执行时间由ensureCapacity的复制操作主导，因此最坏情况下的时间复杂度为O(n)，其中n为当前数组的元素数量。

注：如果做摊还分析，多次调用addEnd的平均时间复杂度是O(1)，但你问的是最坏情况，单次触发扩容的场景就是最坏情况。

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