أنواع وظائف التعقيد للخوارزميات. تقييم مدى تعقيد الخوارزميات، أو ما هو O(log n) مفهوم الخوارزميات البسيطة والمعقدة

لمقارنة الخوارزميات، من المعتاد استخدام خاصية عامة تسمى الكفاءة. يقولون أن الخوارزمية L، أكثر فعاليةخوارزمية أ 2،إذا كانت الخوارزمية L، فسيتم تشغيلها في وقت أقل و (أو) تتطلب وقتًا أقل موارد الكمبيوتر (ذاكرة الوصول العشوائي، مساحة القرص، حركة مرور الشبكة، وما إلى ذلك).

يجب أن تفي الخوارزمية الفعالة بمتطلبات وقت التنفيذ المقبول والاستهلاك المعقول للموارد، كما هو مذكور بالفعل في الفقرة 1.1. يشكل الجمع بين هذه الخصائص مفهوم تعقيد الخوارزمية. ومع زيادة وقت تنفيذ الخوارزمية و/أو الموارد المعنية، يزداد التعقيد. وبالتالي، فإن مفهومي الكفاءة والتعقيد يتعارضان مع بعضهما البعض.

تسمى خاصية الخوارزمية التي تعكس الوقت المستغرق في تنفيذها تعقيد الوقت.تسمى خاصية الخوارزمية التي تعكس تكاليف موارد الكمبيوتر لتنفيذها التعقيد بالسعة.

في التقييمات الكمية والنوعية للخوارزمية المتعلقة بتحديد التعقيد، يتم استخدام نهجين - عملي ونظري.

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

التقييم العملي ليس مؤشرا مطلقا لفعالية الخوارزمية. وتعتمد القيم الكمية التي يتم الحصول عليها من هذا النهج على عوامل كثيرة، مثل:

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

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

التعقيد النظرييميز الخوارزمية دون الرجوع إلى معدات محددة، برمجةووسائل التنفيذ . في هذه الحالة، يتم التعبير عن التعقيد الزمني في عدد العمليات ودورات تشغيل آلة تورينج وما إلى ذلك. يتم تحديد التعقيد السعوي من خلال حجم البيانات (الإدخال، الوسيط، الإخراج)، وعدد الخلايا المعنية على شريط آلة Thjoring، وما إلى ذلك.

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

قد تعتمد التقديرات الكمية التي يتم الحصول عليها باستخدام النهج النظري أيضًا على عدد من العوامل التالية:

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

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

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

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

بشكل عام، تي (ع)هي بعض الوظائف لكمية البيانات المدخلة ص.في كثير من الحالات تي (ع)يتم التعبير عنها كدالة متعددة الحدود أو قوة أو لوغاريتمية ص.

سلوك الكمية تي (ع)اعتمادا على التكبير صمُسَمًّى التعقيد المقاربخوارزمية. ويقولون ان ت(ص) لقد ترتيب التعقيد 0(J(n))(يقرأ "عنكبيرة من/من ف")لبعض الخوارزمية، إذا كان هناك ثابت معوحجم البيانات شمثل ذلك أعلى > ن 0وهناك عدم مساواة ت(ص) ق/(ن).

هذه الحقيقة مكتوبة كما تي(ن) = 0(ي(ن))ويعني أن لهذه الوظيفة تي (ع)هناك مثل هذه الوظيفة و (ن)وثابت ج، الذي يبدأ من بعض ن 0,معنى تي (ع)لا يتجاوز راجع (ن).

وظيفة و (ن)يمثل الحد الأعلى لقيم الدالة تي (ن).دعونا، على سبيل المثال، ت(ن) = 2ص أ + ن 2.اختيار القيم ن 0= 0 و ج = 5، لأي شخص ن > ن 0لدينا ت(ن) = 2ص أ + ن 2 T(n) من الرتبة i 4.

