我正在尝试从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是在输入字符串的单词数。有人可以确认吗？
谢谢。(^_^)
我相信这个算法的复杂性比其他答案假设的要复杂一些（哈哈），直观地归结为我们正在预先（而不是附加）和循环的事实，也因为有一些过度简化。
为了正式（和正确），这里的其他分析没有使用足够的变量——让我们称之为w句子l中的单词数和这个句子中单词的最大长度。
然后iss >> data是O(w)（“最多与最长的单词一样昂贵”）。在l循环的迭代中，这是O(lw)。
ans.insert(0, data + " ")更复杂 -insert是O(x + y)针对x现有内容y的长度和新内容的长度。随着现有内容的长度不断增加（每次最多增加w），这个功能的复杂性并不完全显而易见。
执行l前置的成本最多w + 2w + 3w + ... + lw- 每次迭代我们必须为我们之前添加的所有单词以及我们现在刚刚添加的单词付费。这有一个封闭形式的表达式: w(1+2+...+l) = w * l(l+1)/2，这是O(w*l^2)。
把它放在一起，循环的成本是O(wl + w*l^2)，也就是O(w*l^2)。它是非正式的“二次”，但它不仅仅取决于一个变量n，因此最好将其归类为所有相关变量的函数。
附言。使用大 O 符号容易犯的错误之一是总是只谈论n- 但什么是n？在这个例子中，我们依赖的不仅仅是一个变量，所以使用n可能会产生误导。insert是新长度O(n)在哪里n- 但是如果您已经在谈论n其他一些参数（例如单词数），则会发生错误。
PP。请指出我分析中的错误/更正！
购买力平价。insert不能保证O(x + y)像我上面所说的那样 - 但假设这种复杂性是安全的。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句