关于算法的时间复杂度

Question

我试图从LeetCode.com解决以下问题：

给定输入字符串，逐字反转字符串。因此，“天空是蓝色的”应该变成“蓝色是天空”。

我想出了以下代码片段：

class Solution {
public:
    void reverseWords(string &s) {
        if(s.empty()) return;

        istringstream iss(s);
        string data, ans;
        while(iss>>data) {
            ans.insert(0, data+" ");
        }

        s=ans.substr(0,ans.size()-1);
    }
};

我想知道同样的时间复杂性。我认为它是O(n^2)，其中n是输入字符串中的单词数。有人可以确认吗？

谢谢。 (^_^)

Answer 1

我相信这个算法的复杂性比其他答案所假设的要复杂得多（哈哈），直观地说我们正在预先（不附加）和循环，还因为有一点过于简单化。

---

为了正式（和正确），这里的其他分析没有使用足够的变量 - 让我们将w称为句子中的单词数量，将l称为该句子中单词的最大长度。

然后iss >> data是O(w)（“最多和最长的单词一样昂贵”）。在循环的l迭代中，这是O(lw)。

---

ans.insert(0, data + " ")更复杂 - insert是O(x + y)为x现有内容的长度和y新内容的长度。随着现有内容的长度不断增长（每次最多添加w），此功能的复杂性并不完全明显。

执行l prepends的成本最多是w + 2w + 3w + ... + lw - 我们必须为我们之前添加的所有单词以及我们现在添加的单词付出的每次迭代。这有一个closed form expression：w(1+2+...+l) = w * l(l+1)/2，这是O(w*l^2)。

---

把它放在一起，循环的成本是O(wl + w*l^2)，这只是O(w*l^2)。它是非正式的“二次”，但它不仅仅取决于一个变量n，因此最好将其归类为所有相关变量的函数。

---

PS。使用大O符号的一个容易犯的错误就是总是只谈n - 但是什么是n？在这个例子中，我们不仅仅依赖于一个变量，因此使用n可能会产生误导。 insert是O(n)，其中n是新的长度 - 但如果你已经在谈论n关于其他一些参数（比如单词的数量），那么错误就会发生。

聚苯硫醚。请在我的分析中指出错误/更正！

购买力平价。正如我上面所声称的那样，insert isn't guaranteed to be O(x + y) - 但假设这种复杂性是安全的。

Answer 2

复杂性是O(N)，正如J.Doe正确解释的那样

istringstream使用O(n)并在开头附加（并导致随后的移动）使用另一个O(n)

看这里的解释，为什么常数2不相关：https://en.wikipedia.org/wiki/Big_O_notation#Example

如果f（x）是几个因子的乘积，则可以省略任何常数（产品中不依赖于x的项）。