تحليل الخوارزميات

في علم الحاسوب ، يُعرَّف تحليل الخوارزميات بأنه عملية تحديد التعقيد الحسابي للخوارزميات ، أي مقدار الوقت أو مساحة التخزين أو الموارد الأخرى اللازمة لتنفيذها. يتضمن ذلك عادةً تحديد دالة تربط حجم مُدخلات الخوارزمية بعدد خطواتها ( تعقيدها الزمني ) أو عدد مواقع التخزين التي تستخدمها ( تعقيدها المكاني ). تُوصف الخوارزمية بأنها فعّالة عندما تكون قيم هذه الدالة صغيرة، أو عندما ينمو حجمها ببطء مقارنةً بنمو حجم المُدخلات. قد تؤدي مُدخلات مختلفة من نفس الحجم إلى سلوك مختلف للخوارزمية، لذا فإن وصف أفضل وأسوأ ومتوسط الحالات قد يكون ذا أهمية عملية. عندما لا يُنص على خلاف ذلك، فإن الدالة التي تصف أداء الخوارزمية عادةً ما تكون حدًا أعلى ، يُحدد بناءً على أسوأ مُدخلات الخوارزمية.

صاغ دونالد كنوث مصطلح "تحليل الخوارزميات" . ^{[ 1 ]} يُعد تحليل الخوارزميات جزءًا مهمًا من نظرية التعقيد الحسابي الأوسع نطاقًا ، والتي تُقدّم تقديرات نظرية للموارد اللازمة لأي خوارزمية لحل مشكلة حسابية مُحددة . تُتيح هذه التقديرات فهمًا أفضل للاتجاهات المنطقية للبحث عن خوارزميات فعّالة .

في التحليل النظري للخوارزميات، من الشائع تقدير تعقيدها بالمعنى التقاربي، أي تقدير دالة التعقيد لمدخلات كبيرة كيفما كانت. تُستخدم رموز Big O و Big-omega و Big-theta لهذا الغرض. ^{[ 2 ]} على سبيل المثال، يُقال إن البحث الثنائي يعمل في عدد من الخطوات يتناسب مع لوغاريتم حجم $n$ للقائمة المرتبة التي يتم البحث فيها، أو في $O (log n)$ ، أو بعبارة أخرى "في زمن لوغاريتمي ". عادةً ما تُستخدم التقديرات التقاربية لأن التطبيقات المختلفة لنفس الخوارزمية قد تختلف في كفاءتها. ومع ذلك، فإن كفاءة أي تطبيقين "معقولين" لخوارزمية معينة ترتبط بعامل ضرب ثابت يُسمى ثابتًا خفيًا .

يمكن أحيانًا حساب مقاييس دقيقة (وليست تقريبية) للكفاءة، لكنها عادةً ما تتطلب افتراضات معينة تتعلق بالتنفيذ المحدد للخوارزمية، والتي تُسمى نموذج الحساب . يُمكن تعريف نموذج الحساب باستخدام حاسوب مجرد ، مثل آلة تورينج ، أو بافتراض أن عمليات معينة تُنفذ في وحدة زمنية واحدة. على سبيل المثال، إذا كانت القائمة المرتبة التي نطبق عليها البحث الثنائي تحتوي على $n$ عنصرًا، ويمكننا ضمان إمكانية البحث عن كل عنصر في القائمة في وحدة زمنية واحدة، فإننا نحتاج على الأكثر إلى $log₂$ $( n) + 1$ وحدة زمنية لإرجاع الإجابة.

نماذج التكلفة

تعتمد تقديرات كفاءة الوقت على تعريفنا للخطوة. ولكي يتوافق التحليل مع وقت التشغيل الفعلي، يجب ضمان أن يكون الوقت اللازم لتنفيذ خطوة ما محدودًا بقيمة ثابتة. يجب توخي الحذر هنا؛ فمثلاً، تحسب بعض التحليلات جمع عددين كخطوة واحدة. قد لا يكون هذا الافتراض مناسبًا في بعض السياقات. على سبيل المثال، إذا كانت الأعداد المستخدمة في عملية حسابية كبيرة جدًا، فلا يمكن افتراض ثبات الوقت اللازم لعملية جمع واحدة.

يتم استخدام نموذجين للتكلفة بشكل عام: ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}^{[ 6 ]}^{[ 7 ]}

