تحليل الخوارزميات
إن تحليل خوارزمية هو تحديد مقدار الموارد (مثل الوقت و سعة التخزين) اللازمة لتنفيذها. معظم الخوارزميات تصمم للعمل مع مدخلات ذات حجم مطلق. يعبر عادة عن كفاءة أو وقت التشغيل اللازم لخوارزمية بتابع يتبع لحجم المدخلات إلى عدد الخطوات (تعقيد الزمن) أو أمكنة التخزين (تعقيد المكان).
تحليل الخواروميات جزء مهم من نظرية التعقيد الحسابي التي تقدم تقديرات نظرية للموارد اللازمة من أجل إنجاز خوارزمية لحل مسألة تحسيبية. وتقدم هذه التقديرات نظرة أفضل للبحث عن خوارزميات كفوءة.
غالباً ما يستخدم المعنى المقارب لتحديد درجة تعقيد خوارزمية في تحليل الخوارزميات، ونقصد بذلك تقدير درجة التعقيد من أجل دخل عشوائي كبير. وتستخدم لهذا الغرض عدة تدوينات كتدوين أوه الكبيرة وتدوين أوميغا وتدوين ثيتا. على سبيل المثال ، فإن الوقت الذي يستغرقه البحث الثنائي يتناسب مع لوغاريتم حجم الدخل الخاضع للبحث، )، أو كما يقال "في وقت لوغاريتمي". وتستخدم عادة التقديرات المقاربة، والسبب يعود إلى أن عدة تنفيذات للخوارزمية قد تؤدي إلى تفاوت في الكفاءة. وعلى كل حال، فإن كفاءة أي من تنفيذين "معقولين" لخوارزمية يرتبط بمعامل ضرب ثابت يسمى بالثابت المخفي.
يمكن في بعض الأحيان التوصل إلى قياسات دقيقة(وليست مقاربة) للكفاءة ولكن ذلك يتطلب عادة بعض الافتراضات المتعلقة بتنفيذ معين للخوارزمية وهو ما يسمى بنموذج التحسيب. ويمكن تعريف نموذج التحسيب من خلال حاسوب مجرد، كآلة تورنگ، أو/و افتراض تنفيذ بعض العمليات في وحدة زمنية ما. فعلى سبيل المثال ، إذا احتوت القائمة الخاضعة للبحث الثنائي على 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 3 7463-3102-X