وظيفة ت(ص) يرتبط بخوارزمية محددة، لذلك يُقال غالبًا أن ترتيب التعقيد 0(/(ن))لديه بالضبط الخوارزمية.

ويقولون ان تي (ع)لقد الحد الأدنى Q(g(n))(يقرأ "أوميغا كبيرة من ز from /g")، في حالة وجود الثابت c وكمية البيانات ن 0مثل ذلك / صوهناك عدم مساواة تي (ن) > الفريق الاستشاري (ن).

هذه الحقيقة مكتوبة كما تي(ن) = س(ز(ن)).دعونا، على سبيل المثال، ت(ن) =الثانية 4 + ن 2.اختيار القيمة ج = 1، لأي شخص صلدينا تي (ع)= الثاني 4 + ع2 > س أ >لذلك، ت(ص) لديه الحد الأدنى ط 4 .

من السهل أن نرى أن الترتيب والحد الأدنى ليسا فريدين لبعض الوظائف تي (ن).في الأمثلة أعلاه، يمكن للمرء أن يختار i 5 و i 6 و... كـ /(i) وكـ ز (ن) - i 3, i 2,.... عادة يتم اختيار الدالة ذات الدرجة الدنيا كـ /(i) و as ز (ن)- بالحد الأقصى.

يمثل ترتيب التعقيد 0(/(i)) والحد الأدنى Q(g(rc)) فئات الوظائف. بشكل بديهي، يمكن فهم Q(g"(n)) على أنها فئة من الوظائف تنمو بنفس سرعة نموها على الأقل تي (ن).وبالمثل، بشكل حدسي 0(و(ن))يمكن فهمها على أنها فئة من الوظائف التي لا تنمو بشكل أسرع من تي (ن). معمن الناحية العملية، عند تقييم مدى تعقيد الخوارزمية، فإن الشيء الأكثر أهمية هو فئة الوظائف 0(و(ن)).تحديد نوع الدالة /(i) هو المهمة الرئيسية للحسابالتعقيد النظري للخوارزمية.

بالنسبة لأي خوارزمية، عند تحديد درجة النمو، يمكنك استخدام الخصائص التالية لـ 0(/(i)):

1) 0(كف(جي))= 0(/(ط))، حيث ك= ثابت. وبالتالي فإن المضاعف الثابت في الدالة لا يؤثر على معدل النمو. على سبيل المثال،

2) 0(J(ري)"g(n)) = 0(J(n))"0(g(ri)).وبالتالي فإن ترتيب حاصل ضرب وظيفتين يساوي حاصل ضرب تعقيداتهما. على سبيل المثال،

في بعض الأحيان يتم كتابة هذه الخاصية كـ

3) 0(/(ع) + ز (ن))يساوي مسيطر(وظائف بأقصى درجة) وظائف /(ط) و ز (ن).على سبيل المثال،

في نظرية تعقيد الخوارزميات، يتم التمييز بين الفئات التالية من وظائف التعقيد:

• 1) التعقيد المستمر 0(1). لا يعتمد وقت تشغيل الخوارزمية والموارد المستخدمة على كمية بيانات الإدخال. عادةً ما تكون الخوارزميات التي لا تحتوي على حلقات واستدعاءات متكررة بهذا التعقيد؛
• 2) التعقيد الخطي 0(ن).عادة، يتم العثور على هذا التعقيد في المهام التي يجب فيها معالجة كل عنصر من عناصر بيانات الإدخال لعدد معين من المرات، وهو ما لا يرتبط بأي حال من الأحوال بعدد معالجة العناصر الأخرى؛
• 3) التعقيد اللوغاريتمي 0(سجل 2 ث)، 0(رقم 2 ن).يتم استخدام قواعد لوغاريتمية أخرى في بعض الأحيان؛
• 4) تعقيد متعدد الحدود 0(i 2), 0(i 3), 0(i 4),...;
• 5) التعقيد الأسي 2 ص, 3",....

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

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

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

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

