反轉字符串中的單詞的運行時間

所以，如果我們有：

瑪麗有隻小羊羔

我們會得到：

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

反轉字符串中的單詞的運行時間

回答

相關問題