وقت التشغيل التقريبي يعتمد على مدى تعقيد الخوارزمية. أنواع وظائف تعقيد الخوارزمية

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

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

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

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

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

مثال 1. دعونا نقدر التعقيد الزمني للخوارزمية لحساب مضروب عدد صحيح موجب.

مضروب الدالة (س: عدد صحيح): عدد صحيح؛

فار م، ط: عدد صحيح؛

For i:=2 To x Do m:=ro*i;

لنحسب إجمالي عدد العمليات التي يقوم بها البرنامج متى قيمة معينةس. يتم تنفيذ العامل m:=1; مرة واحدة. جسم الحلقة (الذي يتم فيه تنفيذ عمليتين: الضرب والتخصيص) x - 1 مرة؛ يتم تنفيذ عامل المهمة:=m مرة واحدة. إذا تم أخذ كل عملية كوحدة تعقيد، فإن التعقيد الزمني للخوارزمية بأكملها سيكون 1 + 2 (x - 1) + 1 = 2x ومن ثم فمن الواضح أن القيمة x يجب أن تؤخذ كمعلمة. دالة التعقيد الزمني هي كما يلي:

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

مثال 2. حساب المنتج القياسي لمتجهين A = (a1، a2، …، ak)، B = (b1، b2، …، bk).

For i:=l To k Do AB:=AB+A[i]*B[i];

في هذه المشكلة، حجم البيانات المدخلة هو n = 2k. عدد العمليات المنفذة هو 1 + 3k = 1 + 3(n/2). هنا يمكنك أن تأخذ V=k=n/2. لا يوجد اعتماد في تعقيد الخوارزمية على قيم عناصر المتجهات A و B. كما في المثال السابق، يمكننا هنا التحدث عن الاعتماد الخطي لتعقيد الوقت على معلمة البيانات.

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

المشكلة الثانية تتعلق بتصنيف الخوارزميات حسب التعقيد الزمني. تنمو الدالة Tα(V) عادةً مع زيادة V. ما مدى سرعة نموها؟ هناك خوارزميات ذات اعتماد خطي لـ Tα على V (كما كان الحال في الأمثلة التي درسناها)، مع اعتماد تربيعي، ومع اعتماد على درجات أعلى. تسمى هذه الخوارزميات متعددة الحدود. وهناك خوارزميات ينمو تعقيدها بشكل أسرع من أي كثيرة حدود. المشكلة التي غالبًا ما يحلها منظرو الخوارزمية هي السؤال التالي: هل الخوارزمية متعددة الحدود ممكنة لمشكلة معينة؟

الوظائف التي تتم مواجهتها غالبًا عند تحليل الخوارزميات:

• سجل ن(الوقت اللوغاريتمي)،
• ن(الزمن الخطي)،
• نسجل ن,
• ن 2 (الوقت التربيعي)،
• 2ن(الوقت الأسي).

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

• ن= 50 ≈ 19 دقيقة،
• ن = 60 ≈ 320 ساعة،
• ن = 70 ≈ 37 سنة.

السؤال 15=49. الخوارزميات المتسلسلة والدورية والعودية.

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

مثال. احسب محيط المثلث الذي أضلاعه أ، ب، ج.13

خوارزمية هيكل المتفرعة

من الناحية العملية، نادرًا ما يكون من الممكن تقديم حل لمشكلة ما في شكل خوارزمية

هيكل خطي. في كثير من الأحيان يعتمد على أي وسيط

يتم تنفيذ النتائج الحسابية إما وفقًا لواحد أو لآخر

الصيغ، أي اعتمادا على تنفيذ البعض حالة منطقية

يتم تنفيذ العملية الحسابية وفقًا لصيغة أو أخرى.

تسمى الخوارزمية لمثل هذه العملية الحسابية بالخوارزمية

هيكل المتفرعة.

التفرع هو هيكل تحكم ينظم تنفيذ العمليات فقط

أحد الإجراءين المحددين بحسب العدل

بعض الشرط.

الشرط هو سؤال له إجابتان محتملتان: نعم أو لا.

يتم تسجيل التفرع في شكلين: كامل وغير كامل (الشكل 1 أ، ب).

أ) النموذج الكامل ب) النموذج غير الكامل

الخوارزميات الدورية – الخوارزميات التي من الضروري فيها حساب القيم بشكل متكرر باستخدام نفس التبعيات الرياضية (المخططات الكتلية). معان مختلفةالكميات الموجودة فيها. يمكن أن يؤدي استخدام الحلقات إلى تقليل حجم الدائرة بشكل كبير

الخوارزمية وطول البرنامج المقابل. هناك دورات مع

عدد معين وغير معروف من التكرار. مع عدد معين من التكرار -

حلقة مع العداد. مع عدد غير معروف من التكرارات - حلقة ذات شرط مسبق،

حلقة مع الشرط اللاحق.

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

تنظيم العمليات الحسابية التي تستدعي فيها الدالة نفسها وسيطة أخرى

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

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