بمجرد اختيار العمليات الهامة، يتم تقسيمها إلى فئتين:

• 1) العمليات التي تؤثر بشكل مباشر على تعقيد الخوارزمية؛
• 2) العمليات التي تشكل "الحمل الزائد" عند تنفيذ الخوارزمية (على سبيل المثال، تخصيص الذاكرة لتخزين البيانات الوسيطة).

يتيح لك العد المباشر أو تقدير عدد العمليات التي تم تنفيذها إجراء التقدير تي (ن).

يمكن استخدام التحليل لتقدير ترتيب التعقيد كود البرنامجتنفيذ الخوارزمية. حيث:

• الخوارزميات التي لا تحتوي على حلقات ومكالمات متكررة لها درجة تعقيد من الترتيب 0(1). وبالتالي، فإن عمليات تخصيص وإدخال وإخراج البيانات، الشرطيةلديك تعقيد مستمر.
• إذا كان هناك صعوبات في جزأين من رمز البرنامج 0(ي((ري))و 0(ي 2 (ن))،ثم التنفيذ المتسلسل له تعقيد

• إذا تم تنفيذ نص الحلقة مرة واحدة لكل عنصر من عناصر البيانات المدخلة، فإن تعقيد تنفيذ الحلقة يكون من ترتيب 0(ن)0( 1) = 0(ن);
• يتم حساب ترتيب تعقيد تنفيذ الحلقات المتداخلة باستخدام قاعدة المنتج 0(ي س (ن)و 2 (ن)) = 0(/,(/?))- 0(ي2(ري)).إذا كان كل واحد منهم لديه تعقيد النظام 0(ن)،تنفيذ الحلقات المتداخلة له تعقيد بترتيب 0(ن 2).

مثال 1.3

تحديد ترتيب تعقيد خوارزمية البرنامج في اللغة

باسكال هو مبين في القائمة 1.2. يتم ترقيم خطوط البرنامج كتعليقات (انظر الفقرة 2.6).

القائمة 1.2

(01) لـ i:=l to n do

(02) البدء

(03) اكتب ("أدخل عنصر الصفيف

مع الفهرس ",i,": ");

(04) ريدلن(MyArray[i]);

(05)النهاية؛

(06) لـ i:=l to n do

(07) لـ j:=1 إلى n افعل

(08) البدء

(09) اكتب ("أدخل عنصر الصفيف

مع الفهارس "، i، "،، j، " : ")؛

(10) ريدلن (MyDArray)؛

(11) النهاية؛

حل

لا تحتوي الأسطر 02، 05، 08، 11 على بيانات قابلة للتنفيذ، لذلك لا يتم أخذها في الاعتبار عند تحديد الأمر.

السطران 03 و04 لهما الترتيب 0(1). تنفيذها المتسلسل له الترتيب 0(1) + 0(1) = 0(1). وبالمثل، فإن تنفيذ السطرين 09 و10 بالتسلسل له درجة تعقيد تبلغ 0(1).

الحلقة في السطور 01-05 لها تعقيد في الترتيب على)،حلقات متداخلة في السطور 06-11 - ترتيب 0(ن 2).التعقيد النهائي للخوارزمية هو من الترتيب

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

من الممكن في كثير من الأحيان التوصل إلى أكثر من خوارزمية لحل نفس المشكلة. وفي هذا الصدد، يطرح السؤال: أي من الخوارزميات "الأفضل"؟

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

العملية الحسابية للخوارزمية هي سلسلة من الخطوات التي يتم اتخاذها عند تنفيذ الخوارزمية لبعض بيانات الإدخال.

من المهم أن نفهم الفرق بين الخوارزمية نفسها والعملية الحسابية الناتجة عن تلك الخوارزمية. الأول هو فقط وصفثانية.

التعقيد الزمني للخوارزمية هو الوقت \(T\) المطلوب لإكمال العملية الحسابية للخوارزمية لبعض بيانات الإدخال.

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

ومع ذلك، يمكن التعبير عن الوقت \(T\) من خلال عدد الإجراءات الأولية \(k\) ومتوسط ​​الوقت اللازم لإكمال الإجراء الأولي \(t\):

علاوة على ذلك، \(k\) خاصية نفسهالخوارزمية، و\(t\) هي خاصية المؤدي.

نظرًا لحقيقة أن \(t\) يمكن اعتباره ثابتًا لمنفذ معين، عادةً ما يتم تقدير تعقيد الخوارزميات بعامل ثابت. وبعبارة أخرى، يتم تقدير مدى تعقيد الخوارزمية ترتيب النمو.

ترتيب النمو دالة موجبة محددة \(g(x)\) لها ترتيب النمو \(f(x)\) (مكتوبة \(g(x)=\mathcal(O)(f(x))\)) لو \(\يوجد c>0: \: \forall x>x_0, \, g(x) \leq c f(x)\).

اعتمادا على البيانات المدخلة، يمكن تشغيل الخوارزمية لأوقات مختلفة. عادة ما يتم تقييمها متوسطالتعقيد والتعقيد في أسوأ الأحوال. هناك أيضا الاعتماد على كمياتإدخال البيانات \(ن\) . عادةً ما يتم تقدير ترتيب النمو من \(n\).

لذلك، على سبيل المثال، قراءة البيانات وتخزينها في الذاكرة كمصفوفة سيكون لها تعقيد \(\mathcal(O)(n)\) ، أو التعقيد الخطي، وضرب المصفوفة موجود بالفعل مكعب\(\mathcal(O)(n^3)\) .

بالإضافة إلى التعقيد الزمني للخوارزمية، فقد تبين أنها مهمة أيضًا مكانيتعقيد الخوارزمية.

التعقيد المكاني للخوارزمية هو الرقم إضافيالذاكرة \(S\) التي تتطلبها الخوارزمية للعمل. الذاكرة \(D\) المطلوبة لتخزين بيانات الإدخال غير مضمنة في \(S\) .

\(S\) في الحالة العامة يعتمد أيضًا على المشغل. لنفترض أنه إذا كان هناك جهازان للتنفيذ يدعمان أعدادًا صحيحة بطول 4 و 8 بايت، على التوالي، فإن التعقيد المكاني للخوارزمية على أعداد صحيحة ذات 8 بايت سيكون ضعف حجم الأعداد الصحيحة ذات 4 بايت. ولذلك، يتم تقييم التعقيد المكاني أيضًا حسب ترتيب النمو.

فئات تعقيد الخوارزمية

تأكيد فئات الصعوبة: هذه هي الفئات التي لها نفس التعقيد.

يتم تمييز فئات الصعوبة الرئيسية التالية:

DTIME تقوم آلة تورينج بإيجاد حل لمشكلة ما في وقت محدد (عدد الخطوات). غالبًا ما يتم تحديد السلوك المقارب للخوارزمية، لذلك، على سبيل المثال، إذا كان ترتيب الزيادة في وقت التشغيل هو \(T(n) = \mathcal(O)(f(n))\) ثم قم بالإشارة إلى \(DTIME(f (ن))\) . P تقوم آلة تورينج بإيجاد حل للمشكلة في الزمن متعدد الحدود (عدد الخطوات)، أي. \(T(n) = \mathcal(O)(n^k)\) ، حيث \(k\in \mathbb(N)\) . \(P=DTIME(n^k)\) EXPTIME تجد آلة تورينج حلاً للمشكلة في زمن أسي (عدد الخطوات)، أي. \(T(n) = \mathcal(O)(2^(n^k))\)، حيث \(k\in \mathbb(N)\) . \(EXPTIME=DTIME(2^(n^k))\) . DSPACE آلة تورينج تجد حلاً لمشكلة باستخدام كمية محدودة من الذاكرة الإضافية (الخلايا). غالبًا ما يتم تحديد السلوك المقارب للخوارزمية، لذلك، على سبيل المثال، إذا كان ترتيب النمو في استهلاك الذاكرة هو \(S(n) = \mathcal(O)(f(n))\) ثم قم بالإشارة إلى \(DSPACE(f (ن))\) . L وجدت آلة تورينج حلاً لمشكلة التعقيد المكاني اللوغاريتمي، أي: \(S(n) = \mathcal(O)(\log n)\). \(L=DSPACE(\log n)\) . PSPACE وجدت آلة تورينج حلاً لمشكلة تتعلق بتعقيد الفضاء متعدد الحدود، أي \(S(n) = \mathcal(O)(n^k)\) ، حيث \(k\in \mathbb(N)\ ) . \(PSPACE=DSPACE(n^k)\) . EXPSPACE تجد آلة تورينج حلاً لمشكلة التعقيد المكاني الأسي، أي \(S(n) = \mathcal(O)(2^(n^k))\)، حيث \(k\in \mathbb(N)\) . \(EXPSPACE=DSPACE(2^(n^k))\) .

بالإضافة إلى ذلك، هناك فئات التعقيد النظرية التي تعمل على هذا المفهوم غير حتميةآلات تورينج (TMTs). تعريفاتهم هي نفسها المذكورة أعلاه، مع استبدال آلة تورينج بـ NMT، وأسمائهم مسبوقة بـ N (على سبيل المثال، NP)، باستثناء NTIME وNSPACE، حيث يتم استبدال D بـ N.

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

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

ومن المعروف أن \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)

