我寫了一個函數，可以在保持單詞順序的同時，翻轉句子中每個單詞的字符。我不確定時間複雜度

-2

我寫了一個函數來做到這一點，它的工作原理;然而，我對我的功能的時間複雜性有點不確定。我覺得它效率很低，但我不確定這可能只是問題的本質。我想象有一種更好的方式來做到這一點，而不是我如何做到這一點。我最初的想法是，這將是O（n^2）的時間複雜性，但我認爲它可能實際上是最差的，因爲我使用了分裂函數。有什麼更好的方法來做到這一點？另外，我是否認爲這實際上比O（n^2）更差呢？我寫了一個函數，可以在保持單詞順序的同時，翻轉句子中每個單詞的字符。我不確定時間複雜度

public static String wordReverse(String string){ 

    //Split the string into an array such that each word is an element in the array 
    String[] arr = string.split(" "); 
    String result = ""; 

    //Iterate throught the elements in the array 
    for(String value : arr){ 
     String word = ""; 

    //Reverse the letters of the element, and append them to a temp string 
    for(int i = value.length(); i > 0; i--){ 
     word += value.charAt(i-1); 
    } 

    //Build the result string 
     result += word += " "; 
    } 

    //Return result string 
     return(result); 
}

來源

2016-09-19 Elroy Jetson

使用'StringBuilder'而不是''串連接''，你可以將複雜度從二次方降低到線性。 –

@MarkoTopolnik不正確。無論如何，最終的字節碼會導致字符串連接被編譯爲使用StringBuilder。無需對其進行硬編碼。 – Jacob

@Jacob最終的字節碼不會做這種事情。成爲我的客人，並檢查出來。 Java編譯器不會做任何這樣的花哨分析，以實現中間結果不逃避方法。 –

你不是更糟糕的是爲O（n^2）。其實，你是O（n）。

split（）是O（n），因爲它傳遞數組一次。

你倒過來也是O（n），因爲它檢查所有的字符。

在最差的情況下級聯爲O（n）。

來源

2016-09-19 19:09:48

級聯是O（n），它在O（n）循環中執行。所以... –

但是外環沒有超過整個輸入。所以在最壞的情況下，內循環每次只執行兩次。在內部循環的最壞情況下，外部循環將只執行一次。因此，O（n） –

內部和外部循環的組合採取了O（n）個步驟，但是您只計算爲一個步驟的連接實際上是O（n）本身。 –

您的方法的複雜性是O（n） - 線性時間。時間隨着單詞和字符的數量線性增加。

來源

2016-09-19 19:10:05 maxTrialfire

好吧，我的理解是錯誤的。順便說一下，我是一名學生，所以我非常期待清晰。我的印象是，當我按照我的方式嵌套for循環時，我不得不遍歷數組中的單詞，而且還要遍歷每個元素中的每個字符。這兩個循環讓我覺得這將是o（n^2）。謝謝（你的）信息。我會用大O符號做更多的練習。 –

嵌套循環並不一定意味着O（n^2）。如果你迭代你的整個輸入一次在外部循環，再次在內部循環，那麼它將是n^2。例如，看看冒泡排序如何工作。在你的情況下，內部循環只是處理下一個輸入，並不是總輸入的函數。希望有所幫助 – maxTrialfire

我寫了一個函數，可以在保持單詞順序的同時，翻轉句子中每個單詞的字符。我不確定時間複雜度

回答

相關問題