يُخصص نموذج التكلفة الموحدة ، والذي يُسمى أيضًا نموذج تكلفة الوحدة (وما شابهه من نماذج)، تكلفة ثابتة لكل عملية تشغيلية للآلة، بغض النظر عن حجم الأرقام المعنية.
يُحدد نموذج التكلفة اللوغاريتمية ، والذي يُسمى أيضًا قياس التكلفة اللوغاريتمية (وما شابهه من اختلافات)، تكلفة لكل عملية تشغيلية على الآلة تتناسب مع عدد البتات المستخدمة.

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

من النقاط الأساسية التي غالباً ما يتم تجاهلها أن الحدود الدنيا المنشورة للمسائل غالباً ما تُعطى لنموذج حسابي أكثر تقييداً من مجموعة العمليات التي يمكن استخدامها عملياً، وبالتالي توجد خوارزميات أسرع مما قد يُعتقد ببساطة أنه ممكن. ^{[ 8 ]}

تحليل وقت التشغيل

يُعد تحليل وقت التشغيل تصنيفًا نظريًا يُقدّر ويتنبأ بزيادة وقت تشغيل الخوارزمية مع ازدياد حجم مُدخلاتها (يُرمز له عادةً بـ $n$ ). تُعتبر كفاءة وقت التشغيل موضوعًا بالغ الأهمية في علوم الحاسوب ، إذ قد يستغرق البرنامج ثوانٍ أو ساعات أو حتى سنوات لإتمام تنفيذه، وذلك بحسب الخوارزمية المُستخدمة. ورغم إمكانية استخدام تقنيات تحليل أداء البرمجيات لقياس وقت تشغيل الخوارزمية عمليًا، إلا أنها لا تُوفّر بيانات التوقيت لجميع المُدخلات المُحتملة التي لا حصر لها؛ إذ لا يُمكن تحقيق ذلك إلا من خلال الأساليب النظرية لتحليل وقت التشغيل.

أوجه القصور في المقاييس التجريبية

بما أن الخوارزميات مستقلة عن المنصة (أي يمكن تنفيذ خوارزمية معينة بلغة برمجة عشوائية على جهاز كمبيوتر عشوائي يعمل بنظام تشغيل عشوائي )، فهناك عيوب إضافية كبيرة لاستخدام نهج تجريبي لتقييم الأداء المقارن لمجموعة معينة من الخوارزميات.

لنأخذ مثالاً على برنامج يبحث عن عنصر محدد في قائمة مرتبة بحجم n . لنفترض أن هذا البرنامج نُفِّذ على الحاسوب A، وهو جهاز متطور، باستخدام خوارزمية بحث خطي ، وعلى الحاسوب B، وهو جهاز أبطأ بكثير، باستخدام خوارزمية بحث ثنائي . قد يبدو اختبار الأداء على الحاسوبين اللذين يُشغِّلان برنامجيهما كما يلي:

ن (حجم القائمة)	وقت تشغيل الحاسوب أ ( بالنانو ثانية )	وقت تشغيل الكمبيوتر B ( بالنانو ثانية )
16	8	100,000
63	32	150,000
250	125	200,000
1000	500	250,000

بناءً على هذه المقاييس، قد يتبادر إلى الذهن بسهولة أن الحاسوب (أ) يُشغّل خوارزميةً تتفوق في كفاءتها على خوارزمية الحاسوب (ب) . مع ذلك، إذا زاد حجم قائمة المدخلات إلى عدد كافٍ، يتضح بشكل قاطع خطأ هذا الاستنتاج.

ن (حجم القائمة)	وقت تشغيل الحاسوب أ ( بالنانو ثانية )	وقت تشغيل الكمبيوتر B ( بالنانو ثانية )
16	8	100,000
63	32	150,000
250	125	200,000
1000	500	250,000
...	...	...
مليون	500,000	500,000
4,000,000	2,000,000	550,000
16,000,000	8,000,000	600,000
...	...	...
63,072 × 10 ¹²	31,536 × 10 ¹² نانوثانية، أو سنة واحدة	1,375,000 نانوثانية، أو 1.375 مللي ثانية

