6 
public void foo(int n, int m) {
    int i = m;

    while (i > 100) {
        i = i / 3;
    }
    for (int k = i ; k >= 0; k--) {
        for (int j = 1; j < n; j *= 2) {
            System.out.print(k + "\t" + j);
        }
        System.out.println();
    }
}

複雑さはO（logn）になると思いました。
つまり、内側のループと外側のループの積です -- 100 回を超えて実行されることはないため、省略できます。

私が確信していないのは while 句です。Big-O の複雑さに組み込む必要がありますか? 非常に大きなi値の場合、影響を与える可能性があります。または算術演算は、どのスケールでも問題なく、基本演算としてカウントされ、省略できますか?

4

3 に答える 3

11

whileループは、以下になるまで でO(log m)割り続けるためです。m3100

あなたのケースでは 100 は定数なので、無視できます。

を超えるまで掛けるので、内側のループはO(log n)あなたが言ったとおりです。j2n

したがって、全体の複雑さはO(log n + log m)です。

または算術演算は、どのスケールでも問題なく、基本演算としてカウントされ、省略できますか?

はい、算術演算は通常省略できます。ただし、言語にも依存します。これはJavaのように見え、プリミティブ型を使用しているようです。この場合、算術演算を考慮しても問題ありませんO(1)。はい。しかし、たとえば大きな整数を使用する場合、足し算と掛け算はもはやO(1).

于 2010-06-06T13:00:00.870 に答える
5

複雑さは O(log m + log n) です。

while ループは log3(m) 回 (定数 (log3(100))) 実行されます。外側の for ループは一定回数 (約 100 回) 実行され、内側のループは log2(n) 回実行されます。

于 2010-06-06T12:57:40.423 に答える
2

while ループは m の値を 3 で割るので、そのような操作の回数は log(base 3) m になります。

for ループの場合、操作の数は 2 つの合計と考えることができます。

summation (k = 0 to i) [ summation (j = 0 to lg n) (1)] summation (k = 0 to i) [lg n + 1] (lg n + 1) ( i + 1) は合計になりますログ用語が支配的な操作の数。

そのため、複雑さは O(log (base3) m + lg n) です。ここで、lg は log から base 2 を指します。

于 2013-01-25T09:30:36.127 に答える