كل الحق، لذلك، التعقيد الحسابي. فقط قليلا من تحذير قبل أن يغوص في far-- جدا وهذا ربما سوف يكون من بين أكثر الأشياء-الرياضيات الثقيلة نتحدث عن في CS50. نأمل أنها لن تكون ساحقة جدا وسنحاول وإرشادك من خلال هذه العملية، ولكن فقط قليلا من تحذير عادلة. هناك قليلا الرياضيات المعنية هنا. كل الحق، وذلك من أجل جعل استخدام الموارد الحاسوبية لدينا في world-- حقيقية انها حقا المهم أن نفهم الخوارزميات وكيف معالجة البيانات. إذا كان لدينا حقا خوارزمية فعالة، ونحن يمكن أن تقلل من كمية الموارد المتوفرة لدينا للتعامل معها. اذا كان لدينا خوارزمية هو ذاهب الى اتخاذ الكثير من العمل لمعالجة حقا مجموعة كبيرة من البيانات، انها سوف يتطلب أكثر والمزيد من الموارد، التي هو المال، RAM، كل هذا النوع من الاشياء. لذلك، أن تكون قادرة لتحليل الخوارزمية باستخدام هذه مجموعة أداة، في الأساس، يسأل question-- كيف هذا النطاق خوارزمية ونحن رمي المزيد والمزيد من البيانات في ذلك؟ في CS50، كمية البيانات نحن العمل مع صغير جدا. عموما، برامجنا تسير ليتم تشغيلها في الثانية أو less-- ربما أقل كثيرا ولا سيما في وقت مبكر. ولكن التفكير في شركة تتعامل مع مئات الملايين من العملاء. وأنها بحاجة إلى معالجة أن بيانات العملاء. حيث بلغ عدد العملاء أنهم لدينا يحصل على أكبر وأكبر، فإنه سيحتاج الى المزيد والمزيد من الموارد. كم عدد الموارد أكثر من ذلك؟ حسنا، هذا يعتمد على كيفية نحن تحليل الخوارزمية، باستخدام الأدوات في هذه الأدوات. عندما نتحدث عن تعقيد وalgorithm-- التي في بعض الأحيان عليك تسمعه يشار إلى الوقت تعقيد أو مساحة التعقيد لكننا ذاهبون فقط للاتصال complexity-- نحن نتحدث بشكل عام عن السيناريو الأسوأ. وبالنظر إلى أسوأ كومة المطلقة لل البيانات التي نحن يمكن رمي في ذلك، كيف يتم هذا خوارزمية الذهاب الى معالجة أو التعامل مع البيانات؟ نسميه عادة الأسوأ وقت التشغيل خوارزمية كبير-O. لذلك يمكن القول خوارزمية ل تشغيل في O ن أو O ن المربعة. وأكثر ما هذه يعني في الثانية. في بعض الأحيان، على الرغم من أننا نفعل الرعاية حول أفضل سيناريو. إذا كانت البيانات كل ما كنا نريد أن تكون وكانت مثالية تماما وكنا إرسال هذا الكمال مجموعة من البيانات من خلال أنظمتنا. كيف يمكن ان التعامل في هذه الحالة؟ نشير إلى أنه في بعض الأحيان كبير أوميغا، وذلك في تناقض مع كبير-O، لدينا كبير أوميغا. كبير أوميغا لأفضل سيناريو. كبير-O لسيناريو أسوأ الحالات. عموما، عندما نتحدث عن تعقيد خوارزمية، نحن نتحدث عن على اقصى تقدير. حتى أن تبقي في الاعتبار. وفي هذه الفئة، ونحن في طريقنا عموما لمغادرة تحليل دقيق جانبا. هناك العلوم والمجالات المكرسة لهذا النوع من الاشياء. عندما نتحدث عن المنطق من خلال خوارزميات، ونحن سوف نفعل قطعة تلو قطعة بالنسبة للكثيرين خوارزميات نتحدث عن في الصف. نحن حقا نتحدث فقط عن التفكير من خلال ذلك مع الحس السليم، ليس مع الصيغ، أو البراهين، أو أي شيء من هذا القبيل. لذلك لا تقلق، لن نكون تحول إلى فئة الرياضيات كبيرة. فقلت نحن نهتم التعقيد لأنه يسأل السؤال، كيف لا خوارزميات لدينا التعامل مع أكبر و مجموعات البيانات الكبيرة التي ألقيت عليهم. حسنا، ما هو مجموعة من البيانات؟ ماذا يعني عندما قلت ذلك؟ وهذا يعني كل ما يجعل معظم معنى في السياق، إلى أن نكون صادقين. إذا كان لدينا الخوارزمية، و عمليات Strings-- أننا على الأرجح الحديث عن حجم السلسلة. هذا هو البيانات set-- حجم وعدد من الحروف التي تشكل السلسلة. إذا كنا نتحدث عن وجود خوارزمية الذي يعالج الملفات، يمكن أن نتحدث عن كيفية وتشمل العديد من كيلو بايت هذا الملف. وهذا هو مجموعة البيانات. إذا كنا نتحدث عن خوارزمية الذي يعالج المصفوفات بشكل عام، مثل خوارزميات الفرز أو البحث الخوارزميات، نحن ربما نتحدث عن عدد من العناصر التي تتألف منها مجموعة. الآن، يمكننا قياس ل algorithm-- على وجه الخصوص، عندما أقول ما في وسعنا قياس خوارزمية، I يعني أننا يمكن قياس مدى العديد من الموارد يستغرق ما يصل. سواء كانت تلك الموارد هي، كم بايت من RAM-- أو ميغابايت من ذاكرة RAM التي يستخدمها. أو كم من الوقت يستغرق لتشغيل. ويمكننا أن نطلق على هذا قياس، تعسفا، و ن. حيث n هو عدد عناصر في مجموعة البيانات. وو ن هو عدد سمثينغس. كم عدد وحدات الموارد لا انها تتطلب لمعالجة تلك البيانات. الآن، نحن في الواقع لا يهمني حول ما و ن هو بالضبط. في الواقع، نحن نادرا جدا will-- بالتأكيد سوف أبدا في هذا I class-- الغوص في أي عمق حقا تحليل ما و ن هو. نحن ذاهبون لمجرد الحديث عن ما و ل ن تقريبا أو ما يميل إليه. وميل خوارزمية هو تمليه ولايته الدرجة الأولى. ويمكننا أن نرى ما يعني ذلك بأخذ نظرة على سبيل المثال أكثر واقعية. لذلك دعونا نقول أن لدينا ثلاثة خوارزميات مختلفة. أولها يأخذ ن مكعبة، وبعض وحدات الموارد لمعالجة مجموعة من البيانات من حجم ن. لدينا خوارزمية الثانية التي تأخذ ن مكعبة بالإضافة إلى الموارد ن التربيعية لمعالجة مجموعة من البيانات من حجم ن. ونحن لدينا ثلث الخوارزمية التي تدير in-- أن يستغرق فترة تصل ن ناقص مكعبة 8N تربيع بالإضافة إلى 20 ن وحدات الموارد لمعالجة خوارزمية مع مجموعة البيانات من حجم ن. الآن مرة أخرى، ونحن حقا لن للوصول الى هذا المستوى من التفصيل. أنا في الحقيقة مجرد لديك هذه حتى هنا كمثال على نقطة أنني ذاهب ليكون صنع في الثانية، والتي غير أننا نهتم حقا فقط إزاء اتجاه الأمور كما مجموعات البيانات تكبر. حتى إذا كانت مجموعة البيانات صغيرة، هناك في الواقع فرق كبير جدا في هذه الخوارزميات. الخوارزمية الثالثة هناك يأخذ 13 مرات أطول، 13 أضعاف كمية الموارد لتشغيل نسبة إلى أول واحد. إذا كانت البيانات لدينا هو حجم 10، والتي هو أكبر، ولكن ليس بالضرورة ضخمة، يمكننا أن نرى أن هناك في الواقع قليلا من الفرق. الخوارزمية الثالثة يصبح أكثر كفاءة. انها في الواقع عن 40٪ - أو 60٪ أكثر كفاءة. فإنه يأخذ 40٪ من مقدار الوقت. يمكن أن run-- يمكن أن يستغرق 400 وحدة الموارد لمعالجة مجموعة من البيانات من حجم 10. في حين أن الأول الخوارزمية، على النقيض من ذلك، يأخذ 1000 وحدة من الموارد لمعالجة مجموعة من البيانات من حجم 10. ولكن انظروا الى ما يحدث كما أعدادنا الحصول على أكبر. الآن، والفرق بين هذه الخوارزميات تبدأ لتصبح أقل قليلا وضوحا. والواقع أن هناك النظام أقل terms-- أو بالأحرى، حيث مع انخفاض exponents-- تبدأ لتصبح غير ذات صلة. إذا مجموعة البيانات من حجم 1000 والخوارزمية الأولى يعمل في مليار الخطوات. ويتم تشغيل الخوارزمية الثانية في مليون مليار والخطوات. ويتم تشغيل خوارزمية الثالثة في مقتربا من مليار الخطوات. انها الى حد كبير مليار الخطوات. هذه المصطلحات النظام أقل تبدأ لتصبح غير ذات صلة حقا. وفقط لحقا المطرقة منزل point-- إذا كان إدخال البيانات من حجم ل million-- كل ثلاثة من هذه بكثير جدا اتخاذ quintillion-- واحد إذا بلدي الرياضيات الخطوات correct-- لمعالجة البيانات المدخلة من حجم المليون. كما أن هناك العديد من الخطوات. وحقيقة أن واحدا منهم قد يستغرق بضع 100،000، أو زوجين 100 مليون حتى أقل عندما نحن نتحدث عن عدد أن big-- انها نوع من ذي صلة. أنهم جميعا تميل إلى اتخاذ n تقريبا مكعبة، ولذا فإننا سوف تشير في الواقع إلى كل من هذه الخوارزميات كما يجري بناء على أمر من ن مكعبة أو كبيرة O-ن مكعبة. وفيما يلي قائمة لبعض من أكثر دروس التعقيد الحسابي المشتركة أننا سوف تواجهها في الخوارزميات، عموما. وأيضا على وجه التحديد في CS50. يتم ترتيب هذه من عموما أسرع في القمة، لعموما أبطأ في الأسفل. لذلك خوارزميات وقت ثابت تميل ليكون أسرع، بغض النظر من حجم إدخال البيانات التي تمرر في. أنها دائما تأخذ عملية واحدة أو وحدة واحدة من الموارد للتعامل معها. قد يكون 2، أنه قد يكون 3، قد يكون 4. ولكن هذا رقم ثابت. أنها لا تختلف. خوارزميات الوقت لوغاريتمي هي أفضل قليلا. ومثال جيد حقا خوارزمية الوقت لوغاريتمي كنت قد رأيت بالتأكيد الآن هو تمزيق دفتر الهاتف للعثور على مايك سميث في دفتر الهاتف. نقطع مشكلة في النصف. وحتى ن يحصل على أكبر وأكبر وlarger-- في الواقع، في كل مرة كنت يتضاعف ن، إلا أنها تأخذ خطوة أخرى. ولهذا أفضل كثيرا من، مثلا، الزمن الخطي. وهو إذا كنت مضاعفة ن، فإنه يأخذ ضعف عدد من الخطوات. إذا كنت ثلاثة أضعاف ن، فإنه يأخذ ثلاثة أضعاف عدد من الخطوات. خطوة واحدة لكل وحدة. ثم الامور قليلا more-- أقل قليلا كبيرة من هناك. لديك الوقت الإيقاعي الخطي، وأحيانا دعا الزمن الخطي سجل أو مجرد ن ن تسجيل. وسنقوم مثال من خوارزمية يعمل في ن سجل ن، الذي لا يزال أفضل من الدرجة الثانية time-- ن تربيع. أو وقت متعدد الحدود، ن اثنين أي عدد أكبر من اثنين. أو الوقت المتسارع، الذي هو حتى worse-- C إلى ن. لذلك أثار بعض رقم ثابت ل قوة حجم المدخلات. حتى إذا كان هناك 1،000-- إذا كان إدخال البيانات من حجم 1000، ان الامر سيستغرق C إلى قوة 1،000th. انها أسوأ بكثير من الوقت متعدد الحدود. الوقت مضروب هو أسوأ من ذلك. وفي الواقع، هناك حقا توجد خوارزميات الوقت لانهائية، مثل ما يسمى sort-- الغباء الذي المهمة لخلط عشوائيا مجموعة ثم تحقق لمعرفة سواء كان تابعا لفرزها. وإذا لم تكن كذلك، بشكل عشوائي خلط مجموعة ثانية وتحقق لمعرفة ما إذا كان هو فرزها. وكما يمكنك ربما imagine-- يمكنك أن تتخيل الوضع حيث في أسوأ الحالات، أن الإرادة لم تبدأ فعلا مع مجموعة. ومن شأن ذلك أن خوارزمية تشغيل إلى الأبد. وبحيث يكون خوارزمية الوقت لانهائية. نأمل أن لا يكون الكتابة أي وقت مضروب أو لانهائية خوارزميات في CS50. لذلك، دعونا نلقي أكثر من ذلك بقليل نظرة ملموس في بعض بساطة دروس التعقيد الحسابي. لذلك لدينا example-- أو مثالين here-- خوارزميات الوقت ثابتة، والتي تأخذ دائما عملية واحدة في أسوأ الحالات. لذلك example-- أولا لدينا وظيفة دعا 4 بالنسبة لك، والتي يأخذ مجموعة من حجم 1000. ولكن بعد ذلك على ما يبدو لا تبدو في الواقع في it-- لا يهتم حقا ما هو داخل منه، من أن مجموعة. دائما يعود فقط أربعة. لذلك، أن الخوارزمية، على الرغم من حقيقة أنه يأخذ 1000 عناصر لا فعل أي شيء معهم. فقط يعود الأربعة. انها دائما خطوة واحدة. في الواقع، إضافة 2 nums-- التي رأيناه من قبل، كما well-- فقط العمليتين صحيحة. انها ليست خطوة واحدة. انها فعلا خطوات زوجين. تحصل على، تحصل ب، يمكنك إضافتها معا، وكنت إخراج النتائج. لذلك فمن 84 خطوات. لكنها دائما ثابتة، بغض النظر عن أو ب. لديك للحصول على، والحصول على ب، إضافة معا، خرج النتيجة. لذلك هذا هو خوارزمية الوقت ثابتة. وهنا مثال على خطي algorithm-- الوقت خوارزمية gets-- أن يأخذ خطوة إضافية واحدة، وربما، كما ينمو الدخل الخاص بك عن طريق 1. لذا، دعونا نقول نحن نبحث عن داخل عدد 5 من صفيف. قد يكون لديك الحالة التي تكون فيها يمكنك العثور عليها في وقت مبكر إلى حد ما. ولكن هل يمكن أن يكون أيضا الحالة التي يكون فيها ذلك قد يكون العنصر الأخير للصفيف. في مجموعة من حجم 5، إذا نحن نبحث عن العدد 5. ان الامر سيستغرق 5 خطوات. في واقع الأمر، تخيل أن هناك لا 5 في أي مكان في هذه المجموعة. لا يزال لدينا فعلا للنظر في كل عنصر واحد من مجموعة من أجل تحديد أم لا 5 هناك. حتى في أسوأ الحالات، وهو أن كان العنصر الأخير في الصفيف أو لا وجود لها على الإطلاق. سيظل علينا أن ننظر جميع العناصر ن. وحتى هذه الخوارزمية يعمل في الزمن الخطي. يمكنك التأكد من ذلك عن طريق استقراء قليلا قائلا: لو كان لدينا مجموعة 6-عنصر و كنا نبحث عن عدد 5، قد يستغرق 6 خطوات. اذا كان لدينا مجموعة 7-عنصر و نحن نبحث عن العدد 5. قد يستغرق 7 خطوات. ونحن نضيف عنصر واحد أكثر لدينا مجموعة، فإنه يأخذ خطوة أخرى. هذا خوارزمية خطية في أسوأ الحالات. زوجان أسئلة سريعة بالنسبة لك. ما هو runtime-- ما أسوأ الحالات وقت هذا مقتطف معين من التعليمات البرمجية؟ لذلك ليس لدي حلقة 4 هنا أن يدير من ي يساوي 0، وصولا إلى m. وما اراه هنا، هو أن الجسم من الحلقة يعمل في وقت ثابت. وذلك باستخدام المصطلحات التي لقد تحدثنا بالفعل about-- ما سيكون الأسوأ وقت التشغيل لهذه الخوارزمية؟ تأخذ ثانية. الجزء الداخلي من الحلقة يعمل في وقت ثابت. والجزء الخارجي لل حلقة يتم الانتقال إلى تشغيل الأوقات م. إذن ما هو وقت الأسوأ هنا؟ هل تخمين كبير O-من م؟ كنت على حق. ماذا عن بعضها البعض؟ هذه المرة لدينا حلقة داخل حلقة. لدينا حلقة الخارجي تنطلق من صفر إلى ص. ونحن لدينا حلقة الداخلية التي تدير من صفر إلى p، وداخل تلك، أذكر أن الجسم حلقة تشغيله في وقت ثابت. إذن ما هو وقت الأسوأ هذا مقتطف معين من التعليمات البرمجية؟ حسنا، مرة أخرى، لدينا الحلقة الخارجي الذي يمتد الأوقات ص. وكل التكرار time-- تلك الحلقة، إلى حد ما. لدينا حلقة داخلية الذي يعمل أيضا أوقات ص. ثم داخل ذلك، هناك ل ثابت قصاصة صغيرة time-- هناك. حتى إذا كان لدينا حلقة الخارجي الذي يدير الأوقات ص الداخل والتي هي حلقة الداخلية التي يدير ص times-- ما هو أسوأ الحالات وقت هذا مقتطف من التعليمات البرمجية؟ هل تخمين كبير O-من ص التربيعية؟ أنا دوغ ويد. هذا هو CS50.