[Powered by Google Translate] ربما كنت قد سمعت الناس يتحدثون عن خوارزمية بسرعة وكفاءة لتنفيذ مهمة معينة، ولكن ما الذي يعنيه بالضبط لخوارزمية أن تكون سريعة أو كفاءة؟ حسنا، انها لا نتحدث عن القياس في الوقت الحقيقي، مثل ثواني أو دقائق. وذلك لأن أجهزة الحاسوب والبرامج تختلف اختلافا جذريا. قد برنامجي تشغيل أبطأ من يدكم، لأنني تشغيله على كمبيوتر قديم، أو لأنني يحدث ليكون اللعب لعبة الفيديو على الانترنت في الوقت نفسه، والذي القص كل ما عندي من الذاكرة، أو قد تكون قيد التشغيل برنامج I بلدي من خلال البرامج المختلفة الذي يتصل مع الجهاز بشكل مختلف عند مستوى منخفض. انها مثل مقارنة التفاح والبرتقال. لمجرد كمبيوتر أبطأ بلدي وقتا أطول من يدكم لإعادة جوابا لا يعني أن يكون لديك خوارزمية أكثر كفاءة. 

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

ولكن لا يكون خائفا بعيدا عن تعريف رسمي. ماذا يعني هذا في الواقع في أقل الناحية النظرية؟ حسنا، انها في الاساس وسيلة لتحليل مدى سرعة وقت التشغيل برنامج ينمو مقارب. وهذا هو، ويبلغ حجم المدخلات الخاصة بك يزيد نحو اللانهاية، يقول، كنت الفرز مجموعة من حجم 1000 مقارنة مع مجموعة من حجم 10. كيف يمكن للوقت من برنامجك تنمو؟ على سبيل المثال، تخيل عد عدد من الشخصيات في سلسلة أبسط طريقة  من خلال السير السلسلة بأكملها الرسالة تلو الرسالة وإضافة 1 إلى عداد لكل حرف. ويقال هذه الخوارزمية لتشغيل في وقت الخطية مع الاحترام لعدد من الشخصيات، 'ن' في السلسلة. وباختصار، فإنه يعمل في O (N). لماذا هذا؟ حسنا، باستخدام هذا النهج، حسب الوقت اجتياز السلسلة بأكملها يتناسب مع عدد من الأحرف. حساب عدد الأحرف في سلسلة 20-حرف سوف يستغرق مرتين طالما أنه يأخذ لحساب الأحرف في سلسلة من 10 أحرف، لأنه لديك للنظر في جميع الشخصيات وكل حرف يأخذ نفس المقدار من الوقت للنظر في. كما يمكنك زيادة عدد الأحرف، وزيادة وقت التشغيل خطيا مع طول الإدخال. 

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

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

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

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

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

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

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

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

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

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

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

إذا كنت تعمل في خوارزمية O ² (ن)، أو ما هو أسوأ، وO (2 ⁿ) الخوارزمية، واحدة من أسرع أنواع متزايدة، عليك أن تبدأ حقا أن نلاحظ التباطؤ عند بدء العمل مع كميات كبيرة من البيانات. 

هذا التعقيد مقارب. شكرا.