Python列表处理算法的时间复杂度分析与确认

问题背景 #

已知在Python中，l1 == l2的比较操作时间复杂度为O(n)，执行后程序会立即终止。现在结合给定的外层循环，分析以下算法的时间复杂度，满足两个假设条件：

• l1与l2长度均为n
• l1与l2之间至少存在一个不相同的元素

算法代码 #

for i in range(len(l1)):
    if (l1[i] != l2[i]):
        l2[i] = l1[i]
        if (l1 == l2):
           return True
        else:
           return False

分析与结论 #

你的初步思路对最坏情况的场景判断是准确的：当唯一不同的元素位于最后一位时，循环需要完整遍历n次（时间复杂度O(n)），修改l2的最后一个元素后执行一次O(n)的数组比较，随后程序终止。

但需要明确：时间复杂度的大O表示法会忽略常数系数，O(2n)本质上等价于O(n)。因为大O描述的是输入规模n趋近于无穷大时，算法执行时间的增长趋势——2n和n的增长速率都是线性的，没有量级上的差异。

因此，该算法的时间复杂度为O(n)。

内容的提问来源于stack exchange，提问作者Wasif Latif Hussain