以下代碼在內存方面的複雜程度如何？

我從here讀了Big-O符號，並且在計算複雜度方面幾乎沒有問題。因此，對於下面的代碼，我計算了複雜度。需要你的投入相同。以下代碼在內存方面的複雜程度如何？

private void reverse(String strToRevers) 
    { 
     if(strToRevers.length() == 0) 
     { 
      return ; 
     } 
     else 
     { 
      reverse(strToRevers.substring(1)); 
      System.out.print(strToRevers.charAt(0)); 
     } 
    }

如果存儲器因子被認爲是隨後的上述代碼的n個字符的字符串的複雜度是O（n^2）。解釋是對於由n個字符組成的字符串，下面的函數將被遞歸地調用n-1次，並且每個函數調用創建一個單個字符的字符串（stringToReverse.charAT（0））。因此它是n *（n-1）* 2，轉換爲o（n^2）。讓我知道如果這是正確的？

來源

2010-03-28 Cshah

因此，它是n *（n-1）* 2，其轉換爲o（n^2）。讓我知道如果這是正確的？

差不多：它是n * (n-1)/2，而不是*2，這也是O（n^2）。請注意，o（n^2）（little-O）means something else，所以區別很重要。

這是假設我們正在考慮這是僞代碼。特定於語言的實現和智能編譯器可能能夠大幅縮短運行時間。例如，一個可以觀察到你簡單地反轉字符串的編譯器可能只是做一個就地反轉，即O（n）。

來源

2010-03-28 13:40:11

@John：對，它應該是n *（n-1）/ 2 – Cshah 2010-03-28 14:23:55

看起來像Java，所以它的不是 O（n ** 2）。這是因爲字符串共享底層的字符序列緩衝區;他們可以做到這一點，因爲他們是不可變的對象。

但它是堆棧空間中的O（n）。這不好。最好分配一個可變的工作緩衝區，將字符串反轉爲該字符串，然後一次打印整個批次。

來源

2010-03-28 13:46:06

+1。 'System.out'和其他小東西指向它是Java，'substring'不會複製原始的'String'字符數組。這是'String（String）'構造函數的一個原因。 – Phil 2010-03-28 13:55:00

爲了舉例，不要考慮在java中子字符串共享底層字符序列的事實。假設每次爲新字符串分配一個內存。 – Cshah 2010-03-28 14:20:09

以下代碼在內存方面的複雜程度如何？

回答

相關問題