بالإضافة إلى ذلك، \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)

ومن المعروف أيضًا أنه إذا كان \(P = NP\) ، فإن \(EXPTIME = NEXPTIME\) .

تعد مسألة المساواة بين P وNP إحدى القضايا الرئيسية التي لم يتم حلها في علوم الكمبيوتر الحديثة.

أمثلة على الخوارزميات

دعونا نعطي بعض الأمثلة على الخوارزميات البسيطة ونفكر في مدى تعقيدها.

رفع إلى السلطة الكاملة

تم وصف هذه الخوارزمية في الهند القديمة قبل عصرنا وتستخدم لحساب القوة الطبيعية \(n\) عدد حقيقي\(س\)

1. اكتب \(ن\) في النظام الثنائيحساب الميت
2. استبدل في هذا الإدخال كل حرف من الرقم 1 بزوج من الحروف KH، وكل 0 بالحرف K
3. قم بشطب الزوج الموجود في أقصى اليسار KX
4. قراءة السلسلة الناتجة من اليسار إلى اليمين، عند مواجهة الحرف K، قم بتربيع النتيجة، وعندما تواجه الحرف X، اضرب النتيجة في x. في البداية تكون النتيجة x.

في هذه الخوارزمية، لدينا عدد من عمليات الضرب يساوي عدد الأرقام في التمثيل الثنائي \(n\) في أفضل الحالات، و\(2(n-1)\) في أسوأ الحالات. على أية حال، تعقيد الوقت.

