範囲内の印刷素数の数の複雑さは？

Question

私はこの質問を書いています。

startからendに素数を印刷する特定のコードの時間の複雑さは何ですか？それは $ O（end * \ sqrt {n}）$ ？

/**
 * Print prime numbers between start and end inputs
 * Time-Complexity: O(end * sqrt(n))
 * Space-Complexity: O(1) only one value as input
 * @param start, end
 * @return
 */
public void printPrimeSeries(int start, int end) {
    for (int i = start; i < end; i++) {
        if (findPrimeOrNot(i)) {
            System.out.println("The value " + i + " is a prime number");
        }
    }
}

public boolean findPrimeOrNot(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Enter start number for prime:");
    int startInput = scanner.nextInt();

    System.out.println("Enter end number for prime:");
    int endInput = scanner.nextInt();

    PrimeNoSeries primeNoSeries = new PrimeNoSeries();
    primeNoSeries.printPrimeSeries(startInput, endInput);
}

.

通知：それは私のコードではありません。それは mahesh87 。

それに対する私の答えは次のとおりです。

---

あなたの場合 $ n $ はend - startです。 $ O $ 表記 $ n $ は、startとendの範囲です。あなたの場合。 $ O $ 表記の最悪の場合に興味があるため、startが常に0であると想定できます。 $ n $ は、endのためのエイリアスです。

$ n $ を定義したので、printPrimeSeriesは $ o（n）$ （0からendまで）。このメソッドは、 $ o（\ sqrt {n}）$ であるfindPrimeOrNotから2に反復するMath.sqrt(n)を使用します。両方の組み合わせは $ o（n）o（\ sqrt {n}）$ です。これは $ O（n \ \ sqrt {n}）$ 。

$ on $ 表記法は、アルゴリズムの漸近的な振る舞いについて何かを示しています。少なくともこの場合、2つのパラメータがある場合はあまり重要ではありません。

そうはい、あなたの仮定は完全に正しいです（ $ n $ の代わりに作成したことを無視します）。

---

他のユーザーは、正しい回答が $ o（（end-start）\ sqrt {end}）$ です。これは有効な観点となると思いますが、 $ O $ 表記の点では、与えられたケースの表記法では有益な情報を提供していません。

今私の質問：与えられたアルゴリズムの時間の複雑さを説明するための正式に正しい方法は何ですか？私の推論は有効ですか、それとも間違った間違っているのですか？

Answer 1

どちらも $ o（end \ cdot \ sqrt {end}）$ "と"時間の複雑さは $ O（（開始末尾）\ cdot \ sqrt {end}）$ "は正しいステートメントです（関与する整数の算術演算が一定に実行できると仮定して）

2番目の上限はきつくなることがあります。たとえば、 $ start= end-10 $ を設定すると、2番目の上限は変わりませんが、2番目の1つは $ o（\sqrt {end}）$ 。

は、「NotationⅢでは問題サイズを表します。これは、あなたの場合の開始と終了の範囲です。」偽です。 インスタンスのサイズ（任意の合理的なエンコーディング）のサイズは $ o（\ log end）$ です。

Answer 2

あなたの関数findPrimeOrnot（n）は、最悪の場合の $ o（n ^ {1/2}）$ で実行されます。多くの場合、実行時間は速くなります。たとえば、N偶数nの場合、関数は単一の部門の後に戻ります。しかし、すべての除数がすべてSQRT（N）にテストされている場合、実行時間は確かに $ \ theta（n ^ {1/2}）$ です。ランダム整数xがPrimeである可能性はx / log xです。

分割の平均数が正確にどのようなものであるかを確認する必要があります。あなたのアルゴリズムを改善することができるにつれて、部門の数は少なくとも（終了開始）* sqrt（n）/ log n、そして最大（終了 - 開始）の部門（N）部門です。

プリムを印刷したい場合は、印刷の実行時間（終了開始）/ log nのプライムがプリムを印刷するための時間よりはるかに大きいという大きな一定要素を持っていることがわかります。任意の合理的な範囲のプリムのために。