該功能的大O符號是什麼？

我寫了一個函數，我需要知道它的大O符號。我試圖解決這個問題，我得到O（N^2），但是我被告知這不是正確的答案。該功能的大O符號是什麼？

有人可以告訴我什麼是正確的符號，也是一步一步解釋他們是如何來到這個答案？

該功能如下。

預先感謝

public static string Palindrome(string input) 
    { 
     string current = string.Empty; 
     string longest = string.Empty; 

     int left; 
     int center; 
     int right; 


     if (input == null || input == string.Empty || input.Length == 1) { return input; } 


     for (center = 1; center < input.Length -1; center++) 
     { 
      left = center - 1; 
      right = center + 1; 

      if (input[left] == input[center]) 
      { 
       left--; 
      } 

      while (0 <= left && right < input.Length) 
      { 
       if (input[left] != input[right]) 
       { 
        break; 
       } 

       current = input.Substring(left, (right - left + 1)); 

       longest = current.Length > longest.Length ? current : longest; 

       left--; 
       right++; 
      } 
     } 
     return longest; 
    }

來源

2012-10-26 Reznoir

第一個'for'循環給你'N'迭代。 'while'循環循環'N/2'次最差情況和'1'最好情況。 – Blender

@Blender，while循環需要O（n^2）而不是O（n），請參閱我的答案以獲取詳細信息。 –

這功課嗎？ xD – evotopid

這是O（n^3）算法：

這部分帶爲O（n^2）：

//爲O（n ）次循環

 while (0 <= left && right < input.Length) 
     { 
      if (input[left] != input[right]) 
      { 
       break; 
      }

//服用子是O（n）

  current = input.Substring(left, (right - left + 1)); 

      longest = current.Length > longest.Length ? current : longest; 

      left--; 
      right++; 
     }

也有是外爲O（n），for循環，這將導致O（N * N^2）。

你可以通過改變該行提高你的算法：

current = input.Substring(left, (right - left + 1)); 
    longest = current.Length > longest.Length ? current : longest;

到：

currentLength = right - left + 1; 
    if(currentLength > longest) 
    { 
    longest = current.Length > longest.Length ? current : longest; 
    longestLeft = left; 
    longestRight = right; 
    }

終於從longestLeft返回一個字符串來longestRight。實際上避免多次使用substring方法。

來源

2012-10-26 07:17:17

非常感謝，我完全忽略了子字符串函數 – Reznoir

的if (input[left] != input[right])語句執行爲O（n^2）倍，因此是它後面的幾個任務，尤其是：

current = input.Substring(left, (right - left + 1));

在子串函數典型實現方式中，字符的序列從複製將字符串轉換爲新的字符串對象。副本是O（n）操作，導致循環和子字符串操作的O（n^3）時間。

人們可以通過移動分配到current和longest到while構建體的閉括號之後解決問題。但請注意，left--;和right++;然後將已經執行的一個時間比在現有的代碼多，所以分配給current變得

current = input.Substring(left+1, (right-1 - (left+1) + 1));

或

current = input.Substring(left+1, (right-left-1));

因此，O（n）的子串操作最多完成O（n）次。

來源

2012-10-26 07:28:18

該功能的大O符號是什麼？

回答

相關問題