لا توجد عمليا أي ذاكرة إضافية مطلوبة في التنفيذ الفعال للخوارزمية، ولا تعتمد على البيانات المدخلة، وبالتالي فإن التعقيد المكاني هو \(S(n) = \mathcal(O)(1)\) .

تجدر الإشارة إلى أن هناك خوارزميات أكثر كفاءة. ومع ذلك، بالمقارنة مع التنفيذ "الساذج" الذي يتطلب \(\mathcal(O)(n)\) عمليات الضرب، فإن هذه الخوارزمية فعالة نسبيًا.

ضرب الأعداد الصحيحة

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

يُضرب العامل الأول في اثنين بالتتابع، ويُقسم العامل الثاني على 2. وتكتب النتائج في عمودين حتى يتم الحصول على 1 في الثاني.

نتيجة الضرب هي مجموع الأعداد في العمود الأول، ومقابلها الأعداد الفردية في العمود الثاني.

نظرًا لأنه يمكن تنفيذ قسمة الأعداد الصحيحة وضربها في 2 عن طريق الإزاحة، فإن هذه الخوارزمية تنتج عمليات إزاحة \(2 \log_2 n\)، حيث \(n\) هو الأصغر بين الرقمين. في أسوأ الحالات، نفس النتائج في عمليات الإضافة \(\log_2 n - 1\). على أية حال، تعقيد الوقت \(T(n) = \mathcal(O)(\log n)\).

