6

私はこのメソッド isPalindrome() を持っており、その時間の複雑さを見つけようとしています。また、コードをより効率的に書き直そうとしています。

boolean isPalindrome(String s) {
    boolean bP = true;
    for(int i=0; i<s.length(); i++) {
        if(s.charAt(i) != s.charAt(s.length()-i-1)) {
            bP = false;
        }
    }
    return bP;
}

これで、このコードが文字列の文字をチェックして、前の文字と同じかどうかを確認し、同じ場合は bP を変更しないことがわかりました。

そして、操作が s.length()、s.charAt(i)、および s.charAt(s.length()-i-!)) であることを知っていると思います。

時間の複雑さを O(N + 3) にすると思いますか? これは正しいです。

また、これをより効率的にするために、文字を一時的な文字列に格納するとよいでしょうか?

4

12 に答える 12

16

それはただのO(N)です。

O(N+3) と言うのはあまり意味がありません - 定数因数は無視されます。

不一致が見つかったときにブレークアウトすることで、より速くすることができます。

bP = false;
break;

(それが O(N) であるという事実を変えるわけではありませんが、ほとんどの場合は高速化されます。)

これは正しくありません:

このコードは、文字列の文字をチェックして、前の文字と同じかどうかを確認します

先頭の文字と末尾の文字が一致するかどうかをチェックする、つまり単純な回文チェッカーです。

もう 1 つの高速化はループするまでs.length()/2です。そうしないと、回文である文字列に対してすべての比較を 2 回行うことになります。

于 2009-08-23T13:32:40.993 に答える
13

指定されたコードは、文字 "N" が文字 "length-N" と同じかどうかをチェックすることによって、文字列が回文であるかどうかをチェックしているように見えます。すでに述べたように、次の方法で効率を高めることができます。

  • 前半のみ確認
  • 不一致を見つけるとすぐに抜け出す (false を返す)

それらの提案に、私は追加します

  • 変更されないため、ループのたびに s.length() を繰り返し再計算しないでください。

すべてを考えると：

boolean isP(String s) {
  int l = s.length();
  int l2 = l/2;
  int j = l - 1;
  for(int i=0; i<l2; i++) {
    if(s.charAt(i) != s.charAt(j)) {
        return false;
    }
    j--;
  }
  return true;
}
于 2009-08-23T13:37:31.847 に答える
6

これはおそらく Java で最も効率的な実装です。

    public static boolean isP(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < (chars.length / 2); i++) {
            if (chars[i] != chars[(chars.length - i - 1)])
                return false;
        }
        return true;
    }

利点：

  • 違いを一目見ただけで戻ります。
  • 直接 char[] アクセスを使用して、charAt で行われる境界チェックを回避します。
  • 文字列全体ではなく、文字列の半分だけを繰り返します。

それは、他のすべての提案されたソリューションと同様に、まだ O(N) です。

非常に大きな文字列の提示されたソリューションの時間を測定しました (ナノ秒単位の時間):

 Aran:           32244042
 Andreas:        60787894
 Paul Tomblin:   18387532

まず、上記の測定はクライアント VMで行われました。したがって、計算i < (chars.length / 2)は定数としてインライン化されませんでした。-server Vm パラメータを使用すると、より良い結果が得られました。

 Aran:           18756295
 Andreas:        15048560
 Paul Tomblin:   17187100

少し極端にするには:

最初に警告の言葉: 使用/発送する予定のプログラムでこのコードを使用しないでください。

コメントで指摘されているように、隠れたバグが含まれており、Java APIに従わず、エラー処理もありません。これは純粋に、ダーティ トリックによって得られる理論上のパフォーマンスの向上を示すためのものです。

文字列クラスは内部的に防御的なコピーを作成するため、文字列から配列をコピーするときにオーバーヘッドが発生します。

文字列から元の char[] を直接取得すると、文字列でリフレクションと unsave 操作を使用することを犠牲にして、パフォーマンスを少し絞り出すことができます。これにより、さらに 20% のパフォーマンスが得られます。

public static boolean isPReflect(String s) {
    char[] chars = null;
    try {
        final Field f = s.getClass().getDeclaredField("value");
        f.setAccessible(true);
        chars = (char[]) f.get(s);
    }
    catch (IllegalAccessException e) {
    }
    catch (NoSuchFieldException e) {
    }

    final int lenToMiddle = chars.length / 2;
    for (int i = 0; i < lenToMiddle; i++) {
        if (chars[i] != chars[(chars.length - i - 1)]) 
            return false;
    }
    return true;
}

時間:

 Aran:           18756295
 Andreas1:       15048560
 Andreas2:       12094554
 Paul Tomblin:   17187100
于 2009-08-23T14:02:04.343 に答える
4

2 つの反対のポインターを使用した別のソリューションを次に示します。

boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
        ++i;
        --j;
    }
    return i >= j;
}

複雑さは再びO ( n ) です。

もう少し詳しく説明します。すべての操作のコストが 1 ユニットであるとしましょう。比較、代入、算術演算、関数呼び出しには、それぞれ 1 単位のコストがかかります。isPalindromeしたがって、最悪の場合 (回文である)のコストの呼び出しはs、たとえば次のようになります。

  4 + n/2 · (3 + 4) + 1
= 5 + n/2 · 7
= 5 + 7/2 · n

また、定数係数 (ここでは 5 + 7/2) が省略されているため、5 + 7/2 · n ∈ O ( n ) になります。

于 2009-08-24T09:41:01.267 に答える
3

O(N)です。N=s.length() の場合、N 回の比較を行っています。1 文字の比較であるため、各比較には O(1) 時間がかかります。

+3 は重要ではありません。漸近表記法は最高次の項のみを考慮するためです。

于 2009-08-23T13:33:29.307 に答える
2

まず、「最悪の場合」の複雑さがO(N)任意の入力文字列の場合よりも優れている場合、この問題に対する単一スレッドのソリューションはあり得ません。簡単に言えば、アルゴリズムは最悪の場合、文字列内のすべての文字を調べる必要があります。O(N)理論的には、ハードウェアの並列処理を使用して改善できます。つまり、文字列のさまざまな部分で動作する無限にスケーラブルな数のプロセッサがあります。実際には、スピードアップをまったく達成するのは難しいでしょう。入力文字列 (または関連する部分) を各プロセッサに送信するコストは、私が知らない解決策がない限り、「O(N)」になります。

第二に、ご覧O(N)のとおり、動作は最終的な答えではありません。また、乗法定数を N -> 無限大として考慮する必要があり、N の値が小さい場合はより少ない項を考慮する必要があります。

第三に、@dfa は、マイクロ最適化はあなたの仕事ではないと言っています。彼は正しい道を進んでいますが、それほど明確ではないと思います。IMO、1)アプリケーションを可能な限り高速に実行する必要があり、2)アプリケーションのプロファイリングで、この特定の計算が実際に重大なボトルネックであることが示されない限り、マイクロ最適化は時間の無駄です。

最後に、ある特定のハードウェア プラットフォーム/JIT コンパイラでプログラムを高速化するマイクロ最適化は、別のハードウェア プラットフォームでは低速化する可能性があります。複雑なマイクロ最適化コードは、JIT コンパイラが効率的なコードを生成するのが困難です。また、リフレクションを使用して (たとえば) String クラスの内部にアクセスすると、一部のプラットフォームではコードが実際に失敗する可能性があります。(Java クラス ライブラリの仕様には、文字列に「値」と呼ばれるプライベート フィールドがあるとは書かれていませんchar[]!!!)

于 2009-08-23T23:14:43.687 に答える
1

では、まず第一に、メソッドは何をすることになっているのでしょうか?

私の推測: 文字列が回文かどうかを判断します。

明らかに、O(N) の下でそれを取得することはできません。

O(N+3) == O(N)

もう 1 つの質問は、それが最も効率的なソリューションであるかということです。そうでないかもしれない。

改善の余地：

  1. 半分に切る。すべての文字を 2 回チェックします (Michiel Buddingh が提案したように)。

  2. 事前に文字配列を取得します。これにより、内部で発生するいくつかのインデックス チェックが省略されますchatAt()。

他のすべての操作charAt()およびlength()は、標準の String 実装を使用した O(1) です。

于 2009-08-23T13:35:54.780 に答える
0

最初の改善点: 不一致を見つけたらブレークできますよね?

于 2009-08-23T13:32:39.027 に答える
0

(i == (s.length() / 2)+1) で停止することにより、関数の複雑さを半分に減らすことができます。Big O の観点からは関係ありませんが、それでもかなりの利益です。

于 2009-08-23T13:34:04.657 に答える
0

Big Oの複雑さには、常にコスタントがありません (N->oo の場合、コスタントは重要ではないため)。したがって、時間の複雑さは単純O(n)です。

また、これをより効率的にするために、文字を一時的な文字列に格納するとよいでしょうか?

これはあなたの仕事ではありません。JIT コンパイラーは、このマイクロ最適化を処理します。

于 2009-08-23T13:35:10.710 に答える
0

ループ内の操作を一定時間で実行できると仮定すると、複雑さは O(N) になります。「Big-O」表記は純粋な速度ではなく成長を測定するため、一定の要因は無視できます。これにより、O(N+3) は O(N) に等しいという結論が得られます。

于 2009-08-23T13:36:36.870 に答える
0

または、単に行うことができます

def isPalindrome?(x)
 return x == x.reverse
end

これはまだ O(n) 時間の複雑さです。

于 2013-05-11T15:06:13.523 に答える