يُظهر الحاسوب (أ)، الذي يُشغّل برنامج البحث الخطي، معدل نمو خطي . يتناسب زمن تشغيل البرنامج طرديًا مع حجم مُدخلاته. فمضاعفة حجم المُدخلات تُضاعف زمن التشغيل، ومضاعفته أربع مرات تُضاعفه أربع مرات، وهكذا. من ناحية أخرى، يُظهر الحاسوب (ب)، الذي يُشغّل برنامج البحث الثنائي، معدل نمو لوغاريتمي . فمضاعفة حجم المُدخلات أربع مرات لا تُزيد زمن التشغيل إلا بمقدار ثابت (في هذا المثال، 50,000 نانوثانية). على الرغم من أن الحاسوب (أ) يبدو ظاهريًا أسرع، إلا أن الحاسوب (ب) سيتفوق عليه حتمًا في زمن التشغيل لأنه يُشغّل خوارزمية ذات معدل نمو أبطأ بكثير.

ترتيبات النمو

بصورة غير رسمية، يمكن القول إن خوارزمية ما تُظهر معدل نمو من رتبة دالة رياضية إذا كانت الدالة $f$ $($ $n$ $)$ مضروبة في ثابت موجب، بعد حجم إدخال معين $n$ ، تُشكّل حدًا أعلى أو أقصى لوقت تشغيل تلك الخوارزمية. بعبارة أخرى، بالنسبة لحجم إدخال مُعطى $n$ أكبر من $n₀$ وثابت _c $،$ فإن وقت تشغيل تلك الخوارزمية لن يتجاوز أبدًا $c$ $\times$ $f$ $($ $n$ $)$ . يُعبّر عن هذا المفهوم غالبًا باستخدام ترميز Big O. على سبيل المثال، بما أن وقت تشغيل فرز الإدراج ينمو تربيعيًا مع زيادة حجم الإدخال ، يُمكن القول إن فرز الإدراج من رتبة $O$ $($ $n²$ $)$ $.$

يُعد ترميز Big O طريقة ملائمة للتعبير عن أسوأ سيناريو لخوارزمية معينة، على الرغم من أنه يمكن استخدامه أيضًا للتعبير عن الحالة المتوسطة - على سبيل المثال، أسوأ سيناريو لـ quicksort هو $O (n 2)$ ، لكن وقت التشغيل في الحالة المتوسطة هو $O (n log n)$ .

أنماط النمو التجريبية

$بافتراض أن$ زمن التشغيل يتبع قاعدة القوة، $t \approx kn a$ ، يمكن إيجاد المعامل $a$ ^{[ 9 ]} بأخذ قياسات تجريبية لزمن التشغيل $t1$ و $t2$ عند نقاط معينة لحجم المشكلة $n1$ و $n2$ $،$ وحل المعادلة $t2 / t1 = ($ $n2$ $/$ $n1$ $)$ $a$ بالنسبة إلى $a$ $،$ أي $a = log(t2$ $/$ $t1$ $)$ $/log($ $n2$ $/$ $n1$ $) . بعبارة$ $أخرى$ $،$ يقيس هذا ميل الخط التجريبي على الرسم $البياني$ اللوغاريتمي المزدوج $لزمن$ التشغيل مقابل حجم المدخلات، عند $نقطة$ $حجم$ $معينة$ $.$ إذا كان ترتيب النمو يتبع قاعدة القوة (وبالتالي يكون الخط على الرسم البياني اللوغاريتمي خطًا مستقيمًا)، فإن القيمة التجريبية لـ $a$ ستظل ثابتة في نطاقات مختلفة، وإذا لم يكن الأمر كذلك، فإنها ستتغير (ويصبح الخط منحنيًا) - ولكن لا يزال من الممكن استخدامها لمقارنة أي خوارزميتين معينتين من حيث ترتيبات النمو المحلية التجريبية الخاصة بهما . ينطبق هذا على الجدول أعلاه:

ن (حجم القائمة)	وقت تشغيل الحاسوب أ ( بالنانو ثانية )	الترتيب المحلي للنمو (ن^_)	وقت تشغيل الكمبيوتر B ( بالنانو ثانية )	الترتيب المحلي للنمو (ن^_)
15	7		100,000
65	32	1.04	150,000	0.28
250	125	1.01	200,000	0.21
1000	500	1.00	250,000	0.16
...	...		...
مليون	500,000	1.00	500,000	0.10
4,000,000	2,000,000	1.00	550,000	0.07
16,000,000	8,000,000	1.00	600,000	0.06
...	...		...