من أجل التنفيذ الفعال للخوارزمية، لا توجد حاجة عمليًا إلى ذاكرة إضافية، ولا تعتمد على البيانات المدخلة، لذلك \(S(n) = \mathcal(O)(1)\)

مرة أخرى، تجدر الإشارة إلى أن هناك خوارزميات أكثر كفاءة. ومع ذلك، بالمقارنة مع التنفيذ "الساذج" الذي يتطلب عمليات إضافة \(\mathcal(O)(n)\)، فإن هذه الخوارزمية فعالة نسبيًا.

مثال

ضرب 23 في 43.

لنأخذ 23 كعامل ثاني.

النتيجة \(43+86+172+688 = 989\)

حصلنا على 10 عمليات وردية و4 عمليات إضافة. كمرجع، \(\log_2(23) \approx 4.52\) .

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

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

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

تعريفات

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

هناك مفاهيم التعقيد في الأسوأ, متوسطأو أفضل سيناريو. عادة، يتم تقدير التعقيد في أسوأ الحالات.

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

ترتيب التعقيد المتزايد للخوارزميات

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

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

أنواع التقديرات المقاربة

O - تقدير أسوأ الحالات

النظر في التعقيد و(ن) > 0، دالة بنفس الترتيب ز(ن) > 0حجم المدخل ن > 0.
لو و(ن) = يا(ز(ن))وهناك ثوابت ج> 0, ن 0 > 0، الذي - التي
0 < f(n) < c*g(n),
ل ن > ن 0.

الدالة g(n) في هذه الحالة هي تقدير دقيق مقارب للقيمة f(n). إذا كانت f(n) دالة لتعقيد الخوارزمية، فسيتم تعريف ترتيب التعقيد على أنه f(n) – O(g(n)).

يحدد هذا التعبير فئة من الوظائف التي لا تنمو بشكل أسرع من g(n) حتى عامل ثابت.

أمثلة على الوظائف المقاربة

Ω - تقدير لأفضل حالة

ومع ذلك، فإن التعريف مشابه لتقدير الحالة الأسوأ
و(ن) = Ω(ز(ن))، لو
0 < c*g(n) < f(n)

Ω(ز(ن))يحدد فئة من الوظائف التي لا تنمو بشكل أبطأ من الوظيفة ز (ن)حتى عامل ثابت.

Θ – تقدير للحالة المتوسطة

ومن الجدير بالذكر فقط أنه في هذه الحالة الوظيفة و (ن)في ن > ن 0في كل مكان بين ج 1 *ز(ن)و ج 2 *ز(ن)، حيث c هو عامل ثابت.
على سبيل المثال، متى و(ن) = ن 2 + ن; ز(ن) = ن 2.

معايير لتقييم مدى تعقيد الخوارزميات

معيار الوزن الموحد (UWC)يفترض أن كل خطوة من خطوات الخوارزمية يتم تنفيذها في وحدة زمنية واحدة، وخلية ذاكرة في وحدة حجم واحدة (حتى ثابت).
معيار الوزن اللوغاريتمي (LWC)يأخذ في الاعتبار حجم المعامل الذي تتم معالجته بواسطة عملية معينة والقيمة المخزنة في خلية الذاكرة.