- شرط استكمال الدورة؛

- جسم العودية، والذي يتضمن الأفعال المقصودة

التنفيذ في كل تكرار؛

- خطوة العودية التي تستدعي فيها الخوارزمية العودية نفسها.

هناك فرق بين العودية المباشرة وغير المباشرة. في الحالة الأولى، الخوارزمية

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

ويسمى العودية بشكل غير مباشر.

الشرط الرئيسي للخوارزميات العودية هو أن عملية الانعكاس ليست كذلك

يجب أن تكون لا نهائية. بمعنى آخر، يجب تنفيذه

التحقق من اكتمال المكالمة، أو في تعريف متكرر

هناك قيود بموجبها مزيد من التهيئة

توقف العودية.

مثال على الدالة العودية هو حساب مضروب الرقم.

عامل كثافة العمليات (كثافة العمليات ن)

إذا (ن) قم بإرجاع n*factoria(n-1);

آخر العودة 1؛

مثال على الإجراء العودي:

الإجراء التوصية (أ: عدد صحيح)؛ ابدأ إذا كان a>0 ثم Rec(a-1); writeln(أ); نهاية؛

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

لتقييم فعالية الخوارزمية، أهم المؤشرات هي:

وقت تنفيذ الخوارزمية
- المبلغ المطلوب من ذاكرة الوصول العشوائي.

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

تبسيطات لتقدير وقت تنفيذ الخوارزميات

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

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

\(1/6 ن^3 + 20ن + 16 \سيم 1/6ن^3\)،

بدلاً من \(1/6N^3\) يكتبون "هذه الخوارزمية لها تعقيد \(O(N^3)\)، بدلاً من \(3N^4\) يكتبون "هذه الخوارزمية لها تعقيد \(O(N) ^4)\ )".

تعريف الكبير O

يقال أن \(f\) هو "O كبير" لـ \(g\) لـ \(x \to x_0\) إذا كان هناك ثابت \(C>0\) بحيث يكون لجميع \(x\) من جوار النقطة \(x_0\)، تظل المتراجحة \(|f(x)| \leq C|g(x)|\) قائمة. يوجد أدناه رسم توضيحي للتعريف (المحور \(x\) هو حجم بيانات الإدخال، والمحور \(y\) هو وقت تنفيذ الخوارزمية). نرى أنه بدءًا من نقطة معينة، حيث أن حجم البيانات المدخلة يميل إلى \(\propto\) \(f(n)\) ينمو بشكل أبطأ من \(g(n)\) وبشكل عام \(g (ن)\) كأنما يحدها من فوق.

أمثلة. \(1 = O(N)، N = O(N^2).\)

بالإضافة إلى تقديرات النموذج \(O(N)\)، يتم استخدام التقدير \(\Omega(N)\) (أوميغا كبير). ويشير إلى الحد الأدنى لنمو الوظيفة. على سبيل المثال، دع عدد عمليات الخوارزمية يتم وصفه بواسطة الدالة \(f(N)=\Omega(N^2)\). وهذا يعني أنه حتى في أنجح الحالات، سيتم تنفيذ إجراءات \(N^2\) على الأقل. بينما يضمن التقدير \(O(N^3)\) أن الحالة الأسوأ لن تكون أكثر من إجراءات \(N^3\). يتم استخدام التقدير \(\Theta(N)\) أيضًا، وهو التقدير المقارب العلوي والسفلي عندما\(O(N)\) و \(\Omega(N)\) هي نفسها.لذلك، \(O(N)\) هو تقدير تقريبي للخوارزمية على أسوأ بيانات الإدخال،\(\Omega(N)\) - على أفضل بيانات الإدخال،\(\Theta(N)\) - تدوين مختصر للكلمة المتطابقة\(O(N)\) و \(\أوميغا(N)\).

تقديرات وقت التشغيل لخوارزميات مختلفة

دعونا نشير إلى T(N) باعتباره وقت تنفيذ الخوارزمية. دع الخوارزمية قيد الدراسة لها الشكل:

1. مجموعة من التعليمات بما في ذلك فقط العمليات الأساسية:

البيان 1؛
...
بيان ك؛

ثم T(N) = T(البيان 1) + ... + T(البيان ك).

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

2. تصريحات إذا كان آخر

إذا (الشرط) (
تسلسل التصريحات 1
}
آخر(
تسلسل التصريحات 2
}

هنا سيتم تنفيذ إما تسلسل العبارات 1 أو تسلسل العبارات 2، منذ ذلك الحين نريد تقدير وقت تنفيذ الحالة الأسوأ، T(N) = max(T(تسلسل العبارات 1)، T(تسلسل العبارات 2)). على سبيل المثال، إذا كان وقت تنفيذ تسلسل العبارات 1 هو O(N)، وتسلسل العبارات هو O(1)، فإن T(N) = O(N).

من أجل (i = 0؛ i< N; i++) {
تسلسل التصريحات
}

