这个解决方案是如何在一个句子O（N）中反转单词的，当它在整个句子中调用reverse，然后在每个单词上调用reverse？

Question

http://www.geeksforgeeks.org/reverse-words-in-a-given-string/

这个解决方案是如何在一个句子O（N）中反转单词的，当它在整个句子中调用reverse，然后在每个单词上调用reverse？你知道吗

N=整个串的长度 M=每根线的长度

不是O（N）+O（N*M）吗？使用M来表示字符串的长度是否正确，因为M对于每个输入都是不同的？你知道吗

Answer 1

看看代码的作用：

1. 它扫描整个句子（N个字符）寻找单词边界。你知道吗
2. 对于每个单词，它都会反转单词。对于word中的W个字符，reverse函数循环W/2次。你知道吗
3. 最后，它反转整个字符串（N/2个循环）。你知道吗

棘手的部分是单词的颠倒。因为这些词都是同一个句子的一部分，所以你可以把它们看作是整个句子的又一次遍历。你知道吗

这使得：

1. O（n）
2. O（n）
3. O（n）

所以整个过程就是O（3n），也就是O（n）。你知道吗

Answer 2

如果使用N作为整个字符串的长度，那么不应该使用N*M来表示反转每个单词，它只是N，因为您要对整个字符串本身进行两次：一次反转它，一次反转单个单词。你知道吗

编辑：如果给你一个字符串列表，你想反转列表的顺序，然后反转字符串本身，那么它将是O（N）+O（L*M），其中N是数组中元素的数量，M是单词的长度，因为数组与单词是分开的。您可以反转数组的顺序，而不反转单词，因此这是一个独立于单词的计算。当你反转单词时，它是单词的长度乘以你正在反转的单词的数量。你知道吗

Answer 3

你在重复使用N来表示两个不同的意思。实际上应该有三个变量：

• N是整个字符串的长度
• M是字符串中的字数
• O是每个单词的（平均）长度

然后整个算法将在O(N + M*O)中运行。但是，M*O总是比N小，因为字符串是由单词和分隔它们的空格组成的。所以你可以把整个事情简化成O(N)。你知道吗