isSubstringOf（）的哪個方法更高效？

-1

請你看看這2個代碼，實現同樣的結果：isSubstringOf（）的哪個方法更高效？

別人的解決方案：

bool hasSubstring(const char *word, const char *container) { 

    if (container[0] == '\0' || word[0] == '\0') 
     return false; 

    for(int i = 0; container[i] != '\0'; i++) { 

     bool foundNonMatch = false; 
     for(int j = 0; word[j] != '\0'; j++) { 

      if (container[i + j] != word[j]) { 
       foundNonMatch = true; 
       break; 
      } 

     } 

     if (!foundNonMatch) 
      return true; 
    } 

    return false; 
}

我的解決辦法：

bool isSubstringOf(string word, string container) { 

    bool success = false;  

    // if either is empty, automatically return false 
    if (!word.empty() && !container.empty()) { 

     // loop through the container and while not successful 
     for (unsigned i = 0; i < container.size() && !success; i++) { 

      // if the first letter of the word is found in the container... 
      if (word.at(0) == container.at(i)) {       

       success = true; // success is temporarily true 

       // loop through the word to make sure it exists in the container 
       for (unsigned j = 1; j < word.size(); j++) { 

        // if either a mismatch happens, or container is too small 
        if (container.size() <= (j+i) || word.at(j) != container.at(j+i)) 
         success = false; // set the flag to false again 

       } 

      } 
     } 
    } 

    return success; 
}

哪一個使用更少的時間和複雜性？

據我所知，在最壞的情況下都是O(n^2)，對吧？

來源

2013-08-01 Oleksiy

你確定他們達到相同的結果，例如空字符串？ – doctorlove

@doctorlove哦，是的，謝謝你指出，這意味着當任何字符串是「」時返回false。「」包含「」沒有意義。「」什麼都沒有。問題更新 – Oleksiy

後者可能會繼續檢查每個循環中的大小 - 如果你運氣好的話，它將被優化掉 – doctorlove

或者，而不是推倒重來，你可以只使用：

container.find(word)

這是標準庫中，所以你可以確信，這是合理的高性能和正確的。您可以通過使用經過充分測試的已知構建模塊來優化程序員時間，QA時間和用戶時間（而不是運送潛在的錯誤代碼），而不是自行編譯。

來源

2013-08-01 14:30:21 Bogatyr

謝謝，這是一個複習題，所以我覺得它會是一個有趣的練習:) – Oleksiy

當然，自己嘗試一下，沒有錯，看看有什麼關係，然後在生產代碼中使用庫函數:)。 – Bogatyr

僅僅通過查看兩段代碼，除非有明顯的減速，否則無法區分執行速度。

大多數編譯器都會優化你的代碼，因此除非你喜歡學習操作碼，否則告訴哪一個會更快的預編譯並不容易。

根據速度，您應該對代碼進行基準測試。強調它，看看它是如何執行的。

但效率不是全部關於速度。你也應該考慮哪一種適合你的編碼風格。就我個人而言，我討厭在研究複製粘貼的代碼之前看到的隨機大塊。

+後它有代替：codereview

來源

2013-08-01 14:17:31

他們都是二次 - 容器的每一個字母是針對這兩種情況下每個單詞的每個字母檢查。
既然你問的是在粗野，一般回答有關

「的時間和複雜性」

。看看你的機器上哪個最快。

來源

2013-08-01 14:26:34 doctorlove

它畢竟不屬於這裏。 –

isSubstringOf（）的哪個方法更高效？

回答

相關問題