لأن سيتم تنفيذ الحلقة N مرات، ثم سيتم تنفيذ تسلسل البيانات أيضًا N مرات. إذا كان T(تسلسل البيانات) = O(1)، فإن T(N) = O(N)*O(1) = O(N).

4. الحلقات المتداخلة.

من أجل (i = 0؛ i< N; i++) {
ل (ي = 0؛ ي< M; j ++){
...
}
}

يتم تنفيذ الحلقة الخارجية N مرات. في كل مرة يتم تنفيذ الحلقة الخارجية، يتم تنفيذ الحلقة الداخلية M

الآن فكر في هذا الرمز:

من أجل (i = 0؛ i< N; i++) {
ل (ي = ط + 1؛ ي< N; j ++){
تسلسل التصريحات
}
}

دعونا نلقي نظرة على التغير في عدد تكرارات الحلقة الداخلية اعتمادًا على تكرار الحلقة الخارجية.

I دورة j (عدد مرات التنفيذ)
0 ن
1 ن-1
2 ن-2
...
ن-1 1

ثم سيتم تنفيذ تسلسل العبارات N + N-1 + ... + 1 مرة. لحساب هذه المبالغ بسرعة، تكون الصيغ من التحليل الرياضي مفيدة، في هذه الحالة الصيغة

أولئك. سيكون لهذه الخوارزمية تعقيد \(O(N^2)\).

وإليك الصيغ الأخرى الأكثر طلبًا والمفيدة لمثل هذه الحالات:

4. عندما يتضمن التأكيد استدعاء طريقة، يتم حساب تقدير وقت تنفيذ التأكيد مع الأخذ في الاعتبار تقدير وقت تنفيذ الطريقة. على سبيل المثال:

ل (ي = 0؛ ي< N; j ++){

إذا كان وقت تنفيذ الطريقة هو \(g(N)=O(N)\)، \(T(N) = O(N)*O(N) = O(N^2)\).

5. البحث الثنائي (الثنائي).

إنت ل = 0؛
إنت ش = أ.الطول - 1
كثافة العمليات م؛
بينما (ل<= u) {
م = ل + (ش - 1)/2
إذا أ[م]< k {
ل = م +1؛
}
وإلا إذا كان A[m] == k (
عودة م؛
}
آخر(
ش = م - 1؛
}
}
العودة -1؛

يتيح لك البحث الثنائي العثور على فهرس الرقم k في مصفوفة مرتبة؛ إذا لم يكن هذا الرقم موجودًا فيه، فسيتم إرجاع -1. أولاً نقارن k بالرقم الموجود في منتصف المصفوفة. إذا كان k أقل من هذا الرقم، فيجب علينا البحث عنه في النصف الأيسر من المصفوفة، وإذا كان أكثر، ففي النصف الأيمن. بعد ذلك، تتم مقارنة k بالرقم الموجود في منتصف نصف المصفوفة المحددة في الخطوة السابقة، وما إلى ذلك. مع كل تكرار، يتم تقليل مساحة البحث بمقدار النصف. السؤال الذي يطرح نفسه هو: كم عدد التكرارات التي يجب إجراؤها في أسوأ الحالات (أي عندما لا يتم العثور على رقم يساوي k في المصفوفة مطلقًا ولا توجد بيانات متبقية للمقارنة).

نرى أنه بعد تكرار واحد ستكون هناك بيانات \(N/2\) متبقية للبحث عن الفهرس \(k\)، وبعد تكرارين سيكون هناك بيانات \(N/4\) متبقية، وبعد 3 تكرارات - \( N/8\) وغيرها. سنعرف عدد التكرارات في أسوأ الحالات إذا قمنا بحل المعادلة \(\frac(N)(2^x)=1\). هذه المعادلة تعادل المعادلة \(2^x=N\)، وبالتالي \(x=log_(2)(N)\) أو \(x=log(N)\) (انظر تعريف اللوغاريتم). ولذلك، فإن تقدير التعقيد لخوارزمية البحث الثنائي هو \(O(logN)\).

والخبر السار هو أنه لتحديد وقت تنفيذ معظم الخوارزميات، يكفي عدد قليل من الوظائف: \(1, logN, N, NlogN, N^2, N^3, 2^N\). يوضح الرسم البياني معدلات النمو المختلفة في وقت تنفيذ الخوارزمية اعتمادًا على حجم البيانات المدخلة:

ومن هذا الرسم البياني، على وجه الخصوص، يتضح أنه إذا كان وقت تنفيذ الخوارزمية "لوغاريتميًا"، أي. الخوارزمية معقدة \(O(logN)\)، فهذا رائع جدًا، لأن ينمو وقت التنفيذ ببطء شديد مع زيادة حجم بيانات الإدخال، إذا كان وقت التنفيذ يعتمد خطيًا على حجم بيانات الإدخال، فهذا أيضًا ليس سيئًا، ولكن من الأفضل عدم استخدام الخوارزميات ذات وقت التشغيل الأسي (\( O(2^N)\)) أو استخدمه فقط على أحجام البيانات الصغيرة جدًا.

فصول P و NP

تسمى الدالة الحقيقية غير السالبة \(f(m)\)، المحددة للقيم الصحيحة الموجبة للوسيطة، متعددة الحدود إذا كان هناك كثير الحدود \(P(m)\) مع معاملات حقيقية مثل \( f(m) \leq P( m)\) للجميع \(m \in N^+\). تنتمي المشكلات التي توجد لها خوارزميات ذات وقت تشغيل "متعدد الحدود" إلى الفئة P (يتم حل هذه المشكلات بشكل عام بسرعة ودون أي مشاكل).

تعريف رسمي.تنتمي اللغة L إلى الفئة P إذا وفقط في حالة وجود آلة تورينج حتمية M بحيث:

بالنسبة لأي بيانات مدخلة، تنتهي M من عملها في وقت متعدد الحدود،
- لجميع \(x \in L\) M ينتج النتيجة 1،
- لجميع \(x\) التي لا تنتمي إلى \(L\)، M تنتج النتيجة 0.

مشاكل فئة NP- المهام التي تحقق الشرط: إذا كان هناك إجابة (حل محتمل)، فمن السهل التحقق منها - تحقق مما إذا كان حلاً أم لا.

لنفكر في مثال لمشكلة من فئة NP. لنفترض مجموعة من الأعداد الصحيحة، على سبيل المثال، (-7، -3، -2، 5، 8). تحتاج إلى معرفة ما إذا كان هناك 3 أرقام من بين هذه الأرقام التي مجموعها 0. في هذه الحالة، الجواب هو "نعم" (على سبيل المثال، مثل هذا الثلاثي هو الأرقام (-3،-2،5). كما يزداد حجم مجموعات الأعداد الصحيحة، ويزداد عدد المجموعات الفرعية المكونة من 3 عناصر بشكل كبير، وفي الوقت نفسه، إذا حصلنا على مجموعة فرعية واحدة (وتسمى أيضًا شهادة)، فيمكننا بسهولة التحقق مما إذا كان مجموع عناصرها صحيحًا. يساوي 0.

تعريف رسمي:

تنتمي اللغة L إلى الفئة NP إذا وفقط في حالة وجود كثيرات الحدود \(p\) و\(q\) وآلة تورينج حتمية M بحيث:

بالنسبة لأي \(x,y\)، يقوم الجهاز M الموجود على بيانات الإدخال \((x,y)\) بالتنفيذ في الوقت المناسب \(p(|x|)\)،
- لأي \(x \in L\) هناك سلسلة \(y\) بطول \(q(|x|)\) بحيث \(M(x,y)=1\)،
- لأي \(x\) ليس من \(L\) وجميع السلاسل ذات الطول \(q(|x|)\) \(M(x,y)=0\).

قابلية الاختزال متعدد الحدودأو اختزال الكارب. يتم تقليل الدالة \(f_1\) إلى الدالة \(f_2\) إذا كانت هناك دالة \(f \in P\) بحيث تكون لأي \(x\) \(f_(1)(x)=f_( 2 )(و(خ))\).

تسمى المشكلة T NP-كاملة، إذا كان ينتمي إلى الفئة NP وأي مشكلة أخرى من NP يمكن اختزالها إليها في زمن متعدد الحدود. ولعل المثال الأكثر شهرة لمشكلة NP-Complete هو مشكلة SAT (من كلمة الإشباع). لنحصل على صيغة تحتوي على متغيرات منطقية وعوامل التشغيل "AND" و"OR" و"NOT" والأقواس. المشكلة هي: هل من الممكن تعيين قيم لجميع المتغيرات التي تظهر في الصيغة؟ كذبو حقيقيبحيث تأخذ الصيغة القيمة " حقيقي".

تسمى المشكلة T NP-صعب، إذا كانت هناك مشكلة NP-Complete والتي تقلل إلى T في وقت متعدد الحدود. ما نعنيه هنا هو قابلية كوك للاختزال. إن اختزال كوك للمشكلة \(R_1\) إلى \(R_2\) هو خوارزمية زمنية متعددة الحدود تحل المشكلة \(R_1\) بشرط أن يتم إعطاء الوظيفة التي تجد حل المشكلة \(R_2\) لها على أنها أوراكل أي أن الوصول إليه لا يتطلب سوى خطوة واحدة.

فيما يلي العلاقات المحتملة بين فئات المشكلات المذكورة أعلاه (لا يزال العلماء غير متأكدين مما إذا كانت P وNP متماثلتان).

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

تصنيف الصعوبة

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

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

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

أمثلة

O(n) - التعقيد الخطي

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

O(log n) - التعقيد اللوغاريتمي

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

O(ن 2) - التعقيد التربيعي

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

هناك تصنيفات أخرى للصعوبة، لكنها جميعها تقوم على نفس المبدأ.

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

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

الفصل 2. تعقيد الخوارزميات.

2.1 الوقت والتعقيد الحسابي للخوارزميات.

التعقيد الزمني للخوارزمية (ت(ن) ، أين ن– حجم المشكلة) هو وقت تنفيذ الخوارزمية، ويقاس بالخطوات (تعليمات الخوارزمية التي يجب تنفيذها لتحقيق نتيجة). أي أن هذا هو عدد العمليات الأولية التي تشكل الخوارزمية لحل المشكلة (:=،<>, =, +, –, *, /; و، أو لا، xor؛ اتصل، ارجع).

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

https://pandia.ru/text/78/183/images/image002_151.gif" width="178 height=60" height="60">

يحدث ت(ن)= ج* ن2 ينطبق على مصفوفة مربعة.

العمليات الأولية في هذه الحالة هي مزيج من "+" و"*".

إذا كانت المصفوفة الأصلية هي الهوية، فسنحصل على أفضل حالة.

إذا كان نصف العناصر في المصفوفة 0، والنصف الآخر 1، فإننا نحصل على حالة متوسطة.

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

2.2 ياو Ω - الرموز.

سلوك التعقيد الزمني مع الزيادة ن (ن® ¥ ) مُسَمًّى التعقيد المقارب للخوارزمية.

لوصف معدل نمو التعقيد المقارب، نستخدم تدوين O.عندما يقولون أن التعقيد الزمني للخوارزمية هو أمر جيد ن2 :

ت(ن)= يا(ن2 )= يا(F(ن)),

وهذا يعني أن هناك ثوابت إيجابية ج، ن0=مقدار ثابت (ج>0), بحيث للجميع ن ³ ن0 عدم المساواة يحمل

ت(ن) £ ج* F(ن)

هذا هو الحد الأعلى لتقدير التعقيد.

مثال 2:

يترك تي(0)=1، تي(1)=4، …، تي(ن)=(ن+1)2، فإن التعقيد الزمني لهذه الخوارزمية له ترتيب النمو ت(ن)= يا(ن2 ).

ويمكن أن يظهر ذلك للجميع ن > ن0 في ن0 = 1, ج = 4 عدم المساواة (١) راضٍ.

(ن+1)2 £ 4* ن2

مثال 3:

إذا تم كتابة التعقيد الزمني على أنه متعدد الحدود

ت(ن)= ج1 ن2 + ج2 ن+ ج3 ,

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

ت(ن)= يا(ن2 ).

على سبيل المثال:

3 ن2 +5 ن+1 £ 5 ن2

" ن ³ 1

مثال 4:

إذا كانت بعض الخوارزميات تحتوي على تعقيد مضاعف 3 نومن ثم يمكن إثبات أن ترتيب الزيادة في السرعة لا يمكن أن يكون متعددا يا(2 ن):

ت(ن)=3 ن¹ يا(2 ن).

يجب أن تكون هناك ثوابت ج, ن0 ، بحيث يحمل عدم المساواة التالية:

3ن £ ج*2 ن, ن > ن0 .

ومن هنا نحصل على:

مع³ (3/2)2, ن > ن0 .

لكن عندما ن® ¥ لا يوجد مثل هذا الثابت مع، والتي من شأنها أن تلبي هذا عدم المساواة.

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

ت(ن) ³ دبليو(F(ن))

عدم المساواة (2) يعني أن هناك بعض الثبات مع، والتي في ن® ¥ تعقيد الوقت

ت(ن) ³ ج* F(ن).

نظرًا لصعوبة التحديد الدقيق لـ T(N) (التعقيد الزمني المقارب)، اعتمادًا على حجم البيانات الأولية، يتم عمليًا استخدام الحدود الدنيا والعليا للتعقيد الزمني للخوارزمية:

ت(ن) = س (F(ن))

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

مثال 5:

دع التعقيد الزمني يكتب بواسطة الصيغة

تي(ن)=3ن2 –100ن+6=يا(ن2)

3n2 >3n2 –100n+6, ن³ 1، ج = 3.

لو ج1» 0 (C1=0.00001)، ثم عدم المساواة

10-5 ن2 > 3 ن2 –100 ن+6, ن³ 1

لم ينفذ.

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

3ن2 –100ن+6¹ على).

ج*ن< 3N2, N>ج.

3ن2 –100ن+6=(ن2)

ج=2.29, ن ³ ن0.

2.99* ن2 < 3 ن2 –100 ن+6

ويمكن أن يظهر أن الحد الأدنى

3 ن2 –100 ن+6 ¹ دبليو(ن3 ) في ج = 1.

عدم المساواة 3 ن2 –100 ن+6 ³ ن3 لم ينفذ.

3 ن2 –100 ن+6= دبليو(ن)

ج1 = , ن> ن0 .

https://pandia.ru/text/78/183/images/image007_89.gif" width = "305" height = "247 src = ">

F1 (ن)=100 ن2

F2 (ن)=5 ن3

ن0 =20 – نقطة حرجة.

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

0 " style="margin-left:5.4pt;border-collapse:collapse;border:none">

ن!

مثال 6:

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

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

دعونا نعطي خمس خوارزميات لحل نفس المشكلة، كل واحدة منها معقدة:

أ1: 100 ن

أ2: 100 ن* سجلN

أ3: 10 ن2

أ4: ن3

أ5: 2 ن

ثم لمشاكل مع ن=2 ¸ 9 A5 سيكون أسرع ( F(ن) ~ 4 ¸ 512 ). ستعطي الخوارزميات الأخرى نتائج أقل بكثير عند الاستبدال.

في ن=10 ¸ 58 يبدو أن A3 هو الأفضل.

في ن=59 ¸ 1024 سيكون A2 هو الأكثر فعالية.

في ن>1024 يفضل A1.

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

حكم المجموع : دع البرنامج يتكون من خوارزميتين تم تنفيذهما بالتسلسل P1 و P2، حيث يتم تحديد التعقيد يا(F(ن)) و يا(ز(ن)) على التوالى. بعد ذلك سيتم تحديد التعقيد الزمني للبرنامج بأكمله كمجموع التعقيدات الزمنية لكل من الخوارزميات:

ت(ن) = ت1 (ن)+ ت2 (ن)

في الحالة العامة نحصل على:

تي (ن)Þ O(الحد الأقصى f(n)، g(n))

حكم الأشغال: دع التعقيد الزمني لبرنامج يتكون من خوارزميتين تنفيذيتين متوازيتين بترتيب التعقيد يا(F(ن)) و يا(ز(ن)) وبناء على ذلك، يتم تعريفه على أنه نتاج التعقيدات الزمنية لكل من الخوارزميات:

ت(ن) = ت1 (ن)* ت2 (ن)

على العموم:

ت(ن) Þ يا(F(ن)* ز(ن))

اللوغاريتمات.

2.3. العودية.

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

F(ن) Þ F(ن* F(ن-1))

على سبيل المثال، لتقييم الخوارزمية بشكل متكرر n! سيعتمد التعقيد على مدى تعقيد كل من الخوارزميات المضمنة في العودية.

على العموم ت(ن) ~ يا(ن).

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

2.4 تقييم مدى تعقيد الخوارزميات والبرامج.

2.4.2 خوارزميات استعادة التبعية.

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

لبناء اعتماد تحليلي لتعقيد البرنامج، قم بتقييم الوظيفة ت(ن) في فترة ما [ نمين, نماكس] . ثم يتم تقريب المنحنى الموجود لبعض الوظائف التحليلية، وتغيير معلمات الوظيفة وتقدير خطأ التقريب.

كقاعدة عامة، يتم استخدام وظائف التعقيد الزمني المعروفة على هذا النحو: يا(ن!), يا(XN), يا(نكس), يا(سجلN), يا(https://pandia.ru/text/78/183/images/image010_72.gif" width="307" height="225 src=">ونتيجة لتجربة البرنامج، تم إنشاء جدول للصعوبات الزمنية مُقتَنىً:

ونتيجة للبحث عن تقريب للدالة، تم الحصول على الاعتماد التحليلي التالي:

https://pandia.ru/text/78/183/images/image012_68.gif" width = "321" height = "143 src = ">

مثال 2:

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

في هذه الحالة، يتم إنشاء عائلة من الوظائف التقريبية ويتم العثور على مدى تعقيد الخوارزمية من الناحية التحليلية.

كثافة اليد العاملة" href="/text/category/trudoemkostmz/" rel="bookmark">كثافة اليد العاملة (وقت العمل).

إن الطبيعة متعددة الحدود أو الأسية للخوارزمية ثابتة فيما يتعلق بشكل تمثيل بيانات الإدخال (نظام ثنائي أو عشري أو أي نظام أرقام آخر).

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

المشاكل التي يكون تعقيدها الزمني أسيًا ( ت(ن)= يا(كن) ) ، غير متضمنة في R.

تعليق : يمكن إثبات أن المشكلات ذات التعقيد الخطي مدرجة في P

ت(ن)= يا(ن1 )

دعونا نقدم فئة من مشاكل NP التي يمكن حلها في زمن متعدد الحدود باستخدام خوارزمية غير حتمية.

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

في خوارزمية غير حتمية (NDA) لأي حالة معينة يمكن أن يكون هناك أكثر من حالة تالية مقبولة، أي أن مثل هذه الخوارزمية يمكنها تنفيذ أكثر من عبارة واحدة في أي وقت محدد.

NDA ليست خوارزمية عشوائية أو احتمالية. إنها خوارزمية يمكن أن تكون في العديد من الحالات (وهذا يعادل حل مشكلة مع العديد من الخيارات بالتوازي).

مثال:

من شأن الخوارزمية الحتمية (DA) أن تحل هذه المشكلة بشكل تسلسلي (البحث في جميع الخيارات، والمقارنة مع معيار الأمثلية K0 حتى تختار البديل A0).

يمكن لـ NDA في نفس الوقت (بالتوازي) تلقي جميع البدائل ومقارنتها بـ K0، ونسخ نفسها في النموذج عملية منفصلةلكل بديل، والذي يتم تنفيذه بشكل مستقل.

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

الذي - التي. يتميز NDA بثلاثة معايير:

1. خيار- دالة متعددة القيم تكون قيمها عناصر من المجموعة S؛

2. فشليتسبب في توقف نسخة من الخوارزمية عن العمل؛

3. نجاحيتسبب في توقف جميع نسخ الخوارزمية عن العمل وإصدار نتيجة.

من الواضح أنه لا يوجد الجهاز الماديغير قادر على السلوك غير الحتمي غير المحدود، مما يعني أن NDA هي طريقة نظرية.

تشكل المشكلات التي يمكن حلها باستخدام NDA متعدد الحدود فئة من مشاكل NP.

2.5.2 ن.ب.-صعب ون.ب.- المهام الكاملة.

المشكلة المدرجة في P هي ن.ب.-صعب، إذا كان هناك متعدد الحدود DA (PDA) لحله، والذي يمكن استخدامه للحصول على حلول لجميع المشكلات المدرجة في NP. وهذا يعني أن المشكلة تكون صعبة NP إذا كانت على الأقل بنفس صعوبة أي مشكلة NP.

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

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

لإثبات أن المشكلة هي NP كاملة، فمن الضروري إثبات أنها تنتمي إلى NP.

تعتبر فكرة استخدام خوارزمية لحل مشكلة ما للحصول على خوارزمية لحل مشكلة أخرى من أهم الأفكار في نظرية الخوارزميات.

التعريف 1: يتم تحويل المهمة P1 إلى المهمة P2 إن وجدت حالة خاصةيمكن تحويل المشاكل P1 في زمن كثير الحدود إلى حالة خاصة من المشكلة P2. ثم يمكن الحصول على الحل P1 في زمن متعدد الحدود من الحل إلى حالة خاصة من المشكلة P2.

https://pandia.ru/text/78/183/images/image024_39.gif" width="158 height=56" height="56">

على سبيل المثال:

F2 (الحادي عشر)=(س1 Ú س2 ) Ù ( ) Ù ()

غير ممكن، لأن لأي الحادي عشر F2 (الحادي عشر)= خطأ شنيع.

نظرية :

مشكلة الإشباع هي NP-Complete.

اختيار الحادي عشر (صحيح، خطأ)

إذا كان E(x1, x2,…, xN) فالنجاح

فشل آخر

باستخدام تحويل المشكلة P1 إلى P2، يمكن إثبات أنه حتى الحالة المحدودة لمشكلة الإشباع تكون NP-كاملة.

ك-الجدوى .

تعني K-satisfiability أن أي جملة مدرجة في CNF تحتوي على متغيرات منطقية K على الأكثر.

الحد الأدنى للحالة K = 3. بالنسبة للدالة المنطقية الممثلة في CNF، يمكن العثور على الدالة في زمن متعدد الحدود ه*(×2)، لا تحتوي على أكثر من ثلاثة متغيرات في كل جملة. ثم هقابلة للتنفيذ إذا كانت قابلة للتنفيذ ه*.

ه* (س1 , س2 ,…, xn) ® ه* (الحادي عشر)

للقيام بذلك، استخدم طريقة تقليل ترتيب الجملة

(أ1 Ú أ2 Ú … Ú أك)=(أ1 Ú أ2 Ú ض) Ù (أ3 Ú أ4 Ú … Ú أك Ú )

باستخدام عملية التحلل التكراري، يمكن للمرء الحصول عليها ه*.

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

حالة خاصة: عندما تكون K=2 الدالة هالمدرجة في ر.

يمكن أيضًا أن تتضمن أمثلة مشكلات الفئة NP مشاكل الرسم البياني :

1) تحديد الحد الأقصى لمجموعات الرسم البياني غير الموجه (مشكلة NP-hard).

2) مشكلة تحديد رسم بياني فرعي كامل (مشكلة NP-Complete).