يتضح جلياً أن الخوارزمية الأولى تُظهر نمواً خطياً يتبع قاعدة القوة. أما القيم التجريبية للخوارزمية الثانية فتتناقص بسرعة، مما يشير إلى أنها تتبع قاعدة نمو مختلفة، وعلى أي حال، فإن معدلات نموها المحلية أقل بكثير (وتتحسن باستمرار) تجريبياً من الخوارزمية الأولى.

تقييم تعقيد وقت التشغيل

يمكن أحيانًا تقييم تعقيد وقت التشغيل لأسوأ سيناريو لخوارزمية معينة من خلال فحص بنية الخوارزمية ووضع بعض الافتراضات المبسطة. انظر إلى الشفرة الزائفة التالية :

1. احصل على عدد صحيح موجب n من المدخل 2 إذا كان n > 10 3 اطبع "قد يستغرق هذا بعض الوقت..." 4 من أجل i = 1 إلى n 5 لـ j = 1 إلى i 6 اطبع i * j 7 اطبع "تم!"

سيستغرق جهاز كمبيوتر معين فترة زمنية محددة لتنفيذ كل تعليمة من التعليمات اللازمة لتنفيذ هذه الخوارزمية. لنفترض أن الإجراءات المنفذة في الخطوة 1 تستغرق وقتًا لا يتجاوز T1 _، والخطوة 2 تستغرق وقتًا لا يتجاوز T2 _، وهكذا.

في الخوارزمية المذكورة أعلاه، تُنفَّذ الخطوات 1 و2 و7 مرة واحدة فقط. ولتقييم أسوأ الحالات، يُفترض أن تُنفَّذ الخطوة 3 أيضًا. وبالتالي، فإن إجمالي الوقت اللازم لتنفيذ الخطوات من 1 إلى 3 والخطوة 7 هو:

T_{1}+T_{2}+T_{3}+T_{7}.\,

تُعدّ الحلقات في الخطوات 4 و5 و6 أكثر تعقيدًا في التقييم. سيُنفّذ اختبار الحلقة الخارجية في الخطوة 4 عدد ( _n+ 1) من المرات، ^{[ 10 ]} مما سيستغرق زمنًا قدره T4 ( n + 1). أما الحلقة الداخلية، فتُحدّد قيمتها بواسطة المتغير j، الذي يتكرر من 1 إلى i . في المرور الأول عبر الحلقة الخارجية، يتكرر j من 1 إلى 1: تُنفّذ الحلقة الداخلية دورة واحدة، لذا فإن تشغيل جسم الحلقة الداخلية (الخطوة 6) يستهلك زمنًا _قدرهT6 ، ويستهلك اختبار الحلقة الداخلية (الخطوة 5) زمنًا _قدره2T5 . خلال المرور التالي عبر الحلقة الخارجية، يتكرر j من 1 إلى 2: تُنفّذ الحلقة الداخلية دورتين، لذا فإن تشغيل جسم الحلقة الداخلية (الخطوة 6) يستهلك زمنًا _{قدره 2T6}، ويستهلك اختبار الحلقة الداخلية (الخطوة 5) زمنًا _قدره3T5 .

إجمالاً، يمكن التعبير عن إجمالي الوقت اللازم لتشغيل جسم الحلقة الداخلية كمتتابعة حسابية :

T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}

والتي يمكن تحليلها ^{[ 11 ]} على النحو التالي

\left[1+2+3+\cdots +(n-1)+n\right]T_{6}=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}

يمكن تقييم إجمالي الوقت اللازم لتشغيل اختبار الحلقة الداخلية بطريقة مماثلة:

{\begin{aligned}&2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}\\={}&T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}\end{aligned}}

والتي يمكن اعتبارها على النحو التالي

{\begin{aligned}&T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}\\={}&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}\\={}&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+nT_{5}\\={}&\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}\end{aligned}}

وبالتالي، فإن إجمالي وقت تشغيل هذه الخوارزمية هو:

f(n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}

والذي يختزل إلى

f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}

