反转字符串中的单词的运行时间

所以，如果我们有：

玛丽有只小羊羔

我们会得到：

YRAM大新一个elttil BMAL

的实现的算法如下：

string wordsToSplit = "Mary had a little lamb"; 

string[] words = wordsToSplit.split(" "); 
string wordsReversed = ""; 

foreach(string word in words) 
{ 
     string reversedWord = ""; 
     foreach(char letter in word){ 
      reversedWord = letter + reversedWord; 
     } 
     wordsReversed += " " + reversedWord; 
}

这个psuedo代码应该可以工作。然而这个特定算法的运行时间是多少？我认为它会是O（n^2），其中N是字符串中的字数。但这似乎不正确...

东西告诉我这实际上是O（N）* O（M），其中'N'是单词的数量，'M'是每个单词中的字符数字。因此，在最坏的情况下，如果我们有类似于“a b c d e f g h i j k l m n o p”的情况，这可能是O（n^2）...

您认为如何？这是窃听我...

来源

2014-11-21 supersixfour

在你的代码中，你永远不会使用“currentIndex”。 – jrsala 2014-11-21 19:30:57

'yarm'不正确。 – 2014-11-21 19:31:36

'（字数）*（每个字中的字符数）==（字符串中的字符数）'。你不能少于这个，因为你至少需要读整个字符串。该公式中任何地方都没有平方。 – 2014-11-21 19:38:12

在你的算法：

split具有线性复杂的输入字符串
假设的长度，通过
```
string wordsReversed; 
```
你居然意思是
```
string wordsReversed = ""; 
```
和通过
```
wordsReversed.join(" ", reversedWord); 
```
你实际上意味着
```
wordsReversed += " " + reversedWord; 
```
然后外foreach循环的主体具有线性在由于两个内foreach环和reversedWord串接中的word长度复杂其中wordsReversed在word的长度上具有线性复杂度。
最后，所有的word S的words的长度之和是初始输入字符串的长度

因此你的总的复杂性为O（n），因为它应该是。由于上述原因，虽然该算法确实在这种情况下确实会有些低效，但对于该算法，“a b c d e f g h i j k l m n o p”并不是最坏的情况。

来源

2014-11-21 19:37:09 jrsala

实际的时间复杂度取决于如何在您的语言中实现字符串连接。例如，在Java中，循环中的天真串连接将花费O（N * M）时间，其中N是总字符串长度，M是要追加的字符串的数量。

在一个合理的级联算法中（例如使用Java的StringBuilder;参见Dynamic Arrays），内部使用一个自增长缓冲区，以保证一系列级联的线性时间。

无论如何，在你的情况下，不需要动态缓冲区 - 你事先知道你建立的字符串的长度。您甚至可以将输入视为一个char数组，并就地完成这项工作。

来源

2014-11-21 19:53:59

反转字符串中的单词的运行时间

回答

相关问题