0

我写了一个函数，我需要知道它的大 O 符号。我自己尝试过解决这个问题，我得到了 O(N^2)，但是有人告诉我这不是正确的答案。

有人可以告诉我正确的符号是什么，并逐步解释他们是如何得出这个答案的吗？

函数如下。

提前致谢

    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;
    }
4

2 回答 2

1

这是 O(n^3) 算法：

这部分需要 O(n^2)：

// O(n) 次 while 循环

        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-26T07:17:17.897 回答
0

该if (input[left] != input[right])语句被执行 O(n^2) 次，它后面的几个赋值也是如此，特别是：

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

在子字符串函数的典型实现中，字符序列从字符串复制到新的字符串对象。复制是一个 O(n) 操作，导致循环和子字符串操作的 O(n^3) 时间。

可以通过将分配移到current和移到构造longest的右括号之后来解决问题。while但请注意，left--;andright++;将比现有代码多执行一次，因此赋值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-26T07:28:18.973 回答