0

わかりましたので、ここで深刻な実行時ヘルプが必要です!

このメソッドは int 値を取り、その素数をチェックしてtrue、数値が実際に素数であるかどうかを返す必要があります。ループがi2 乗する必要がある理由を理解しています。最悪のシナリオは、数が素数 (または素数の倍数) の場合であることを理解しています。しかし、実際の実行時間を定量化する方法がわかりません。

数字 ( ) のパターンや相関関係、および発生するループの数を理解するために、自分でループを手動で実行しましたnが、文字通り、毎回同じトラップに陥り続けているように感じます。これについて新しい考え方が必要です！

ヒントがあります：

「整数のサイズを考える」

これにより、for ループ ( ) で実行される反復回数に関連して、数値内の整数のリテラル数を定量化する必要がありますfloor log(n)) +1。しかし、それは機能していませんか?! n明らかに平方根ではないことはわかっています。

Big O表記をお願いしています。

public class PrimeHunter 
{

    public static boolean isPrime(int n)
    {
        boolean answer = (n > 1) ? true : false; //runtime = linear runtime

        for (int i = 2; i * i <= n; i++) //runtime = ?????
        {   
            if (n % i == 0) //doesn't occur if it is a prime
            {
                answer = false;
                break;
            }

        }
        return answer; //runtime = linear runtime
    }
}
4

4 に答える 4

0

ループは 1 つだけです。実行するmaxi - 2 + 1回数はmaxi*maxi = n. そして、内部の操作は同じです（一定の時間がかかります（制限されます））。あなたはこれを考えすぎていたと思います。

実際には、あなたの教授が直面しているかもしれない小さなつまずきがあるかもしれません. モジュロ演算の時間計算量%. その場合、内項はまったく一定ではありません。

于 2013-10-20T04:42:31.953 に答える
0

これを視覚的に行う方法は、グラフを作成することです。

1 から 20 までの一連の値を選択します。x 軸が値で、y 軸がループが実行される最悪のケースの回数でnあるグラフをプロットします。n視覚化を取得する必要があります。

視覚化すると、より明確になるはずです。そうでない場合は、この同じグラフにいくつかの既知の Big-O 表記法をプロットして、それらを比較することができます。O(n)たとえば、線形値 ( )、指数値 ( O(n^2))、または対数 ( ) 値に近いO(log(n))ですか? より正確な Big-O 値が必要な場合は、そこから行くことができます。

それについて考える 2 番目の方法は、このビットに焦点を当てることです。

I understand why the loop only needs to go up to i squared

iではなくの観点から考えてみてくださいi*i。for ループは まで続きます。i*i = nここiで、 は反復回数です。を解きiます。

于 2013-10-20T03:39:28.087 に答える