3) تحديد الغطاء الرأسي للأصل L للرسم البياني غير الموجه (مشكلة NP الكاملة).

4) تحديد الحد الأقصى لأغطية الرأس للرسم البياني غير الموجه (مشكلة NP-hard).

5) مشكلة تحديد وجود دورة هاميلتونية للرسم البياني (مشكلة NP-Complete).

6) مشكلة البائع المتجول: تحديد الحركة المثلى على طول الرسم البياني مع إدخال واحد في كل قمة (مشكلة NP-hard).

7) مشكلة الجدولة (مشكلة NP كاملة).

2.6 المشاكل غير القابلة للحل خوارزميا

حصة المشاكل أعزبو جَسِيم.

على سبيل المثال:

5+7=؟ - مشكلة واحدة.

س + ص =؟ - مشكلة ضخمة.

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

على سبيل المثال، المفارقات هي:

مثال 1:

مشكلة هيلبرت العاشرة.

د. هيلبرت في عام 1901، عند حل معادلات ديوفانتين، طرح مشكلة تنص على:

ابحث عن خوارزمية تحدد بعض الحلول الصحيحة لمعادلة ديوفانتين التعسفية

F(س, ذ, …)=0

هذه كثيرة الحدود ذات أسس صحيحة ومعاملات صحيحة للمجاهول

