2

こんにちは、読んでくれてありがとう。私は宿題に取り組んでいます。文字列と比較して、ある文字列が別の文字列のサブ文字列であるかどうかを確認するメソッドを作成しました。これを行うための組み込みメソッドがすでにあることを私は知っています。割り当ては私がそれらを使用することを許可していません。とにかく、以下のコードは機能しています。

Big-O表記を使用してアルゴリズムの複雑さを分析する必要があります。外側のループは文字列の長さと同じ回数だけ実行されるため、線形時間で実行されることがわかります。したがって：O（n）

内側のループは異なり、発生する場合と発生しない場合があります。発生する場合は、入力である2番目の文字列の長さより前に終了する場合があります。したがって：O（logn）

したがって、複雑さはO（n * logn）であるように見えます。これはO（n）に単純化されますか、それとも現在の形式のままですか？または、内側のループがO（logn）であるというのは間違っていますか？

import java.util.Scanner;

public class HW3q6 {
public static void main(String[] args) {
    Scanner userInput = new Scanner( System.in );
    System.out.println("Please enter the first string: ");
    char[] charArray1 = userInput.nextLine().toUpperCase().toCharArray();
    System.out.println("Please enter the second string: ");
    char[] charArray2 = userInput.nextLine().toUpperCase().toCharArray();

    System.out.println("The second string is a substring of the first: " + subString(charArray1, charArray2));

}

private static boolean subString(char[] charArray1, char[] charArray2) {
    int counter = 0;
    for (int i = 0; i < (charArray1.length + 1) - charArray2.length ; i++) {
        if (charArray1[i] == charArray2[0]) {
            for (int n = 0; n < charArray2.length; n++) {
                if (charArray1[i+n] == charArray2[n]) {
                    counter++;
                }
            }
            if (counter == charArray2.length) {
                return true;
            } else
                counter = 0;
        }
    }
    return false;

}
}
4

4 に答える 4

2

内側のループはlogNではありません。Big Oは、最悪の場合の複雑さを測定します。あなたのコードから理解できるように、内側のループはN（文字列の長さ2）回実行できます。説明は次のとおりです。

aaaaaaaaとaaacという2つの文字列があるとすると、外側のループは最初の文字と一致し、内側のループに移動してすべての文字をチェックし、falseを認識します。次に、外側のループが2番目の文字列の先頭を最初の文字列の2番目の文字と再び一致させ、次に2番目の文字列のすべての文字がfalseを認識していることを再度確認します。これは、最初の文字列のM文字と2番目の文字列のN文字に当てはまり、O（MN）アルゴリズムを生成します。これは、M = c * N（cは定数）を考慮するとO（N ^ 2）です。

お役に立てれば。

于 2013-01-30T23:01:45.030 に答える
2

私はあなたがすでに答えを受け入れたのを見ます。しかし、時間計算量は、実際O(m*(n-m+1))にmは、小さいテキストとn大きいテキストがどこにあるかということです。この区別が重要であることを確認するには、mとnの数値をいくつか選び、計算します。O(mn)Big-O表記に関しては、とO(m*(n-m+1))以降の間に大きな違いはないという議論がある場合O(mn) > O(m*(n-m+1))、複雑さはO(n^2)以降であると言えますO(n^2) > O(mn) > O(m*(n-m+1))。また、コードが適切なエラーチェックを行っていません。いくつかのヒントについては、文字列照合についてGeekviewpoint.comを参照してください。

于 2013-01-30T23:29:52.027 に答える
1

O(NlogN)と同等ではありませんO(N)

ただし、内側のループが間違っているというあなたの推論O(logN)は誤りです。それが「起こるかもしれないし、起こらないかもしれない」という事実は必ずしもそれを成し遂げるわけではありませんO(logN)。たとえば、内側のループが「平均して約半分の時間」発生した場合、寄与は次のようになりC * 1/2 Nます。すなわちO(N)。

現在、コードを詳細に分析する時間はありませんが、最良、平均、および最悪の場合の複雑さを調べる必要があるようです。

（たとえば、O(NlogN)平均ではあるが最悪の場合の複雑さを持つクイックソートアルゴリズムの古典的な形式O(N^2)。）

于 2013-01-30T22:43:05.833 に答える
1

mellamokbが指摘したように、内側のループは線形時間で実行されます。したがって、アルゴリズム全体はO（mn）になります。ここで、mとnは2つの文字列の長さです。

于 2013-01-30T23:00:21.947 に答える