该功能的大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符号是什么？

回答

相关问题