1

KMP のプレフィックス テーブルを埋めるためのコードを書きました。これは、このアルゴリズムの小さなバリエーションです。このアルゴリズム/実装が O(n) 時間で実行されることを確信できません。2 番目の再帰呼び出しが合計実行時間に与える影響を理解するのに苦労しています。何か助けはありますか？

    public void fillFailTable(int[] failTable,String p){
        failTable[failTable.length-1] = preLength(failTable,p);
    }

    private int preLength(int[] failTable,String s){

        if(s.length() == 1){
            return 0;
        }
        int n = s.length();
        int k = preLength(failTable,s.substring(0,n-1));

        failTable[n-2] = k;

        if(s.charAt(k) == s.charAt(n-1)){
            return k+1;
        }else{
            return preLength(failTable,s.substring(n-1-k));
        }
    }
4

1 に答える 1

0

それは実際にはかなり興味深いものです (なぜ私よりも賢い人がまだこれに答えていないのか不思議に思っています)。私はこれが正しいことに100％近いとは確信していないので、この説明を一粒の塩で受け取ってください（ただし、このメソッドはO（n）で実行されると100％言うことができます。大学の何年も前ですが、彼らはそれを説明してくれませんでした.d'uh、だから私は自分でそれを考え出さなければなりませんでした.

では、s.length = 2 の非常に基本的な例から始めましょう。

  • 各例では、最悪のシナリオだけを考えてみましょう。Big Oh に関心があるためです。つまり、2 番目の preLength() メソッドに入ります。
  • Big Oh を探すと、このコードの "k" (および preLength() によって返される値) が常に 0 になることがわかります。これは、下の画像でわかるように、非常に重要です。

s.length == 2

最初に最初の preLength() メソッドに入ります (* と呼びましょう)。これは s.length = 1 で呼び出され、すぐに 0 で戻ります。 k) != s.charAt(n-1)) 2 番目の preLength() に長さ = 1 の文字列を入力します (n=2 および k=0 であるため)。これも * にすぐに 0 を返します。これで、メソッドの呼び出しが終了します。全部で 3 つのメソッド呼び出しがありました。* と 2 つの preLength()。画像は次のとおりです。

ここに画像の説明を入力

s.length == 3

次に、s.length = 3 で開始する例を見てみましょう。お気づきのように、s.length = 2 で preLength() をすぐに呼び出します。前の例から、これには 3 つのメソッド呼び出しが必要であることがわかります。ここで、メソッド preLength(2) が今回戻ると、ネイティブの preLength(3) に戻り、これが再度 preLength(2) (else の 1 つ) を呼び出すことを覚えておく必要があります。これには、3 つのメソッド呼び出しが必要になります。したがって、合計で 2*3+1 回のメソッド呼び出しが必要です。これで 7 が得られます。ここでもイメージを示します (円は、円で示されている長さの文字列で preLength を呼び出したものです)。

ここに画像の説明を入力

結論

ご覧のとおり、これらすべてのメソッド呼び出しは対称的です。これは、ourkが常に0 に等しいためです。これは、2 番目の preLengt() が最初のものと同じサイズの文字列で呼び出されることを意味します。size の文字列のテーブルを計算するために必要なメソッド呼び出しの数を示す関数はどこにあるので、s.length = m必要な数がわかっている場合、それらの多くが必要になります。前に述べたように、メソッド呼び出しは対称であるため、これは機能します (これは、最悪の場合、常に k=0 と preLenght() が常に 0 を返すため、2* であり、最初に呼び出したメソッド呼び出しを 1 つ追加する必要があるためです)。 .m-1f(m) = 2*f(m-1)+1f(m)m

したがって、基本的に、入力 ( のサイズm) が増加するたびに、計算時間は 2 倍プラス 1 (2*m+1) になります。これは、私の理解では、この方法が最悪の場合 O(n) であることを意味します。

私が言ったように、これを一粒の塩で受け取ってくださいが、これが何らかの意味をなすことを願っています:)

于 2012-08-05T21:52:47.147 に答える