伪代码的大O复杂度分析：字母异位词算法时间复杂度疑问

算法实现 #

areAnagrams(L1, L2)
// i.e. an integer array of size 26, with entries initialised at 0
charCount1[26] := {0} // 26 assignments
charCount2[26] := {0} // 26 assignments
for i from 0 to |L1|
    charCount1[(char as integer) L1[i]]++ // n operations
for i from 0 to |L2|
    charCount2[(char as integer) L2[i]]++ // n operations
for i from 0 to 25
    if charCount1[i] != charCount2[i] // 25 comparisons
        return false
return true
end

我的疑问 #

我认为该算法的时间复杂度为O(n)，因为整体约有2n+77次操作/比较。请问我是否可以通过直接相加操作次数的方式来分析时间复杂度？

解答 #

当然可以！这种通过精确计数操作次数的方式，是时间复杂度分析里非常基础且有效的方法，尤其适合这种逻辑清晰、操作明确的算法。

咱们来拆解你的分析逻辑：

• 初始化两个数组：26+26=52次赋值操作，这属于常数项，不会随输入单词的长度变化而改变
• 遍历两个单词：假设两个单词长度均为n，这里就是n+n=2n次计数操作，这是线性项，会随着输入规模n的增大而线性增长
• 对比数组的25次比较（加上初始化的52次，总常数项约77次），同样属于不随n变化的常数部分

大O符号的核心是描述输入规模增长时，算法运行时间的增长趋势，它会忽略所有常数项和低阶项——因为当n变得足够大时，常数项对整体运行时间的影响会微乎其微，主导运行时间的是线性增长的2n部分。所以你的结论O(n)完全正确，而通过相加操作次数来推导时间复杂度的方法，也是完全合理的。

小补充：如果两个单词长度不同，它们必然不是字母异位词，你可以在算法开头加一步if |L1| != |L2| return false，这样能提前终止不必要的计算，但这不会改变算法的时间复杂度，依然是O(n)。

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