1

私はビッグオー記法について学んでいます。以下のコードでは、区切り文字をスキップして単語数をカウントするプログラムがあります。このアルゴリズムの場合、for ループは文の長さに対して行われ、文字列に対して反復処理を行う含まれるものもあります。したがって、私によると、このアルゴリズムの大きな oh 表記は O(n^3) になります。それは正しいですか、それとも大きな Oh 表記について何か不足していますか?

public class wordCount {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    String sentence = "How are you,zak;far: mon. day ?:";
    int count = 1;
    ArrayList<Character> delim = new ArrayList<Character>();
    delim.add(' ');
    delim.add(',');
    delim.add('.');
    delim.add(':');
    delim.add(';');
    delim.add('"');
    delim.add('\'');
    for (int i = 0; i != sentence.length() - 1; i++) {
        if (delim.contains(sentence.charAt(i))) {
            if (!delim.contains(sentence.charAt(i + 1))) {
                count++;
            }
        }
    }
    System.out.println("The count is: " + count);
}
}
4

4 に答える 4

6

いいえ、あなたはまったく正しくありません - O(n) のcontains"n" は、あなたが興味を持っている "n" と同じであると仮定しています。そうではありません - それは配列リストの長さです. この場合、それは文の長さではなく区切り文字の数です。

したがって、アルゴリズムは実際には O(N * M) です。ここで、N は文の長さ、M は区切り文字の数です。センテンスのみを入力として区切り文字のセットを定数として表示すると、アルゴリズム全体が O(N) になります。

2 回目に条件付きで呼び出しても、反復ごとcontainsの呼び出しの総数containsは 1 または 2 に過ぎません。(たとえば) 区切り文字の数や文のサイズまで増加することはありません。

于 2012-06-18T14:48:23.433 に答える
1

それほど単純ではありません。文字列の長さを N、長さをdelimMとします。

delim.contains(...)文字列内の文字ごとに1 回または 2 回 (O(M))呼び出すため、最終的な複雑さは O(N x M) になります。

于 2012-06-18T14:47:59.157 に答える
1

これは宿題のように感じられるので (そうであればhomeworkタグを追加してください)、解決策ではなくいくつかの観察結果を提供します。

ここには 2 つの異なる "N" があります。 の長さsentenceと のアイテムの数ですdelim。これらの数値は大きく異なる場合があります。

の大きなああ性能を理解する必要がありArrayList<T>.Containsます。それが何であるか知っていますか？

于 2012-06-18T14:49:06.160 に答える
0

ループ内にいくつのループがあるか (およびそれらのループがどこまで続くか) を考える必要があります。

3 つではなく、相互に 2 つを超えるループはありません。

for (int i = 0; i < sentence.length()-1; i++) { // loop level 1
    boolean isDelim = delim.contains(sentence.charAt(i));  // loop level 2
    if (!isDelim) continue;

    if (!delim.contains(sentence.charAt(i + 1)))  // loop level 2
        count++;
}
于 2012-06-18T14:55:24.350 に答える