伪代码中 Big-O 的复杂性

Question

我编写了以下算法，它接受两个单词（字母列表）并检查这两个单词是否是彼此的变位词。

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 operations/comparisons.

我可以像这样简单地添加操作次数吗？

Answer 1

嗯，形式上是 O(|L1| + |L2|)。但是，如果你输入 n = max(|L1|, |L2|)，那么它就是 O(n).

伪代码中 Big-O 的复杂性

Complexity in Big-O from Pseudocode

algorithm

big-o

pseudocode

time-complexity