كقاعدة عامة ، يمكن افتراض أن الحد الأعلى رتبة في أي دالة معينة يهيمن على معدل نموها، وبالتالي يحدد رتبة زمن تشغيلها. في هذا المثال، الحد الأعلى رتبة هو n²، لذا يمكن استنتاج أن ^f $(n) = O (n²)$ . ويمكن إثبات ذلك رسميًا كما يلي $:$

أثبت ذلك $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$
${\begin{aligned}&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\\\leq {}&(n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ ({\text{for }}n\geq 0)\end{aligned}}$
ليكن k ثابتًا أكبر من أو يساوي [ T1 _..T7 _] ${\begin{aligned}&T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k\\={}&2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\ ({\text{for }}n\geq 1)=12kn^{2}\end{aligned}}$ لذلك $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$

يتمثل النهج الأكثر أناقة لتحليل هذه الخوارزمية في اعتبار أن [ T1 _..T7 ] جميعها تساوي وحدة زمنية واحدة، ضمن نظام وحدات مُختار بحيث تكون الوحدة الواحدة أكبر من أو تساوي الأزمنة الفعلية لهذه الخطوات. وهذا يعني أن زمن تشغيل الخوارزمية يتوزع على النحو التالي _:^{[ 12 ]}

$4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\ ({\text{for }}n\geq 1)=O(n^{2}).$

تحليل معدل نمو الموارد الأخرى

يمكن أيضًا استخدام منهجية تحليل وقت التشغيل للتنبؤ بمعدلات نمو أخرى، مثل استهلاك مساحة الذاكرة . على سبيل المثال، انظر إلى الشفرة الزائفة التالية التي تُدير وتُعيد تخصيص استخدام الذاكرة بواسطة برنامج بناءً على حجم الملف الذي يُديره هذا البرنامج:

بينما لا يزال الملف مفتوحًا: ليكن n = حجم الملف، لكل زيادة قدرها 100,000 كيلوبايت في حجم الملف، ضاعف مقدار الذاكرة المحجوزة

في هذه الحالة، مع ازدياد حجم الملف n، سيتم استهلاك الذاكرة بمعدل نمو أُسّي ، وهو من رتبة $O (2^n)$ . يُعدّ هذا معدل نمو سريعًا للغاية، ومن المرجح أن يكون من الصعب إدارته، فيما يتعلق باستهلاك موارد الذاكرة .

الأهمية

يُعدّ تحليل الخوارزميات بالغ الأهمية عمليًا، إذ يُمكن أن يُؤثّر استخدام خوارزمية غير فعّالة، سواءً عن طريق الخطأ أو دون قصد، تأثيرًا كبيرًا على أداء النظام. ففي التطبيقات الحساسة للوقت، قد تُصبح نتائج الخوارزمية التي تستغرق وقتًا طويلًا جدًا قديمة أو عديمة الفائدة. كما قد تتطلّب الخوارزمية غير الفعّالة قدرًا هائلًا من قوة الحوسبة أو مساحة التخزين لتشغيلها، ما يجعلها عديمة الجدوى عمليًا.

العوامل الثابتة

يركز تحليل الخوارزميات عادةً على الأداء التقاربي، لا سيما على المستوى الأساسي، ولكن في التطبيقات العملية، تُعدّ العوامل الثابتة مهمة، وتكون البيانات في العالم الحقيقي محدودة الحجم دائمًا. عادةً ما يكون هذا الحد هو حجم الذاكرة القابلة للعنونة، لذا في الأجهزة ذات 32 بت، يكون 2^ ³² = 4 جيجابايت (أكبر في حالة استخدام الذاكرة المجزأة )، وفي الأجهزة ذات 64 بت، يكون 2 ^{^64} = 16 إكسابايت. بالتالي، مع حجم محدود، يمكن استبدال رتبة النمو (الزمني أو المكاني) بعامل ثابت، وبهذا المعنى، تكون جميع الخوارزميات العملية من رتبة $O (1)$ لثابت كبير بما فيه الكفاية، أو لبيانات صغيرة بما فيه الكفاية.

يُعدّ هذا التفسير مفيدًا بشكل أساسي للدوال التي تنمو ببطء شديد: فاللوغاريتم المتكرر (log ^* ) (ثنائي) أقل من 5 لجميع البيانات العملية (2^ ⁶⁵⁵³⁶ بت)؛ واللوغاريتم الثنائي (log log n ) أقل من 6 لجميع البيانات العملية تقريبًا (2 ^{^64} بت)؛ واللوغاريتم الثنائي (log n ) أقل من 64 لجميع البيانات العملية تقريبًا (2 ^{^64} بت). ومع ذلك، قد تكون الخوارزمية ذات التعقيد غير الثابت أكثر كفاءة من الخوارزمية ذات التعقيد الثابت على البيانات العملية إذا نتج عن العبء الإضافي للخوارزمية ذات الوقت الثابت عامل ثابت أكبر، على سبيل المثال، قد يكون لدى المرء $K>k\log \log n$ طالما $K/k>6$ و $n<2^{2^{6}}=2^{64}$ .

بالنسبة للبيانات الكبيرة، لا يمكن تجاهل العوامل الخطية أو التربيعية، ولكن بالنسبة للبيانات الصغيرة، قد تكون الخوارزمية غير الفعالة تقاربياً أكثر كفاءة. يُستخدم هذا بشكل خاص في الخوارزميات الهجينة ، مثل Timsort ، التي تستخدم خوارزمية فعالة تقاربياً (هنا فرز الدمج ، مع تعقيد زمني). $n\log n$ )، ولكن التحول إلى خوارزمية غير فعالة تقاربياً (هنا فرز الإدراج ، مع تعقيد زمني $n^{2}$ ) بالنسبة للبيانات الصغيرة، لأن الخوارزمية الأبسط تكون أسرع على البيانات الصغيرة.