أنكسن+an-1xn-1+…+a2x2+a1x+a0=0

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

في عام 1970، أثبت عالم الرياضيات في لينينغراد يو ماتياسيفيتش رياضيًا استحالة حل معادلة ديوفانتين بشكل عام.

مثال 2:

نظرية فيرما:

لا توجد مثل هذه الأعداد الصحيحة أ, ب، ق، ن (ن>2) ، والتي تحقق المساواة

ان + مليار = cn

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

مثال 3:

مشكلة جولدباخ.

صاغ هولباخ المشكلة في رسالة إلى أويلر عام 1742:

اثبات أن كل عدد صحيح ن³ 6 يمكن تمثيلها كمجموع ثلاثة أعداد أولية

ن= أ+ ب+ ج

هذا يعني أننا بحاجة إلى العثور على خوارزمية تسمح بأي عدد صحيح ن³ 6 ابحث عن تحليل واحد على الأقل إلى ثلاثة مصطلحات بسيطة.

تم اقتراح حل متكرر لهذه المشكلة من قبل أويلر: حتى نهذه المشكلة قابلة للحل وتعادل التحلل إلى مصطلحين بسيطين.

أثبت I. Vinogradov في عام 1937 أن هذا أمر غريب نيمكن العثور على ثلاثة حدود أولية، لكن لم يتم العثور على حل للأعداد الزوجية بعد.

