تحليل الخوارزميات
إن تحليل خوارزمية هوتحديد مقدار الموارد (مثل الوقت وسعة التخزين) اللازمة لتطبيقها. معظم الخوارزميات تصمم للعمل مع مدخلات ذات حجم مطلق. يعبر عادة عن كفاءة أووقت التشغيل اللازم لخوارزمية بتابع يتبع لحجم المدخلات إلى عدد المراحل (تعقيد الزمن) أوأمكنة التخزين (تعقيد المكان).
تحليل الخواروميات جزء مهم من نظرية التعقيد الحسابي التي تقدم تقديرات نظرية للموارد اللازمة من أجل إنجاز خوارزمية لحل مسألة تحسيبية. وتقدم هذه التقديرات نظرة أفضل للبحث عن خوارزميات كفوءة.
غالباً ما يستخدم المعنى المقارب لتحديد درجة تعقيد خوارزمية في تحليل الخوارزميات، ونقصد بذلك تقدير درجة التعقيد من أجل ولج عشوائي كبير. وتستخدم لهذا الغرض عدة تدوينات كتدوين أوه الكبيرة وتدوين أوميغا وتدوين ثيتا. على سبيل المثال ، فإن الوقت الذي يستغرقه البحث الثنائي يتناسب مع لوغاريتم حجم الدخل الخاضع للبحث،
يمكن في بعض الأحيان التوصل إلى قياسات دقيقة(وليست مقاربة) للكفاءة ولكن ذلك يحتاج عادة بعض الافتراضات المتعلقة بتطبيق معين للخوارزمية وهوما يسمى بنموذج التحسيب. ويمكن تعريف نموذج التحسيب من خلال حاسوب مجرد، كآلة تورنگ، أو/وافتراض تطبيق بعض العمليات في وحدة زمنية ما. عملى سبيل المثال ، إذا احتوت القائمة الخاضعة للبحث الثنائي على n عنصر، وكان بإمكاننا حتى نضمن حتى جميع نظرة على عنصر ما يمكن حتى يتم في وحدة زمنية واحدة، فإن الزمن اللازم لإرجاع جواب سيكون على الأكثر إلى إرجاع الجواب في log2 n + 1 وحدة زمنية.
انظر أيضا
- Amortized analysis
- تحليل مقارب
- Best, worst and average case
- تدوين أوه الكبيرة
- نظرية التعقيد التحسيبي
- NP-Complete
- تحليل عددي
- Polynomial time
- Program optimization
- Profiling (computer programming)
- Smoothed analysis
- تعقيد الزمن - تضم جدولاً برتب أبرز الخوارزميات
مصادر
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 1: Foundations, pp. 3-122.
- Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd Edition), Robert Sedgewick, Addison-Wesley Professional, ISBN 978-0201314526
- The Art of Computer Programming, Donald Knuth, Addison-Wesley
- Daniel A. Greene, Donald E. Knuth: Mathematics for the Analysis of Algorithms, Second Edition, Birkhäuser 1982. ISBN ثلاثة 7463-3102-X
