关于ADT List数组实现Concat方法复杂度O(n₂+1)定义的困惑

问题背景 #

学习ADT List的数组、链表实现及Concat方法时，遇到一个困惑：数组实现的Concat方法，老师认为其时间复杂度是O(n₂+1)而非O(n₂)，理由是当第二个列表长度n₂为0时，算法运行时间不为0。已知所有O(n)的函数都属于O(n+1)，但无法理解这个解释，猜测老师可能误解了O(n)的定义——认为O(n)要求存在常数c，对所有n≥0都有f(n)≤c*n（这会导致n=0时f(0)必须为0），而O(n₂+1)则无此要求，想确认这个猜测是否正确。

解答 #

1. 标准大O定义
   大O符号的标准定义是：对于函数f(n)和g(n)，f(n) = O(g(n))当且仅当存在常数c>0和n₀≥0，使得对于所有n≥n₀，有|f(n)| ≤ c*|g(n)|。注意这里只要求不等式对「足够大的n」成立，而非所有n≥0。

2. 老师的误区分析
   你的猜测是正确的。老师错误地要求不等式对所有n≥0成立：

   • 当n₂=0时，Concat方法确实需要执行一些基础操作（比如检查列表状态、初始化结果容器等），此时运行时间f(0)是一个大于0的常数k。如果按老师的错误定义（要求f(n)≤c*n对所有n≥0成立），那么n=0时会得到k≤0，显然矛盾。
   • 而用O(n₂+1)的话，n₂=0时n₂+1=1，此时只需要取c≥k，就能满足f(0)≤c*1，规避了这个矛盾，但这是基于错误定义的冗余写法。

3. 标准定义下的正确结论
   按照标准大O定义，Concat方法的时间复杂度写成O(n₂)完全正确：

   • 我们可以取n₀=1，当n₂≥1时，f(n₂) = 基础操作时间 + n₂个元素的拷贝时间，只要取足够大的c（覆盖基础操作的常数和每个元素拷贝的时间），就能满足f(n₂)≤c*n₂。
   • n₂=0的情况不需要纳入考虑，因为定义只要求对n≥n₀的情况成立。

4. 渐近等价性说明
   从渐近复杂度的角度，n₂和n₂+1是同阶的，O(n₂)和O(n₂+1)没有本质区别——所有属于O(n₂)的函数都属于O(n₂+1)，反之亦然。老师的表述只是因为对标准定义的误解，才采用了更冗余的写法。

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