تعيين	تفسير بديهي	تعريف
	Fيحدها أعلاه الدالة ز	النمط = "الحد الأقصى للعرض: 98%؛ الارتفاع: تلقائي؛ العرض: تلقائي؛" src = "/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border = "0"> أو style = "max-width: 98%؛ الارتفاع: تلقائي؛ العرض: تلقائي؛" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	Fيحدها أدناه الدالة ز(حتى عامل ثابت) بشكل مقارب	النمط = "الحد الأقصى للعرض: 98%؛ الارتفاع: تلقائي؛ العرض: تلقائي؛" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	Fيحدها من الأسفل والأعلى الدالة زمقارب	0)، n_0: \forall (n>n_0) \; |Cg(ن)|
	زيهيمن Fمقارب	النمط = "الحد الأقصى للعرض: 98%؛ الارتفاع: تلقائي؛ العرض: تلقائي؛" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	Fيهيمن زمقارب	النمط = "الحد الأقصى للعرض: 98%؛ الارتفاع: تلقائي؛ العرض: تلقائي؛" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	Fمقابل زمقارب

أمثلة

ملحوظات

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

إذا كان حل مشكلة معينة للرسم البياني n-vertex باستخدام خوارزمية واحدة يستغرق وقتًا (عدد الخطوات) بترتيب n C، وبأخرى - بترتيب n+n!/C، حيث C هو رقم ثابت، إذن وفقًا لـ "أيديولوجية متعددة الحدود" تكون الخوارزمية الأولى فعالة عمليًا، لكن الخوارزمية الثانية ليست كذلك، على الرغم من أنه، على سبيل المثال، عند C = 10 (10 10) يكون الوضع عكس ذلك تمامًا.

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

