كتب الوقت شبه الخطي
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
الوقت شبه الخطي (معلومة)
ويقال إن الخوارزمية تعمل في زمن القصبة (يشار إليه أيضاً بوقت الخط الزمني) إذا كانت T ( n ) = O ( n log k n ) لبعض k الثابت الموجب ؛ الوقت linearithmic هو الحال ك = 1. عن طريق لينة O تدوين هذه الخوارزميات هي O ( ن ). خوارزميات الوقت الكاسيلية هي أيضاً O ( n 1 + ε ) لكل ثابت ε> 0 ، وبالتالي يتم تشغيلها أسرع من أي خوارزمية زمن متعدد الحدود تتضمن حدودها الزمنية مصطلح n c لأي c > 1.
- فرز الموضعي الموضعي ، O ( n log 2 n )
- Quicksort ، O ( n log n ) ، في نسخته العشوائية، لديه وقت تشغيل هو O ( n log n ) في توقع على مدخلات الحالة الأسوأ. تحتوي النسخة غير العشوائية على وقت تشغيل O ( n log n ) فقط عند النظر في متوسط تعقيد الحالات.
- Heapsort ، O ( n log n )، merge sort ، introsort ، binary tree sort، smoothsort ، sortience sorting ، etc. in worst worst
- تحويلات فورييه السريعة ، O ( n log n )
- حساب مجموعة monge ، O ( n log n )
في كثير من الحالات، ن · تسجيل ن إدارة الوقت هو ببساطة نتيجة أداء وΘ (سجل ن ) عملية ن مرات (للتدوين، انظر Big O notation § Family of Bachmann–Landau notations ). على سبيل المثال، يؤدي فرز الشجرة الثنائية إلى إنشاء شجرة ثنائية عن طريق إدخال كل عنصر في الصفيف n-sized واحدًا تلو الآخر. نظرًا لأن عملية الإدراج على شجرة بحث ثنائية التوازن الذاتي تأخذ وقت O (log n ) ، فإن الخوارزمية بأكملها تأخذ O ( n log n ) time.
تتطلب أنواع المقارنة عدد المقارنات O ( n log n ) على الأقل في أسوأ الحالات لأن log ( n !) = Θ ( n log n ) ، بواسطة تقريب ستيرلنغ Stirling . كما أنها تنشأ في كثير من الأحيان من علاقة التكرار T ( n ) = 2 T ( n / 2) + O ( n ).
