تعقيد وقت طباعة الأعداد الأولية ضمن نطاق?
-
29-09-2020 - |
سؤال
لقد كتبت إجابة على هذا السؤال الذي يسأل عن ما يلي:
ما هو تعقيد الوقت للرمز المعطى الذي يطبع الأعداد الأولية من 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$ تدوين لحالة معينة.
الآن سؤالي:ما هي الطريقة الصحيحة رسميا لوصف تعقيد الوقت من خوارزمية معينة?هل منطقتي صحيحة أم أنها مجرد خطأ?
المحلول
على حد سواء " تعقيد الوقت هو O س (نهاية \كدوت \ الجذر التربيعي{نهاية}))"و" تعقيد الوقت هو O س ((بداية نهاية) \كدوت \ الجذر التربيعي{نهاية}))"هي عبارات صحيحة (بافتراض أنه يمكن إجراء العمليات الحسابية على الأعداد الصحيحة المعنية في وقت ثابت).
الحد الأعلى الثاني هو أكثر إحكاما في بعض الحالات.على سبيل المثال ، الإعداد start البداية = النهاية-10$ يبقى الجزء العلوي الأول دون تغيير بينما يبسط الجزء الثاني إلى O س (\الجذر التربيعي{نهاية})).
لاحظ أيضا أن " في notation التدوين represents يمثل حجم المشكلة ، وهو النطاق بين البداية والنهاية في حالتك."غير صحيح.حجم (أي ترميز معقول) المثال هو O س (\نهاية السجل)).
نصائح أخرى
وظيفة الخاص بك فيندبريميورنوت (ن) يعمل في O س (ن^{1/2})) في أسوأ الحالات.غالبا ما يكون وقت التنفيذ أسرع.على سبيل المثال للأرقام الزوجية ن ، ترجع الدالة بعد قسم واحد.ولكن بالنسبة للأعداد الأولية ، حيث يتم اختبار جميع المقسومات حتى الجذر التربيعي (ن) ، فإن وقت التنفيذ هو بالفعل Th \ ثيتا (ن^{1/2})).وفرصة أن عدد صحيح عشوائي س هو رئيس حوالي س / سجل س.
سيكون عليك التحقق من متوسط عدد الأقسام بالضبط.مع الخوارزمية الخاصة بك ، والتي يمكن تحسينها ، وعدد من الانقسامات على الأقل حول (نهاية البداية) * الجذر التربيعي (ن) / سجل ن وعلى الأكثر حول (نهاية البداية) * الجذر التربيعي (ن) الانقسامات.
إذا كنت ترغب في طباعة الأعداد الأولية ، ستجد أن الطباعة لديها عامل ثابت كبير أن وقت تنفيذ الطباعة حول (نهاية البداية) / سجل ن الأعداد الأولية هو أكبر بكثير من الوقت لطباعة الأعداد الأولية ، لأي نطاق معقول من الأعداد الأولية.