صعوبة الوقت بالنسبة لـ DEXتحددها القيمة ل (المرجع)، أين يا ص- قيمة المعامل.
تعقيد السعة في LVKتحددها القيمة ل (م)، أين م– حجم خلية الذاكرة .

مثال على تقدير التعقيد عند حساب المضروب

من الضروري تحليل مدى تعقيد خوارزمية الحساب العاملي. للقيام بذلك، دعونا نكتب هذه المهمة في الكود الكاذب C:

الفراغ الرئيسي () ( نتيجة int = 1؛ int i؛ const n = ...؛ for (i = 2؛ i<= n; i++) result = result * n; }

تعقيد الوقت مع معيار الترجيح الموحد

يكفي أن تحدد ببساطة أن حجم الإدخال لمشكلة معينة هو ن.
عدد من الخطوات - (ن - 1).

وبالتالي فإن التعقيد الزمني تحت RVC يساوي على).

التعقيد الزمني مع معيار الترجيح اللوغاريتمي

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

لذلك، في هذه المهمة هناك ثلاث عمليات:

1) أنا<= n

في الخطوة i، اتضح سجل (ن).
منذ خطوات (ن-1)سيكون تعقيد هذه العملية (ن-1)*سجل(ن).

2) ط = ط + 1

في الخطوة i، اتضح سجل (ط).
.

3) النتيجة = النتيجة * ط

في الخطوة i، اتضح سجل ((i-1)!).
وهكذا يكون المبلغ .

إذا قمت بجمع كل القيم الناتجة وتجاهلت المصطلحات التي من الواضح أنها تنمو بشكل أبطأ مع الزيادة ن، نحصل على التعبير النهائي .

التعقيد السعوي مع معيار الوزن الموحد

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

التعقيد السعوي مع معيار الوزن اللوغاريتمي

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

الاستنتاجات

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

وظيفة الصعوبة 0(1). في خوارزميات التعقيد الثابت، يتم تنفيذ معظم العمليات في البرنامج مرة واحدة أو أكثر. أي خوارزمية تتطلب دائمًا (بغض النظر عن حجم البيانات) نفس القدر من الوقت لها تعقيد مستمر.

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

وظيفة التعقيد 0(ن 2)، 0(ن 3), 0(№) - دالة التعقيد متعددة الحدود: عدد العمليات يزداد مع المربع ن.في الحالة العامة، يمكن أن يكون O(A^)، اعتمادًا على مدى تعقيد المشكلة. تميز وظيفة التعقيد هذه دورة معقدة.

