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

forまた、O(n*n^2) を引き起こす外側の O(n)ループもあります。

次の行を変更することで、アルゴリズムを改善できます。

   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

ステートメントは O(n^2) 回実行され、if (input[left] != input[right])特にそれに続くいくつかの割り当ても同様です。

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

部分文字列関数の一般的な実装では、一連の文字が文字列から新しい文字列オブジェクトにコピーされます。コピーは O(n) 操作であり、ループと部分文字列操作に O(n^3) 時間かかります。

currentこの問題は、割り当てを構文longestの閉じ括弧の前後に移動することで解決できます。whileただし、left--;andright++;は既存のコードよりも 1 回多く実行されることに注意してください。したがって、への代入は次のように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 に答える