انظر أيضاً

التحليل المستهلك
تحليل الخوارزميات المتوازية
التعقيد الحسابي التقاربي
التعقيد القائم على المعلومات
نظرية ماستر (تحليل الخوارزميات)
NP-complete
التحليل العددي
الوقت متعدد الحدود
تحسين البرنامج
قابلية التوسع
تحليل مُنعّم
تحليل الإنهاء - المشكلة الفرعية المتمثلة في التحقق مما إذا كان البرنامج سينتهي على الإطلاق

ملحوظات

↑ "كنوث: آخر الأخبار" . 28 أغسطس 2016. مؤرشف من الأصل في 28 أغسطس 2016.
↑ كورمن، توماس هـ.، محرر. (2009). مقدمة في الخوارزميات ( الطبعة الثالثة). كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. الصفحات 44-52 . ISBN 978-0-262-03384-8. OCLC 311310321 .
↑ ألفريد ف. أهو؛ جون إي. هوبكروفت؛ جيفري د. أولمان (1974). تصميم وتحليل خوارزميات الحاسوب . شركة أديسون-ويسلي للنشر. ISBN 9780201000290.القسم 1.3
↑ يوراي هرومكوفيتش (2004). علم الحاسوب النظري: مقدمة في الأوتوماتا، والحوسبة، والتعقيد، والخوارزميات، والعشوائية، والاتصالات، والتشفير . سبرينغر. ص 177-178 . ISBN 978-3-540-14015-3.
↑ جورجيو أوسييلو (1999). التعقيد والتقريب: مسائل التحسين التوافقي وخصائص قابليتها للتقريب . سبرينغر. ص 3-8 . ISBN 978-3-540-65431-5.
↑ فيجنر، إنجو (2005)، نظرية التعقيد: استكشاف حدود الخوارزميات الفعالة ، برلين، نيويورك: سبرينغر-فيرلاغ ، ص 20، ISBN 978-3-540-21045-0
↑ روبرت إندري تارجان (1983). هياكل البيانات وخوارزميات الشبكات . SIAM. ص 3-7 . ISBN 978-0-89871-187-5.
↑ أمثلة على ثمن التجريد؟، cstheory.stackexchange.com
↑ كيفية تجنب إساءة استخدام O والرشاوى ( مؤرشف بتاريخ 8 مارس 2017 في Wayback Machine ، في مدونة "رسالة غودل المفقودة وP=NP" بقلم آر جيه ليبتون، أستاذ علوم الحاسوب في معهد جورجيا للتكنولوجيا، يروي فكرة روبرت سيدجويك)
↑ يلزم خطوة إضافية لإنهاء حلقة for، وبالتالي يتم تنفيذ n + 1 وليس n عملية تنفيذ.
↑ يمكن إثباتذلك بالاستقراء $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$
↑ هذا الأسلوب، على عكس الأسلوب السابق، يتجاهل الوقت الثابت الذي تستغرقه اختبارات الحلقة التي تُنهي حلقاتها الخاصة، ولكن من السهل إثبات أن هذا الإغفال لا يؤثر على النتيجة النهائية.