وظيفة الصعوبةيا (سجل 2 (A0)، 0(نسجل2(A0). هذا هو الوقت الذي تعمل فيه الخوارزميات التي تقسم مشكلة كبيرة إلى العديد من المشكلات الصغيرة، ثم بعد حلها، يتم دمج الحلول.

وظيفة التعقيد 0 (ه ن).غالبًا ما تنتج الخوارزميات ذات التعقيد الأسي عن نهج يسمى القوة الغاشمة.

وظيفة التعقيد 0(م) -عدد العمليات ينمو بما يتناسب مع المضروب ن.

يجب أن يكون المبرمج قادرًا على تحليل الخوارزميات وتحديد مدى تعقيدها. يمكن حساب التعقيد الزمني للخوارزمية بناءً على تحليل هياكل التحكم الخاصة بها.

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

على سبيل المثال، فكر في خوارزمية لمعالجة عناصر المصفوفة.

لـ /": = 1 إلى نابدأ

تعقيد هذه الخوارزمية عن(أ)، بما أن جسم الحلقة يتم تنفيذه مرة واحدة، فإن تعقيد جسم الحلقة هو 0(1). إذا كانت إحدى الحلقات متداخلة داخل حلقة أخرى وتعتمد كلتا الحلقتين على حجم المتغير نفسه، فإن البنية بأكملها تتميز بالتعقيد التربيعي.

ل /: = 1 ل نافعل من أجل ي: = 1 ل نابدأ

تعقيد هذا البرنامج 0(ن2).

مثال 1.دعونا نقدر مدى تعقيد البرنامج الذي يدخل مصفوفة من لوحة المفاتيح ويجد العنصر الأكبر فيها. تتكون الخوارزمية من الخطوات التالية:

• - إدخال مصفوفة (تحتاج إلى قراءة العناصر A)؛
• - ابحث عن العنصر الأكبر (تحتاج إلى إجراء مقارنة A - 1)؛
• - إخراج النتيجة (تحتاج إلى إخراج رقم أو سلسلة واحدة).

لنجمع عدد العمليات A + (A - 1) + 1 = 2A، أي. موجود

مثل هذا الثابت الذي لا يتجاوز عدد العمليات فيه CA. ولذلك، فإن تعقيد الخوارزمية هو 0(A).

مثال 2.دعونا نقدر مدى تعقيد البرنامج الذي يدخل مصفوفة من لوحة المفاتيح ويجد فيها عنصرًا له خاصية معينة (على سبيل المثال، يساوي قيمة معينة). تتكون الخوارزمية من الخطوات التالية:

• - إدخال الصفيف (عمليات الإدخال)؛
• - البحث عن عنصر له خاصية معينة (يمكن تحديد موقع العنصر إما بالقرب من بداية المصفوفة أو في نهايتها؛ إذا كان العنصر غير موجود، فيجب إجراء جميع مقارنات A للتأكد من ذلك)؛
• - إخراج النتيجة.

في أفضل الحالات، ستتطلب الخوارزمية المحددة عمليات A + 2 (إدخال المصفوفة بأكملها، مقارنة واحدة، إخراج)، في أسوأ الحالات (عند عدم وجود مثل هذا العنصر، عملية 2A + 1). إذا كان A رقمًا كبيرًا، على سبيل المثال في حدود 10 6، فيمكن إهمال الوحدة. ولذلك، فإن تعقيد الخوارزمية يساوي 0(ن).

مثال 3.دعونا نحدد وظيفة التعقيد لخوارزمية التشفير لكلمة طويلة لبطريقة الاستبدال. يجب أن يكون هناك جدول يُكتب فيه لكل حرف من الحروف الأبجدية الحرف الذي يجب استبداله به. دعونا نشير إلى عدد الحروف الأبجدية س.تتكون الخوارزمية من الخطوات التالية:

• - إدخال كلمة (عملية واحدة)؛
• - تنظيم الدورة:
  • 1) لكل حرف ابحث عن بديل له في الجدول (إذا لم يكن الجدول مرتبًا ولا يحتوي على أي خصائص تسهل البحث، ففي أسوأ الحالات ستحتاج سعمليات لشخصية واحدة إذا كان العنصر الذي تم البحث عنه في النهاية)؛
  • 2) إخراج الرمز الموجود؛
• - نهاية الدورة.

إجمالي عدد العمليات 1+ (س+)ل.في حالة كبيرة بما فيه الكفاية سو ليمكن إهمال الوحدات، واتضح أن وظيفة التعقيد للخوارزمية المحددة هي يا(س ل).

مثال 4.دعونا نحدد وظيفة التعقيد لخوارزمية ترجمة الأعداد الطبيعية 1 V لنظام الأرقام الثنائية (بدون عمليات إدخال وإخراج البيانات). تتكون الخوارزمية من الخطوات التالية:

• - حلقة حتى نتيجة قسمة رقم على 2 تساوي 0:
• - قسمة الرقم على 2 وتذكر الباقي؛
• - أخذ نتيجة القسمة كرقم جديد؛
• - نهاية الدورة.

العدد الإجمالي للعمليات لا يتجاوز 1 + سجل 2 أ. لذلك، فإن الخوارزمية الموصوفة لها تعقيد 0(عوج 2 ن).