java - 我们可以说 O(n + m) 等价于 O(n)，当 m 是常数或当 n > m

Question

我正在解决我所在的 leetcode 问题之一(最长回文)

• 遍历整个字符串以计算每个字符出现的频率
• 遍历数组(charFreq)，判断字符出现频率是否为奇数，并进行相应运算。

<强>1。使用数组实现

   public int longestPalindrome(String s) {

    int[] charFreq = new int[58];
    for(char sChar : s.toCharArray()){
      ++charFreq[sChar - 'A'];
    }

    int charsWithOddFreq = 0;
    for(int freq : charFreq){
      if((freq & 1) != 0){
        charsWithOddFreq++;
      }
    }

    int len = s.length();
    return (charsWithOddFreq == 0) ? len : (len - charsWithOddFreq + 1);
  }

在哪里， 1 <= s.length <= 2000
<强> s consists of lowercase and/or uppercase English letters only.

但是，说上面这个程序的时间复杂度是O(n + m)是否正确？ , 在这里 n is the length of the given string(s)和 m is the size of array taken to store frequency(charFreq)还是只说 O(n) 更好？因为我们可以忽略常数因子 (m)，它不依赖于输入字符串的大小，并且每个输入的迭代总是相同的(即 58)。
简而言之，就是O(n + m) ~ O(n)在这种情况下？

<强>2。使用 Map 实现相同

public int longestPalindrome(String s) {

    Map<Character, Integer> charFreq = new HashMap<>();
    for(char sChar : s.toCharArray()) {
      charFreq.put(sChar, charFreq.getOrDefault(sChar, 0) + 1);
    }

    int charWithOddFreq = 0;
    for(int val : charFreq.values()) {
      if((val & 1) != 0) {
        ++charWithOddFreq;
      }
    }

    int len = s.length();
    return (charWithOddFreq == 0) ? len : (len - charWithOddFreq + 1);
  }

使用Map，时间复杂度应该是O(n + m) ，因为 m 会因输入字符串而异，因为它取决于输入大小。但是，在这种情况下(使用 Map 时)我的问题是我们可以说 O(n + m)作为O(n) , 当 n > m ？因为根据限制，即
1 <= s.length <= 2000
和 s consists of lowercase and/or uppercase English letters only.
所以，字符串的长度(n) > 大小写字母的个数(m)简而言之，就是O(n + m) ~ O(n)在这种情况下也是如此吗？

Answer 1

A1。自 m在你的第一个算法中是一个常量 (58)，这是 O(n)时间。这O(n + constant)与O(n)相同.

A2。你的第二个算法也是 O(n)时间。

Using Map, the time complexity should be O(n + m), as m will vary for input string as it is dependent on the input size.

您没有明确说明，但在这种情况下，n是 s 中的字符数, 和 m是 s 中不同字符的数量.

那些可变变量m和 n不是独立的。事实上m将始终小于或等于 n比n .

但是m + n <= 2n , 和 O(2n)与O(n)相同.所以O(m + n)与O(n)相同在这种情况下。

---

(以上不是严格的证明......但它应该足以突出你推理中的缺陷。如果你想要严格的证明，它非常简单，尽管很乏味。)

---

并在(更正的)标题中回答您的问题:

Can we say O(n + m) is equivalent to O(n), when m is constant or when n > m

是的。见上文。

---

请注意，两个版本具有相同(时间)复杂度的事实并不意味着它们的性能相同。