تعقيد وقت طباعة الأعداد الأولية ضمن نطاق?

Question

لقد كتبت إجابة على هذا السؤال الذي يسأل عن ما يلي:

ما هو تعقيد الوقت للرمز المعطى الذي يطبع الأعداد الأولية من start إلى end?هل هو O س (نهاية * \ الجذر التربيعي{ن}))?

/**
 * 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);
}

إشعار:هذا ليس قانون بلدي.انها من قبل ماهيش87.

جوابي على ذلك هو:

---

في قضيتك $n$ هو end - start.في $O$ التدوين $n$ يمثل حجم المشكلة ، وهو النطاق بين start و end في قضيتك.في $O$ تدوين كنت مهتما في أسوأ الحالات ، وبالتالي يمكننا أن نفترض أن start دائما 0.الآن $n$ هو مجرد اسم مستعار ل end.

كما حددنا $n$, ، من الواضح أن printPrimeSeries هو فقط O س (ن)$ (من 0 إلى end).تستخدم الطريقة findPrimeOrNot هذا يتكرر من 2 إلى Math.sqrt(n), ، وهو O س (\الجذر التربيعي{ن})).الجمع بين كليهما هو O س (ن) س (\الجذر التربيعي{ن})), ، وهو فقط O س (ن \ الجذر التربيعي{ن})).

لاحظ أن $O$ يخبرك التدوين بشيء عن السلوك المقارب للخوارزمية.لا يهم كثيرا إذا كان هناك 2 المعلمات ، على الأقل في هذه الحالة.

لذا نعم ، افتراضك صحيح تماما (تجاهل أنك كتبت end بدلا من $n$).

---

اقترح مستخدمون آخرون أن الإجابة الصحيحة هي O س ((نهاية-بداية) \ الجذر التربيعي{نهاية})).أعتقد أن هذه وجهة نظر صحيحة ولكنها لا تقدم أي معلومات مفيدة من حيث $O$ تدوين لحالة معينة.

الآن سؤالي:ما هي الطريقة الصحيحة رسميا لوصف تعقيد الوقت من خوارزمية معينة?هل منطقتي صحيحة أم أنها مجرد خطأ?

Answer 1

على حد سواء " تعقيد الوقت هو O س (نهاية \كدوت \ الجذر التربيعي{نهاية}))"و" تعقيد الوقت هو O س ((بداية نهاية) \كدوت \ الجذر التربيعي{نهاية}))"هي عبارات صحيحة (بافتراض أنه يمكن إجراء العمليات الحسابية على الأعداد الصحيحة المعنية في وقت ثابت).

الحد الأعلى الثاني هو أكثر إحكاما في بعض الحالات.على سبيل المثال ، الإعداد start البداية = النهاية-10$ يبقى الجزء العلوي الأول دون تغيير بينما يبسط الجزء الثاني إلى O س (\الجذر التربيعي{نهاية})).

لاحظ أيضا أن " في notation التدوين represents يمثل حجم المشكلة ، وهو النطاق بين البداية والنهاية في حالتك."غير صحيح.حجم (أي ترميز معقول) المثال هو O س (\نهاية السجل)).

Answer 2

وظيفة الخاص بك فيندبريميورنوت (ن) يعمل في O س (ن^{1/2})) في أسوأ الحالات.غالبا ما يكون وقت التنفيذ أسرع.على سبيل المثال للأرقام الزوجية ن ، ترجع الدالة بعد قسم واحد.ولكن بالنسبة للأعداد الأولية ، حيث يتم اختبار جميع المقسومات حتى الجذر التربيعي (ن) ، فإن وقت التنفيذ هو بالفعل Th \ ثيتا (ن^{1/2})).وفرصة أن عدد صحيح عشوائي س هو رئيس حوالي س / سجل س.

سيكون عليك التحقق من متوسط عدد الأقسام بالضبط.مع الخوارزمية الخاصة بك ، والتي يمكن تحسينها ، وعدد من الانقسامات على الأقل حول (نهاية البداية) * الجذر التربيعي (ن) / سجل ن وعلى الأكثر حول (نهاية البداية) * الجذر التربيعي (ن) الانقسامات.

إذا كنت ترغب في طباعة الأعداد الأولية ، ستجد أن الطباعة لديها عامل ثابت كبير أن وقت تنفيذ الطباعة حول (نهاية البداية) / سجل ن الأعداد الأولية هو أكبر بكثير من الوقت لطباعة الأعداد الأولية ، لأي نطاق معقول من الأعداد الأولية.