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

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

الجمهور: ماري بيث. المتحدث: ماري بيث، وتأتي على ما يصل. اسمحوا لي أن الحصول الميكروفون لأنك هنا. لطيف لمقابلتك. 

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

الجمهور: أوه، هذا هو ذاهب الى اتخاذ إلى الأبد. 

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

المتحدث: وللمتعة، دعونا طرح جهاز توقيت. 

الجمهور: هذا القدر من المتعة، الكثير من المرح. 

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

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

الجمهور: نعم. 

المتحدث: حسنا، من A إلى Z. جميع الحق، تهنئة، يمكنك فعل ذلك. لديك اختيارك. الأزرق؟ كل الحق، شكرا لكم على ذلك. لذا لم تقترح ماري بيث ما كان نهجها، ولكن ما هو نهج آخر كيف قد يذهب حول فرز هذه الأشياء؟ ما الذي قمت به؟ أن الرقم القياسي للفوز كانت دقيقة واحدة و 50 ثانية أو نحو ذلك، بالإضافة إلى تلك التي كنت نسيت أن العد. ما الذي قمت به؟ نعم؟ الجمهور: خذ المكدس. نبدأ من البداية. تحقق أوراقك. وإذا كان رأس واحد هو أعلى من، ربما، هم، واحد القول هي أعلى، ثم التبديل بينها. 

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

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

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

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

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

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

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

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

[VIDEO قراءة] 

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

-Well-- 

-I صباحا آسف، maybe-- 

لا، لا، لا. أعتقد أن هذا النوع فقاعة سيكون بطريقة خاطئة للذهاب. 

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

-We've حصلت لدينا جواسيس في هناك. 

-OK، دعونا نسأل مختلفة سؤال في مقابلة. 

[END تشغيل الفيديو] 

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

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

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

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

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

ماذا لو كنت بدلا من ذلك تغيير القصة ليكون ليس عن فقاعة نوع، ولكن عن هذا الحد الأعلى. يمكنك التفكير في خوارزمية بعد أن قمنا نظرت بالفعل الذين العلوي، كحد أقصى قياس الوقت أو العمليات، سوف يقال ان يحدها بواسطة ن، وهي وظيفة الخطية، لا واحدة من الدرجة الثانية هذا المنحني؟ ما هو خوارزمية دائما لا تستغرق أكثر من مثل ن الخطوات، أو خطوات 2N، أو الخطوات 3N؟ نعم؟ 

الجمهور: العثور على أكبر رقم في القائمة؟ 

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

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

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

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

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

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

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

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

الجمهور: فقاعة نوع؟ 

المتحدث: يأخذ فقاعة نوع لك ن بمستوى الحد الأدنى الخطوات، لماذا؟ لماذا؟ لماذا يجب أن البداية وحتى يأتي لك حدسي، حتى لو لم يحدث ذلك فقط حتى الآن؟ نعم؟ 

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

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

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

الجمهور: Printf؟ المتحدث: ما هذا؟ الجمهور: Printf؟ المتحدث: Printf. حسنا، بالتأكيد. لذلك يأخذ عدد محدد من الخطوات. وأود أن now-- الآن أن نحن نتحدث عن رمز C وليس خدش، شيء مثل القول، مع printf، نحن يجب أن تبدأ في الحصول على الحذر. لأن printf لا تأخذ المدخلات، انها سلسلة، وسلاسل لا لها طول تقنيا. لذلك إذا كنا نريد الآن أن يلتقط عليك، إذا كنت لا تمانع، من الناحية الفنية يمكننا القول بأن printf لا تأخذ طول المدخلات متغير، وبالتأكيد قد يستغرق أكثر الوقت لطباعة سلسلة هذا الوقت الطويل، من هذا الوقت الطويل. 

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

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

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

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

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

الجمهور: ن المربعة. المتحدث: ن المربعة. لماذا؟ 

الجمهور: لأن لديك لتحديد (غير مسموع). 

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

ماذا عن نوع الإدراج، حيث أخذت الذين أعطيت، وبعد ذلك ساقط له أو لها في المكان المناسب؟ ثم مضيت إلى الشخص الثاني، ساقط له أو لها في المكان المناسب. ثم الشخص التالي، ساقط له أو لها في المكان المناسب. لاحظ أن هذا هو ذاته الخطية، إذا جاز التعبير. أنا خط مستقيم، وأنا لن ذهابا وإيابا، لم يسبق لي ان ننظر الى الوراء حقا، ولكن ماذا يحدث عندما أقوم بإدخال له أو لها في بداية قائمة كما فعلنا يوم الاثنين؟ ما الذي يحدث؟ نعم؟ الجمهور: [غير مسموع]. المتحدث: نعم، هذا كان الصيد، أليس كذلك؟ تذكرون من زملائك، إذا كانت تم إجراء أي حركة مع أقدامهم، وكان ذلك لعملية جراحية. حتى إذا كان هناك ثلاثة أشخاص هنا و الشخص الجديد ينتمي على الطريق هناك، على مرحلة طويلة مثل هذه، بالتأكيد، وقال انه أو أنها يمكن أن مجرد الذهاب الى النهاية. ولكن إذا نحن نفكر حول كمبيوتر ومجموعة من الذاكرة، هؤلاء الناس تسير لدينا لخلط ورق اللعب على لإفساح المجال لهذا الشخص. وبحيث ن ناقص 1 shufflings، ن ناقص 2 shufflings، ن ناقص 3 shufflings هي مجرد نوع من يجري ورائي، وليس أمامي كما كان من قبل، بمعنى ما. الآن بوصفها جانبا، وكما كنت قد شوهدت أون لاين إذا كنت تبدأ بدس حول حول أنواع، وهناك الكثير من مختلفة منها هناك، بعض منهم أفضل من غيرها. في الواقع، هي واحدة bogosort هذا هو نوع من المرح للبحث. Bogosort يأخذ مجموعة من أرقام أو القول سطح السفينة من البطاقات، المراوغات عشوائيا عليهم، و الشيكات لو انهم فرزها. وإذا لم يكن، يفعل ذلك مرة أخرى. وإذا لم يكن، يفعل ذلك مرة أخرى. إن لم يكن، يفعل ذلك مرة أخرى. غبي بشكل لا يصدق. 

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

الجمهور: بيتر. 

المتحدث: ما هذا؟ 

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

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

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

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

الجمهور: [غير مسموع] المتحدث: ما هذا؟ الجمهور: بواسطة حذوها. المتحدث: بواسطة حذوها. ذلك أنهم أولا تجميع كل من الماس معا على ما يبدو، كل من قلوب معا على ما يبدو، وهكذا دواليك، دون احترام لهذه الأرقام على بطاقات. والآن تظهر، على سبيل المثال، ليتم فرزها من حيث العدد. جيد جدا. 

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

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

[تصفيق] 

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

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

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

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

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

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

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

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

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

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

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

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

الجمهور: دارين. 

المتحدث: دان. وصعدت دان الأمام. 

الجمهور: دارين. المتحدث: دارين، وفعلت. قلت دارين أو دان؟ 

الجمهور: دارين. 

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

الجمهور: لوقا. 

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

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

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

الجمهور: ادريانو. 

المتحدث: ادريانو. يتم فرز ادريانو الآن. وما اسمك؟ 

الجمهور: أليكس. 

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

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

الجمهور: عمر. 

المتحدث: عمر، خطوة إلى الأمام، وفعلت. يتم فرز النصف الأيسر. وما اسمك؟ 

الجمهور: كريس. 

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

الجمهور: مارينا. 

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

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

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

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

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

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

الجمهور: سجل ن. 

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

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

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

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