مراجع

سيدجويك، روبرت ؛ فلاجويه، فيليب (2013). مقدمة في تحليل الخوارزميات ( الطبعة الثانية). أديسون-ويسلي. ISBN 978-0-321-90575-8.
غرين، دانيال أ.؛ كنوت، دونالد إي. (1982). الرياضيات لتحليل الخوارزميات ( الطبعة الثانية). بيركهاوزر. ISBN 3-7643-3102-X.
كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل.؛ وستين ، كليفورد (2001). مقدمة في الخوارزميات . الفصل 1: الأسس ( الطبعة الثانية). كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 3-122 . ISBN 0-262-03293-7.
سيدجويك، روبرت (1998). الخوارزميات في لغة سي، الأجزاء 1-4: الأساسيات، هياكل البيانات، الفرز، البحث (الطبعة الثالثة ). ريدينغ، ماساتشوستس: أديسون-ويسلي بروفيشنال. ISBN 978-0-201-31452-6.
كنوت، دونالد . فن برمجة الحاسوب . أديسون-ويسلي.
جولدرايش، أوديد (2010). التعقيد الحسابي: منظور مفاهيمي . مطبعة جامعة كامبريدج . ISBN 978-0-521-88473-0.

روابط خارجية

الوسائط المتعلقة بتحليل الخوارزميات في ويكيميديا كومنز

[1] "كنوث: آخر الأخبار" . 28 أغسطس 2016. مؤرشف من الأصل في 28 أغسطس 2016.

[2] كورمن، توماس هـ.، محرر. (2009). مقدمة في الخوارزميات ( الطبعة الثالثة). كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. الصفحات 44-52 . ISBN 978-0-262-03384-8. OCLC 311310321 .

[AhoHopcroft1974-3] ألفريد ف. أهو؛ جون إي. هوبكروفت؛ جيفري د. أولمان (1974). تصميم وتحليل خوارزميات الحاسوب . شركة أديسون-ويسلي للنشر. ISBN 9780201000290.القسم 1.3

[Hromkovič2004-4] يوراي هرومكوفيتش (2004). علم الحاسوب النظري: مقدمة في الأوتوماتا، والحوسبة، والتعقيد، والخوارزميات، والعشوائية، والاتصالات، والتشفير . سبرينغر. ص 177-178 . ISBN 978-3-540-14015-3.

[Ausiello1999-5] جورجيو أوسييلو (1999). التعقيد والتقريب: مسائل التحسين التوافقي وخصائص قابليتها للتقريب . سبرينغر. ص 3-8 . ISBN 978-3-540-65431-5.

[Wegener20-6] فيجنر، إنجو (2005)، نظرية التعقيد: استكشاف حدود الخوارزميات الفعالة ، برلين، نيويورك: سبرينغر-فيرلاغ ، ص 20، ISBN 978-3-540-21045-0

[Tarjan1983-7] روبرت إندري تارجان (1983). هياكل البيانات وخوارزميات الشبكات . SIAM. ص 3-7 . ISBN 978-0-89871-187-5.

[8] أمثلة على ثمن التجريد؟، cstheory.stackexchange.com

[9] كيفية تجنب إساءة استخدام O والرشاوى ( مؤرشف بتاريخ 8 مارس 2017 في Wayback Machine ، في مدونة "رسالة غودل المفقودة وP=NP" بقلم آر جيه ليبتون، أستاذ علوم الحاسوب في معهد جورجيا للتكنولوجيا، يروي فكرة روبرت سيدجويك)

[10] يلزم خطوة إضافية لإنهاء حلقة for، وبالتالي يتم تنفيذ n + 1 وليس n عملية تنفيذ.

[11] يمكن إثباتذلك بالاستقراء $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$

[12] هذا الأسلوب، على عكس الأسلوب السابق، يتجاهل الوقت الثابت الذي تستغرقه اختبارات الحلقة التي تُنهي حلقاتها الخاصة، ولكن من السهل إثبات أن هذا الإغفال لا يؤثر على النتيجة النهائية.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]