فصول الصعوبة

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

فئة P

مشكلة المساواة بين الفئتين P و NP

العلماء المشهورين

• ليونيد ليفين
• ألكسندر رازبوروف
• إيدي شامير

أنظر أيضا

روابط

• يوري ليفشيتس "المشكلات الحديثة لعلوم الكمبيوتر النظرية". دورة محاضرات حول الخوارزميات للمسائل NP-hard.
• أ.أ.رازبوروفعلوم الكمبيوتر النظرية: وجهة نظر عالم الرياضيات // كمبيوتررا. - 2001. - رقم 2. (رابط بديل)
• أ.أ.رازبوروفحول تعقيد الحسابات // التعليم الرياضي. - MCNMO، 1999. - العدد 3. - ص 127-141.

مؤسسة ويكيميديا. 2010.

تعرف على "التعقيد الزمني للخوارزمية" في القواميس الأخرى:

التعقيد الزمني (للخوارزمية)- — موضوعات حماية المعلومات EN تعقيد الوقت... دليل المترجم الفني

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

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

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

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

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

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

- (GM) نظام التشفير مع المفتاح العموميتم تطويره بواسطة شافي جولدفاسر وسيلفيو ميكالي في عام 1982. GM هو أول نظام تشفير للمفتاح العام الاحتمالي والذي يمكن إثبات قوته في ظل التشفير القياسي... ... ويكيبيديا إقرأ المزيد