分析func2函数的最优与最坏时间复杂度，二者是否可能相同？

最优与最坏时间复杂度是否可能相同？ #

是的，二者完全可能相同。当算法的执行步骤数不依赖输入数据的具体取值，或者输入数据的差异不会改变执行步骤的量级时，最优、平均、最坏时间复杂度就会是同一个量级。比如普通的数组遍历（O(n)）、无提前终止的两层嵌套循环（O(n²)），都属于这类情况。

func2函数的时间复杂度分析 #

先明确函数核心逻辑：woo是函数级变量（仅初始化一次），外层循环执行n次，内层循环默认执行n次，但当woo累加至10000时，会提前退出当前内层循环。

最坏时间复杂度 #

当woo永远不会等于10000时（比如数组元素全为0，或累加后始终无法达到10000），内层循环每次都完整执行n次，外层循环执行n次，总操作次数为n*n = n²，因此最坏时间复杂度为O(n²)。

最优时间复杂度 #

即使遇到最理想的情况：第一次内层循环的第1次迭代就让woo等于10000，此时仅提前退出第一次内层循环，后续的n-1次外层循环中，woo的值已经大于10000（除非累加负数，但即使如此，也只会改变少数几次内层循环的执行次数），总操作次数为1 + (n-1)*n = n² -n +1。根据Big O表示法的规则，我们只保留最高阶项、忽略低阶项和常数，因此最优时间复杂度仍然是O(n²)。

你提到的n(n-1)确实属于O(n²)范畴，因为Big O关注的是增长趋势，n(n-1)=n²-n的主导增长项是n²，低阶项n可以被忽略。你在IDE中的测试结果也验证了这一点：无论输入数组如何，随着n增大，执行次数的增长趋势是平方级的。

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