c++ - Big-O函数分析，将字符串中的所有元音替换为一个字符

Question

我不确定我是否正确地进行了大 O 分析。

这是一个用指定字符替换字符串中所有元音的函数。

我选择将字符串中的每个字符与包含所有元音的恒定大小的字符串进行比较。

鉴于输入字符串的大小可以向上扩展，但元音字符串的大小是恒定的，我认为大 O 分析是 O(n * m) 而不是 O(n * n)，其中 n 是输入字符串，m为元音字符串。

我认为它应该只是 O(n) 而不是 O(n * m)，因为第二个 for 循环迭代了恒定数量的元素，所以它会被丢弃？

如果有人能纠正我，我将不胜感激。

using namespace std;

string replaceVowels(string str, char ch) {

    string vowels = "aeiouyAEIOUY";

    for(int i = 0; i < str.size(); i++) { //O(n)

        for(int j = 0; j < vowels.size(); j++) { //O(m)
            if (str[i] == vowels[j])
                str[i] = ch;
        }
    }

    // O(n * m) or O(n) or O(n * n)?
    return str;
}

Answer 1

在Big O notation您可以忽略所有常数(严格为正)因素。

这意味着(因为 m=12 是常数)O(n * m) = O(n)，所以两者在技术上都是正确的，但当然O(n) 是人们会说的(很像我们在小学时被教导要回答“二分之一”而不是“四分之二”)。

就是这样，至少在理论上是这样。然而在实践中，确定什么算作常数以及什么可以任意大有时是一项主观任务。例如，在这种情况下，我们使用 sizeof(int) 是常量这一事实(否则 i < str.size() 不会花费常量时间)，但我们仍然假设 n 没有上限(否则 O(n)=O(1))。 从技术上讲，这些假设不可能同时成立，但无论如何我们都采用与我们假设物理学中空气摩擦为 0 以适应更简单模型的方式大致相同的方式。