متنوع

تعقيد الوقت: لماذا تعمل بعض الخوارزميات لمليارات السنين

تعقيد الوقت: لماذا تعمل بعض الخوارزميات لمليارات السنين

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

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

ما هو الوقت المعقد؟

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

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

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

1. اسمحوا ص = 0
2. في حين ص يكون <= إلى ف
3. ص=ص+ص
4. ص = ص+1
5. العودة ص

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

ولكن هذا هو عدد المرات التي نكررها خلال الحلقة ، وعلينا أيضًا حساب العمليات داخلها ، حيث نضيف ص و ص و تعيين النتيجة ل ص ثم نضيف ص و 1 ثم قم بتعيين النتيجة إلى ص. لذلك نحن نؤدي عمليتين لكل تكرار، و ها هم ف - (ص - 1)التكرارات. كل ما علينا فعله الآن هو الضرب 2 عمليات و ف - (ص - 1)التكرارات لتأخذ، لتمتلك 2 * (q - (p - 1)) العمليات للحلقة بأكملها. أضف العمليات عند 1. و 5. ، مما يعطينا العدد النهائي 2 * (q - (p - 1)) + 2 عمليات لهذه الخوارزمية.

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

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

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

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

1. ع = (ص 1 * (ع)) / 2
2. ف
= (ف * (ف + 1)) / 2
3. إرجاع ( ف -ص )

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

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

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

ما هو تدوين Big O؟

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

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

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

* يا (1): التعقيد الزمني الثابت- هذا هو المرور المجاني الحسابي الفعال الذي تحدثنا عنه من قبل. هذا لا يعني بالضرورة أنه أسرع. هذا يعني فقط أن ملف تعقيد الوقت لا علاقة لها بحجم المدخلات.

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

* على): التعقيد الزمني الخطي- كانت هذه خوارزمية التجميع لدينا منذ البداية.

* س (ن سجل ن): التعقيد الزمني الخطي- إجراء تحويل فورييه السريع هو O (n Log n) الخوارزمية ، كما هي Mergesort.

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

* علىج، ج> 1): التعقيد الزمني متعدد الحدود- التعقيد الزمني متعدد الحدود يكون مهم جدا لأنها أكثر أو أقل يمثل الحد الأعلى على ما أ الكمبيوتر الكلاسيكي يمكن حلها في فترة زمنية عملية.

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

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

لماذا لا يمكننا مجرد التوصل إلى خوارزميات أفضل

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

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

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

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

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

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


شاهد الفيديو: تعلم البرمجة. 01 - هل البرمجة صعبة وازاي اقدر اتعلمها وايه المراحل اللي هتعدي بيها #مراحلالبرمجة (شهر نوفمبر 2021).