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

Question

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

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

1.使用 array

实现

   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 时）我的问题是，当 n > m 时，我们可以说 O(n + m) 为 O(n) 吗？因为根据约束，即
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 是 [= 中的不同字符数16=].

那些可变变量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

是的。见上。

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

Answer 2

我完全同意，但会更进一步。 由于输入大小有上限，因此两种算法都是 O(1) - 因为对于所有有效输入，有一个恒定的操作数，两种算法都不会超过。

询问使用数组或映射的算法的渐近 worst-case time-complexity（又名 Big-O）是否最好没有意义，除非这些映射的大小可以增长超过显着范围。

我真的建议尝试绘制出每种算法对各种（有效）输入所需的时间差异。您应该会发现，对于如此小的输入，两者的表现非常相似，并且根据输入大小的时间增长非常小。由于地图的复杂性，我希望 array-based 更快；但是同样，对于这样的小问题，就原始毫秒而言，差异不会很明显。

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

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

java

time-complexity