[پخش موسیقی] 

دیوید J. مالان: همه حق. بنابراین خوش آمدید. این CS50 است، و پایان سه هفته. 

بنابراین در چند هفته گذشته به یاد بیاورید، ما صرف کرده ایم بسیار کمی از زمان در C، برنامه نویسی، در نحو. و این کاملا طبیعی است، اگر شما هنوز هم هستیم مبارزه با مشکل تنظیم 2، به کوبیدن سر خود را در برابر دیوار. این پیغام خطا مرموز، به دنبال و اشکالات است که شما کاملا نمی تواند تعقیب کردن. از آنجا که، مطمئن است که در تنها زمان چند هفته شما نگاه به عقب چیزهایی مانند سزار، و [؟ V-genair،،؟] شاید حتی کراک و متوجه که چقدر شما آمده ام در یک دوره کوتاه از زمان. بنابراین در صورتی که هر تسلی، آویزان در آن وجود دارد در حال حاضر. 

امروز، هر چند، ما شروع به انتقال به چیزهایی سطح بالاتر. و ما شروع به را برای مسلم است که شما بچه ها می دانند که چگونه به برنامه، و یا در کم آغاز که سطح راحتی. و ما شروع می کنیم به نظر چگونه ما می توانیم در مورد طراحی برنامه های بیشتر به طور موثر. چگونه ما می توانیم در مورد بهینه سازی بهره وری از الگوریتم های ما، و به طور کلی حل بیشتر مشکلات جالب توجه است. و شروع به گرفتن برای مسلم است که، اگر ما می خواستیم، ما می تواند تا هر کد از نمونه های ما در ذهن داریم. بنابراین، امروز، ما از صفحه کلید را لمس نمی کند برای هر فرم از کد. این خواهید بود سطح بسیار بالاتر، و در نهایت، در مورد حل مسئله. 

بنابراین برای رسیدن به آن نقطه، اجازه دهید به من پیشنهاد که هفت زیر مستطیل نشان دهنده هفت درب، در پشت که یک دسته کامل از اعداد، که در میان آن عدد 50 است. اجازه دهید من این پروژه در این صفحه نمایش در اینجا نیز. و پیشنهاد می کنند که ما نیاز به یک داوطلب کمک به پیدا کردن من در مقابل برای دیدن اینترنت در اینجا. بیا بالا، در صورتی است. بسیار خوب. نام شما چیست؟ 

جنیفر: [نامفهوم] 

دیوید J. مالان: با عرض پوزش؟ 

جنیفر: جنیفر. 

دیوید J. مالان: جنیفر. همه حق است، جنیفر. از ملاقات شما خوشبختم. بیا بالا. بنابراین این در اینجا هفت درب، و آنچه من می خواهم به شما برای ما انجام می دهید در اینجا، در مقابل همه از همکلاسی های شما، به ما پیدا کردن تعداد، 50. برای پیدا کردن یک شماره، شما می توانید زیرچشمی نگاه کردن در پشت هر یک از این درها به سادگی با بهره برداری در یکی از درها، و آن را شماره آن را فاش کند. و بیایید ببینید که چگونه به سرعت شما می توانید با ما تعداد، 50 پیدا کنید. 

15. 16. 50. سادگی انجام می شود. بسیار خوب. دور از تشویق جنیفر. 

[تشویق حضار] 

بسیار خوب. پس چه استراتژی خود را برای پیدا کردن شماره، 50؟ 

جنیفر: ام، من شاید اگر فکر - [نامفهوم] 

دیوید J. مالان: آه. آن یک ثانیه. بنابراین استراتژی خود را برای پیدا کردن شماره، 50؟ 

از JENNIFER: بنابراین من فقط در شروع شروع به دیدن چه عدد اول بود، و سپس من فکر کردم، شاید اگر آنها طبقه بندی شده اند، من فقط می خواهید نگه دارید بهره برداری بالاتر؟ 

دیوید J. مالان: OK. و ما به نظر می رسد پیدا کرده اند که به صورت. اگر چه، بیایید پوست پشت لایه فقط کمی، و شما می خواهید به آن بروید به جلو و فاش کردن درب دیگر شما می توانید از را انتخاب کرده اند؟ 

جنیفر: اوه، عزیزم. 

دیوید J. مالان: آه. 

جنیفر: بنابراین من فقط خوش شانس. 

دیوید J. مالان: بنابراین شما خوش شانس. بسیار خوب. خیلی بد نیست. اما این جالب است بینش، درست است؟ اگر شما به عهده گرفت، و شما را دریافت کنید، در واقع، کمی خوش شانس وجود دارد. اما اگر شما فرض شده است که اعداد طبقه بندی شده اند، می تواند به شما دقیق تر چگونه است که تحت تاثیر قرار رفتار شما؟ 

جنیفر: بنابراین اگر آنها طبقه بندی شده اند، من فکر کردم شاید کوچکترین تا بزرگترین. 

دیوید J. مالان: OK. 

جنیفر: در صورتی که این پایان رسید تا اینکه واقعا بزرگ، پس از بزرگ به کوچک. 

دیوید J. مالان: OK. پس بزرگ به کوچک، یا کوچک و بزرگ. اما اجازه دهید به من پیشنهاد، فرض کنید شما تا به حال و بعد فورا رفت واز بدشانسی، و فرض کنید که آنها شد، در واقع، طبقه بندی شده اند، که چگونه بسیاری از این درب ها ممکن است شما را به زیرچشمی نگاه کردن پشت در که بدترین حالت؟ 

جنیفر: همه آنها. 

دیوید J. مالان: همه آنها. بنابراین تعمیم دهید که به عنوان نفر. اتفاق می افتد به 7 وجود دارد، اما بیایید بیشتر به طور کلی می گویند درب n در وجود دارد صفحه نمایش در اینجا. بنابراین در بدترین حالت، شما می توانید به پشت 7 درب، یا N درب نگاه کنید. و بنابراین این در واقع، آن را کمی امروز شانس، اما آن واقعا یک خطی الگوریتم از انواع، حتی اگر شما نوع پرش در اطراف. آیا این عادلانه است؟ 

جنیفر: آره. 

دیوید J. مالان: خوب، اجازه دهید من را ببینید اگر شما تغییر استراتژی اگر من ما را به حرکت مثال دوم ما در اینجا با 7 درب های متفاوت. اعداد مشابه، اما این زمان آنها طبقه بندی شده اند. استراتژی خود را در اینجا رفتن به چه، تلاش برای قرار دادن از ذهن شما را چه شماره های دیگر بود - 

جنیفر: OK. 

دیوید J. مالان: - زودتر؟ 

جنیفر: شروع میکنم با یکی از اولین. 

دیوید J. مالان: همه حق. شروع با یکی از اولین. 4. که در آن شما برای رفتن، و چرا؟ 

جنیفر: 4 واقعا کوچک است. بنابراین اگر آنها در حال مرتب سازی بر شاید کوچکترین به بزرگترین، باید آن را دو برابر، و -. 

دیوید J. مالان: OK. بیایید ببینید که شما فکر می کنم؟ 

جنیفر: سعی کنید یکی از آخرین. خوب است. 

دیوید J. مالان بسیار خوبی انجام شده است. بسیار خوب. 

[تشویق حضار] 

دیوید J. مالان: OK. بنابراین شما در واقع انجام این کار به طرز وحشیانه ای، به خاطر شما انجام آن بسیار خوب است. که برگ ما را به قادر ایجاد نقطه خاص. بنابراین سعی کنید به عقب در اینجا اجازه دهید. 

جنیفر: OK. 

دیوید J. مالان: خیلی خوب انجام می شود، با این وجود. بنابراین شما در ابتدا آغاز شده است، شما را دیدم که 4 بود، پس از آن شما به پایان نقل مکان کرد. اما فرض کنید شما خوش شانس نیست وجود دارد، و فرض کنید 50 در جایی دیگر بود. مرحله سوم خود شده اند؟ 

جنیفر: بازگشت به آغاز است. 

دیوید J. مالان: بازگشت به آغاز. خوب، پس شما را لمس کردی این درها، که 8 بود. بسیار خوب. به طوری که 50 نیست. به کجا می خواهد شما را نگاه کرد؟ 

جنیفر: اگر من این کار را نکرد می دانم که آنها طبقه بندی شده اند. 

دیوید J. مالان: درسته. خوب، اگر شما نمی دانستید آنها طبقه بندی شده اند - 

جنیفر: آه، آیا می دانید، آره. 

دیوید J. مالان: - اما تو می دانم هنوز که در آن 50 بود؟ 

جنیفر: فقط رفتن نگه دارید. 

دیوید J. مالان: همه حق. OK را بزنید. رفتن ادامه دهید. خوب، که من می توانم با کار می کنند. 

جنیفر: OK. 

دیوید J. مالان: در حال حاضر، اگر شما فقط هستید رفتن به رفتن ادامه دهید، چه خود را الگوریتم واگذاری به حمایت می شود. 

جنیفر: خطی -. 

دیوید J. مالان: این نوع خطی است. اما اجازه دهید به من پیشنهاد من در نقطه ای قرار داده است. اجازه دهید من تازه کردن صفحه. تعداد مشابه، تنظیم، درب های همان. اما فکر می کنم به آن روز برای اولین بار در کلاس زمانی که ما یک دفترچه تلفن در پاره نیمه، مرتب کردن، و چه شد استراتژی ما وجود دارد؟ 

جنیفر: شروع در وسط. 

دیوید J. مالان: OK. بنابراین در عمق دفاع حریف شروع می شود. پس بیایید جلو بروید و شبیه سازی است که. شروع به در از وسط آشکار است که درب. بنابراین عدد 16. پس آنچه را که مرد قوی انجام داده اند، که دفترچه تلفن در نیمه پاره، برای رسیدن به حدس بعدی؟ 

جنیفر: برو در این نیمه. 

دیوید J. مالان: و چرا به سمت راست؟ 

جنیفر: اگر آنها بودند مرتب کردن بر اساس کوچکترین به بزرگترین، و سپس 50 باید در آن پایان. 

دیوید J. مالان: خوب. کاملا معقول است. بنابراین مانند دفترچه تلفن، شما را به حق به عنوان مخالف به سمت چپ است، اما در اینجا غذای آماده کلیدی این است که. شما هم اکنون می توانید دور انداختن، و یا پاره کردن، نیمی از این مشکل، شما را ترک نمی کنم با 7 درب، اما در واقع تنها با 3. است که تقریبا نیمی از اندازه مشکل است. بسیار خوب. بنابراین در حال حاضر آنچه که شما می توانید انجام می شود بعد از اینکه شما به سمت راست؟ 

جنیفر: بنابراین 16 است که هنوز هم بسیار کوچک است، نسبت به 50، تا شاید من را امتحان کنید، مانند، این یکی. 

دیوید J. مالان: همه حق. 42. همه حق است، بنابراین در حال حاضر آنچه که خود را غریزه به شما گفتن؟ 

از JENNIFER: من می توانم دور انداختن و سپس فقط - 

دیوید J. مالان: OK. خوب، شما می توانید دور انداختن نیمه سمت چپ وجود دارد. 

جنیفر: - انتخاب کنید این یکی. 

دیوید J. مالان و سمت راست. 

جنیفر: آره. 

دیوید J. مالان: بنابراین حتی اگر آن را سخت برای دیدن شاید، زمانی که تنها وجود دارد 7 درب، در مورد فکر می کنم، در حال حاضر، قوام الگوریتم شما فقط اعمال می شود. در مورد قبلی، شما خوش شانس، که فوق العاده بود. اما شما با استفاده از روش اکتشافی، من می خواهم بگویم. شما با استفاده از مرتب کردن بر اساس غرایز خود را و دانستن آن طبقه بندی شده اند، اگر آن را بسیار در ابتدا کوچک، بدیهی است، ما کردم برای رفتن بیشتر به سمت راست. اما در بعضی جهات، شما خوش شانس، چرا که شاید این عدد 100 بود، و شاید 50 بیشتر در عمق دفاع حریف بود. شاید 50 حتی بیش از اینجا بود. 

اما آنچه که شما کمی متفاوت این زمان بود، شما هم همین دوباره و دوباره. و من استدلال می کنند که آنچه که شما فقط انجام داد، البته توسط گوشی را تحت تاثیر خود قرار داده کتاب عنوان مثال، چیزی بسیار است الگوریتمی تر، و خیلی کمتر خاص سربار. بسیار کمتر غریزی. بنابراین در پایان روز، چگونه می بهره وری از الگوریتم اول، که در آن شما رفت از چپ به راست، در مقابل الگوریتم دوم در اینجا؟ 

جنیفر: این یکی باید، مانند، شاید نصف زمان، و یا حتی بیشتر، آره. 

دیوید J. مالان: خوب، شاید حتی بیشتر. اجازه دهید فشار کمی سخت تر بر روی آن است. واقعا چه، اگر ما این روند ادامه منطق، ما قطعا نصف زمان در حال اجرا با این الگوریتم دوم با دور انداختن نیمی از اعداد، اما آنچه که ما در آینده انجام دهید تکرار، زمانی که جنیفر نشان داد عدد دوم؟ 

ما دوباره تعداد درب ها نصف شده است. و پس از آن چه ما پس از آن انجام دهید، اگر درهای بیشتر برای بازی کردن با وجود دارد؟ ما می خواهیم آنها را دو نصف کردن، و دوباره و دوباره، و دوباره. و این درست مثل شما بچه ها تمام شد ایستاده در هفته اول کلاس، نیمی از شما نشسته، نیمی از شما نشسته، نیمی از شما نشسته، تا زمانی که یک تنها روح ایستاده بود. و گفتیم که زمان در حال اجرا از آن، تعدادی از مراحل آن را در زمان در نظم از چه؟ 

SPEAKER 1: [نامفهوم] 

دیوید J. مالان: پس ورود به سیستم پایه 2 از n، و یا فقط به سادگی، از n وارد شوید. بنابراین چیزی لگاریتمی. و نمودار یک خط راست نیست که فقط بدتر و بدتر، آن را این منحنی جالب است که این کار را نکرد خیلی بد در طول زمان است. بنابراین به این ایده نگه دارید اجازه دهید. اجازه تشکر جنیفر. با تشکر بسیار برای آمدن در بالا. و یک ثانیه. بدون لامپ میز، اما ما لازم CS50 توپ استرس. 

جنیفر: عالیست. 

دیوید J. مالان: بسیار خوب، در اینجا. با تشکر از شما برای تحمیل استرس در اینجا. بسیار خوب. بنابراین اجازه دهید را ببینید اگر ما می توانیم نه در حال حاضر رسمی این کمی بیشتر. تا دوباره، چیزی است که ما فقط این بود اساسا همان چیزی است که ما انجام داد که در هفته اول. اما به جای پایان تنها با یک خطی الگوریتم، که ما به تصویر کشیده قبلا به عنوان این خط مستقیم، به موجب آن، اگر ما یک درب در صفحه نمایش، پس از آن جنیفر داشته اند به نگاه، به طور بالقوه، پشت درب. اگر ما دو درب دیگر، او ممکن است به نگاه پشت دو درب. 

و بنابراین، این خطی وجود دارد رابطه بین اندازه مشکل، می گویند، محور x، و مدت زمانی که طول می کشد تا حل Y. اما تصویر من اشاره به در اوایل این خط سبز بود. سبز به عمد، زیرا آن را فقط احساس بهتر است. در تئوری، الگوریتم، زمانی که ما این کار را کرد با دفترچه تلفن، هنگامی که ما این کار را کرد با شما بچه ها شمارش هر یک از دیگر، و در حالت دوم، زمانی که جنیفر تنها این کار را کرد تا در اینجا، این نوع بود اساسا بهتر است. به دلیل آن بود فقط دو بار به عنوان سریع نیست. این بود که حتی چهار برابر سریع نیست. آن را به طور کامل وابسته به چه اندازه ورودی، که چگونه بسیاری از مراحل آن را در نهایت در زمان. 

و بنابراین این ایده ساده است که همه ما در زمان برای مسلم با دفترچه تلفن، به همین ترتیب می تواند استفاده شود به چیزی شبیه به این. و این ممکن است خودمانی تر شناخته شده به عنوان، همانطور که شما ممکن تصور کنید، تقسیم و تسخیر. نه بر خلاف چیزی است که ما انجام داد، البته، با دفترچه تلفن. 

اما شبه، به یاد می آورند، این بود. بنابراین ما این کار را انجام نمی دوباره، اما به یاد که هفته ی اول، همه ما ایستاد و پس از آن نیمی از شما نشست، نیمی از شما نشسته، نیمی از شما نشستم. این الگوریتم در یک اجرا شد کمی از راه تقلب در آن، فقط یکی از من نیست با شمارش، اساسا، موثر تر است. در آن صورت، من به اعمال نفوذ منابع ثانویه. مرتب کردن بر اساس پردازنده های چندگانه ها، مغز چندگانه، مردم هوشمند متعدد در اتاق کمک بودند من از چیزی دریافت کنید خطی به چیزی لگاریتمی، از چیزی قرمز به چیزی سبز. 

اما در این مورد، جنیفر به تنهایی می تواند اساسا بر بهبود عملکرد الگوریتم اول خود را، دوباره، فقط فکر کمی سخت تر است. و در حال حاضر، هنگامی که آن زمان به اجرا در می آید این چیزها را بدانند چه خط کد شما می توانید از جمله ارسال که شما می توانید آنها را دوباره تکرار و دوباره و دوباره مرتب کردن بر اساس در مد حلقه. از آنجا که شما نمی خواهید به لوکس، مانند جنیفر در اول، فقط باید یک دسته کامل از IFS و می گویند، HMM، اگر این اولین عدد 4 است، به من اجازه رفتن به تمام راه را به پایان. آه، اگر این تعداد بیش از حد بزرگ است، به من اجازه حرکت خودسرانه به عنصر دوم. شما باید دریابید که آن را به مقدار زیادی سخت تر به رسمی چیزی است که ما انسان را برای اعطا به عنوان بسیار مناسب فن آوری هوشمند، اما یک کامپیوتر تنها رفتن به آنچه که شما آن را به انجام. 

در حال حاضر این بسیار جالب است مفاهیم. این گراف مرتب سازی بر اساس به منظور مرتب سازی بر اساس را پایمال بصری، اما توجه کنید، جایی که خط مستقیم در این گراف است؟ نمودار خطی از کجا است که ما تماس بگیرید N؟ خوب، آن را به سمت پایین مرتب سازی بر اساس این تصویر، درست است؟ بنابراین برای همه ما انجام داده ایم این است که ما نوعی از ام به محور x ها و بزرگنمایی محور y را به تلاش برای رسیدن به معنایی از آنچه انواع دیگر منحنی مانند نگاه کنند. 

و جزئیات ریاضی عبارات امروز نمی خواهد مهم زیاد است، اما توجه کنید که در بسیاری از وجود دارد الگوریتم های که به مراتب بدتر از چیزی که خطی. در واقع، N نبات به نظر می رسد بسیار بد است. 2 نفر به نظر می رسد بسیار بد است. N مربع به نظر می رسد بسیار بد است. و خواهیم دید چه برخی از کسانی که ممکن است در واقعیت امروز می شود. و Log N به عنوان بد احساس نمی کند، اما بهتر از n ورود به سیستم پایه 2 از n است. اما شما می دانید، آن را حتی شده است شگفت انگیز تر اگر جنیفر، و یا اگر ما، که در هفته اول، آمده بود چیزی است که ورود به سیستم ورود به سیستم از n. 

بنابراین به عبارت دیگر، این کل وجود دارد طیف وسیعی از راه حل های احتمالی مشکلات، اما حتی در اینجا، توجه چه اتفاقی خواهد افتاد. وقتی که من زوم کردن، که از این منحنی ها رفتن به اثبات می شود مطلق بدتر از آنهایی که بر روی صفحه نمایش در حال حاضر؟ بنابراین N نبات به نظر می رسد بسیار در حال حاضر بد. اما اگر ما زوم کنید و ببینید که بیشتر از x و محور y، چه کسی تسلط در نهایت؟ بنابراین آن را در واقع معلوم است که 2 به n و شما می توانید این را فقط با شکل متصل کردن در برخی به طور فزاینده ای بزرگ اعداد، و شما خواهید دید که 2 به نفر، در واقع، بزرگتر می شود بسیار سریعتر است. اگر ما واقعا زوم، 2 N الگوریتم کاملا بمکد. منظور من این است که رفتن را بسیار کمی از زمان برای کامپیوتر از طریق دائما و شدیدا چیزی را تکان دادن و بم زدن. 

اما شما در طول زمان، به ویژه با مجموعه مسائل آینده و حتی پروژه های نهایی، اطلاعات خود را مجموعه ای بزرگ می شود، همه درست است؟ حتی در اولین نسخه از فیس بوک، به عنوان تعدادی از دوستان و تعداد کاربران ثبت نام شده بزرگ، شما می توانید از تلفن آن در مرتب کردن و اجرای چیزی با جستجوی خطی، و یا یک دسته بندی بسیار ساده الگوریتم، همانطور که ما امروز خواهید دید. شما باید برای شروع به فکر کردن سخت تر و سخت تر در مورد این مشکلات. و انواع از مشکلات مکان های مانند فیس بوک و گوگل، و مایکروسافت، و دیگران در کار است دقیقا این مرتب سازی بر اساس مرتب کردن بر اساس داده های بزرگ از سوالات به طور فزاینده ای این روزها. 

بسیار خوب. بنابراین موفقیت جنیفر در آن دوم الگوریتم، رک و پوست کنده، او شگفت آور اولین بار، اما اجازه نوشتن آن را به عنوان شانس به طوری که ما می توانید این نقطه را. در مورد دوم، او قوی تر الگوریتمی که دوباره تکرار و دوباره، اما او در زمان برای اعطا برخی از فرض است که ما اجازه او، اما او سوء استفاده برخی از جزئیات بار دوم که او ندارد اولین بار. که چی بود؟ 

که این لیست طبقه بندی شده اند. تا در اسرع وقت لیست طبقه بندی شده اند، ما ادعا می کنند که قادر به انجام جنیفر بود اساسا بهتر است. 7 درب، بله است، که جالب نیست، اما فرض کنید آن ما 7 میلیون درب هستیم. ورود از n است که قطعا رفتن برای انجام خیلی، خیلی سریع تر در دراز مدت. اما او تا به حال به درها را برای او طبقه بندی شده اند. در حال حاضر، من در زمان آزادی برای انجام این کار در پیش بر روی صفحه نمایش کامپیوتر در اینجا، اما فرض کنید که جنیفر تا به حال انجام است که خودش؟ فرض کنید که درب در سوال اطلاعات ارائه شده در یک پایگاه داده، یا دوستان ثبت نام برای فیس بوک، و یا هر صفحه وب بر روی اینترنت است که وب سایت های مختلف ممکن است نیاز به شاخص یا جستجو بیش از. 

فرض کنید که شما فقط به حال داده های خام تعیین و آن را به شما باقی مانده بود، و یا به جنیفر به انجام این کار مرتب سازی؟ که، نه، مستلزم آن است که ما پاسخ سوال، که خب، چقدر زمان جنیفر، و یا حتی، گرفته شده مرتب کردن بر اساس تعداد کسانی که در پیشبرد به طوری که او می تواند استفاده از آن را؟ درست است؟ از آنجا که مفهوم، البته، اگر آن را به من طول می کشد در حالی که کاملا به مرتب کردن بر اساس اعداد، که هک مراقبت که شما می توانید تعدادی مثل 50 خیلی سریع پیدا کنید، همانطور که در مورد جنیفر، اگر ما بیش از با غرق مقدار از زمان کل آن را با مرتب سازی بر چیز در پیش گرفت؟ 

بنابراین اجازه دهید ببینیم که اگر ما نمی توانیم رنگ تصویر اینجا را کلیک کنید. من یک دسته کامل بیشتر استرس توپ، در صورتی که کمک می کند شکستن یخ به اینجا. و اگر شما نمی خواهد ذهن ما نیاز به هفت داوطلب - ، OK. وای. بنابراین ما مجبور به صرف در لامپ میز، به نظر می رسد. بسیار خوب. پس چگونه در مورد شما دو نفر در مقابل. چگونه در مورد شما دو نفر را در پشت. به طوری که چهار است. چگونه در مورد شما را در مقابل پنج، شش و هفت. سمت راست وجود دارد. دوست شما به شما اشاره، بنابراین این جایزه را دریافت کنید. 

بسیار خوب. بیا بالا. و چرا ما به شما بچه ها در اینجا آمده است. من قصد دارم برای شما هر تعداد می دهد. و جلو بروید و خودتان را ترتیب عینا به چه نشان داده شده بر روی صفحه نمایش. 

[صدای INTERPOSING] 

دیوید J. مالان: OOP، متاسفم. اشکال. بسیار خوب. خب، در اینجا ما بروید. شماره پنج. شماره شش. یک، دو، سه، چهار، پنج، شش، هفت. آه، این بی دست و پا است. 

SPEAKER 2: من فقط گرفتن -. 

دیوید J. مالان: معامله خوب است. بسیار خوب. با تشکر از شما برای شرکت در. 

[تشویق حضار] 

OK را بزنید. بسیار خوب. بنابراین ما باید چهار، دو، شش، یک، سه، هفت، پنج. بنابراین ما باید کامل هفت داوطلب اینجا که برابر عرض آرایه ای که ما در حال بازی با قبل از آن است. و من هفت به دلایل انتخاب خواهد شد که فقط مناسب در کمی. و من قصد دارم به پیشنهاد اول که ما به این هفت داوطلب مرتب سازی بر اساس. اگر شما می خواهم برای اولین بار، برای گفتن سلام هر چند. از آنجایی که این رفتن به چند دقیقه بی دست و پا. معرفی خودتان. 

GRACE: سلام، من گریس هستم. من دانشجوی سال دوم در خانه Leverett هستم. 

برانسون: سلام. من برانسون هستم. من دانشجوی سال اول در جوش هستم. 

گیب: سلام. من گیب هستم. من یک تازه وارد در کابوت هستم. 

نیل: من نیل. من دانشجوی سال اول در ماتیوز هستم. 

JASON: من جیسون هستم. من سال اول Greenough هستم. 

مایک: من مایک هستم. من دانشجوی سال اول در Grays در هستم. 

JESS: من جس هستم. من دوم در Leverett هستم. 

دیوید J. مالان: عالی. بسیار خوب. خوب، با تشکر از شما برای همه ما داوطلبان در اینجا تا کنون. و چالش در دست، در حال حاضر در حال رفتن به به مرتب کردن بر اساس از این بچه ها، اما بعد از آن ما قصد داریم که به فکر می کنم کمی سخت در مورد چگونه موثر ما در واقع آنها طبقه بندی شده اند. بنابراین اجازه دهید برای اولین بار این را امتحان کنید. شما بچه ها می توانید شماره های همدیگر را ببینند فقط با قرار دادن در اطراف گوشه. برو جلو و گرفتن چند ثانیه، و مرتب سازی بر خودتان از کوچکترین در سمت راست به بزرگترین باقی مانده است. برو. 

OK را بزنید. خوب است. که به سرعت واقعا رفو بود. در حال حاضر کسی در اینجا، چه الگوریتم که این بچه ها اعمال می شود؟ 

SPEAKER 1: کمترین به بیشترین. 

دیوید J. مالان: OK. کمترین به بیشترین واقعا مرتب سازی بر اساس هدف، اما من مطمئن هستم که نیستم واقعا یک الگوریتم. حداقل به بزرگترین اختصاص بگویم که من گام به گام چه باید بکنید. آره؟ 

SPEAKER 1: [نامفهوم] 

دیوید J. مالان: OK. بنابراین اگر شما یک شخص کوچکتر از شماره شما، پس از آن به حرکت حق از آنها است. به طوری که در حال حاضر گرفتن رسا تر است، بیشتر شبیه به یک الگوریتم، دلیل این که شما می توان گفت، در صورتی که این، پس از آن که. بنابراین ما باید به نوعی از سازه مشروط. و این بچه ها به نظر می رسید برای انجام این کار چند بار، چرا که برخی از شما نقل مکان کرد کمی از راه دور. پس احتمالا نوعی وجود دارد حلقه در ذهن خود. 

اما اجازه دهید سعی کنید به رسمی که. اگر شما بچه ها می تواند تنظیم مجدد به این ترتیب. بیایید ببینیم آیا می توانیم رسمی این کمی، و سپس سوال بپرسید، فقط چگونه کارآمد است؟ البته، هنگامی که ما این کار را آهسته تر، آن را به احساس خوب الگوریتم، اما بیایید ببینید که اگر ما می توانیم قرار دادن انگشتان دست خود را در مراحل دقیق. 

بنابراین شما دو بچه چهار و دو است. یا شما سفارش درست یا نادرست؟ بدیهی است که اشتباه است. بنابراین ما عوض میکنه. حالا من قصد دارم به حرکت در کنار در اینجا و می گویند، چهار تا شش. آیا شما درست یا نادرست؟ 

گیب: درسته. 

دیوید J. مالان: درسته. شش و یک؟ نه. تعویض. به طوری که دو سواپ. شش و سه؟ نه. تعویض. شش و هفت؟ به نظر می رسد خوب است. هفت و پنج؟ 

JESS: [نامفهوم] 

دیوید J. مالان: خوب، مبادله. و طبقه بندی شده اند. بسیار خوب. بنابراین بدیهی است، درست است؟ بنابراین وجود رفتن بیشتر شد. اما، در واقع، این بچه ها، حتی فقط به طور غریزی. به حرکت. آنها نه تنها متوقف، زمانی که آنها اصلاح یک مشکل. است. در واقع، من قصد دارم به برای انجام کار مشابه. من قصد دارم که به نوعی عقب برگشت به ابتدای این مشکل، یا شروع این آرایه مردم، بیایید شروع به خواندن آنها. 

و در حال حاضر چه باید الگوریتم من با کلیک بر روی پاس دوم باشد؟ 

SPEAKER 1: همین. 

دیوید J. مالان: همین. و این، من شروع به دوست، درست است؟ به محض این که شما می توانید خودتان را انجام همان چیزی که دوباره و دوباره، که تبدیل شدن بیشتر مانند یک الگوریتم، و غریزه انسان است. 

بنابراین در حال حاضر، در اینجا ما دوباره بروید. دو و چهار؟ شماره چهار و یک؟ ق، در واقع وجود دارد برخی از هنوز کارهای که باید انجام شود. و سه؟ خوب است. چهار و شش؟ شش و پنج؟ شش و هفت؟ خوب، در حال حاضر، انجام می شود. خوب، نه. من باید به عقب برگردید. 

بنابراین در حال حاضر، دوباره، ما در حال انجام این کار کمی بیشتر به عمد. و در حال حاضر، تنها یک مغز وجود دارد اجرای این الگوریتم است. یک CPU، اگر شما خواهد شد. و رک و پوست کنده، که تنها منبع ما قصد داریم به دسترسی به. و هنگامی که ما به عقب برویم به یک صفحه کلید و چیزی شبیه به C در ما به دفع، ما در حال نوشتن یک برنامه است که می تواند یک چیز در یک زمان انجام دهد. در حالی که، این بچه ها یک لحظه پیش، ما قوی تر قدرت مغز شمرد جمعی خود مثل شما بچه ها در هفته صفر انجام داد. بنابراین اجازه انجام این کار. 

دو و یک است. دو و سه. سه و چهار. چهار و پنج. پنج و شش. شش و هفت. انجام می شود؟ بنابراین من هستم، اما اجازه دهید من بازی مدافع شیطان است. آیا من، مرتب کردن بر اساس کامپیوتر که فقط پاس از طریق این مجموعه ای از ساخته شده است مردم، بدانید که من انجام داده ام؟ 

SPEAKER 1: شماره 

دیوید J. مالان: پس چرا؟ چه خواهد بود من را مجبور به انجام به منظور نتیجه گیری قاطع که من انجام داده؟ احتمالا یک پاس. درست است؟ از آنجا که همه من از آن قبلی پاس این است که من اشتباه اصلاح شده است. و این بدان معناست، شاید وجود دارد هنوز هم یکی دیگر از اشتباه که من نیاز به اصلاح. بنابراین من فقط می تواند مطمئن باشد روندنج و پس از چک کردن یک یا دو، دو و سه، سه و چهار، چهار و پنج، پنج و شش، شش و هفت. خوب، در حال حاضر من هیچ کار. 

من قطعا می تواند به یاد داشته باشید که من هیچ کار با چیزی شبیه به یک متغیر، مانند یک int. تماس با آن معاوضه، و اگر معاوضه 0 بار من است در اینجا، و آن را در 0 آغاز شده، سپس من فقط می احمقانه به رفتن ادامه دهید به جلو و عقب، چک کردن دوباره، و دوباره و دوباره، درست است؟ از آنجا که شما در برخی گیر کرده است نوع حلقه بی نهایت. تا در اسرع وقت 0 سواپ، وجود دارد ما می توانیم که این ادعا الگوریتم در واقع کامل است. 

در حال حاضر، اجازه دهید یک نام را بر این قرار داده است. الگوریتمی که ما پیشنهاد می کنم فقط پیاده سازی شده است چیزی به نام حباب مرتب کردن، شناخته شده به عنوان مثل به این معنا که اعداد است که نوع بزرگتر از حباب راه خود را به بالا، و یا تا به انتهای آرایه ای از اعداد است. اما این الگوریتم چگونه موثر بود؟ چگونه بسیاری از مراحل من فیزیکی به را، برای مثال، به مرتب کردن بر اساس این هفت انسان؟ 

چهار تا پنج؟ خوب، بیش از حد بسیاری از است که در نهایت رفتن به پاسخ. اما حتی پس از آن، با شماره های خاص خیلی جالب نیست. اجازه دهید آن را به عنوان نفر تعمیم. بنابراین اگر من مردم تا به حال نفر در اینجا، و آنها ، مرتب کردن بر اساس، در صورت تصادفی در آغاز، در آن منظور اصلی. خوب، چگونه بسیاری از مراحل من در پاس اول را؟ این یک، دو، سه، چهار، پنج، شش، و آنها هفت نفر هستید، پس که هفت، شش -، به طوری که N منهای یک مراحل اولین بار. 

در حال حاضر، که چگونه بسیاری از مراحل من را به زمانی که من عقب؟ خب، ما در واقع می تواند دو برابر است که اگر ما واقعا می خواستم، اما در حال حاضر، من فقط رفتن به می گویند، همه حق است، دیگر منهای 1. بنابراین N منهای 1 رفتن به آزار دهنده برای پیگیری، پس بیایید فقط دور تا کمی. پس 2N مرحله. پس 14 قدم، دادن یا گرفتن. 

چند بار من را یک گام از دفعه بعد؟ خوب، آن را 3N. واقعا. و در حال حاضر، در بدترین حالت، برای به عنوان مثال، چند بار به من رفته عقب و جلو، عقب و جلو، اجرای این الگوریتم، مبادله مردم در هر پاس، تقریبا؟ این در واقع نفر مربع، درست است؟ 

از آنجا که در بدترین حالت، شما می توانید نوع فکر می کنم در این مورد به طور مستقیم، حتی اگر آن را ممکن است کمی طول می کشد کمی از زمان غرق شوید. در بدترین حالت، چه این هفت نفر مانند، نگاه در نظر از آرایش از تعداد آنها؟ به طور کامل به عقب، درست است؟ و فقط به شبیه سازی آن، نام خود را دوباره بود؟ 

MIKE: مایک. 

دیوید J. مالان: مایک؟ خوب، مایک، می تواند شما را فقط به من بیش از اینجا فقط برای یک ثانیه؟ در واقع، نه. متاسفم مایک، عقب بیایید. نام شما چیست؟ دوباره؟ 

نیل نیل. 

دیوید J. مالان: نیل. خوب، نیل، شما با من، اگر برای شما مهم نیست. بنابراین من قصد دارم برای پیشنهاد، فقط برای سادگی، که نیل در حال حاضر در خود بدترین حالت ممکن است. اما به یاد من اجرا الگوریتم من. من مقایسه، مقایسه، مقایسه، مقایسه، مقایسه، آه. در حال حاضر این بچه ها نظم، بنابراین من ثابت. بنابراین شما بچه ها مبادله. اما در نظر گرفتن حال حاضر، چقدر دورتر نیل به آن بروید؟ این تقریبا N. شما می دانید، آن را در واقع نفر نیست. آن را مانند است، تعداد n منهای 1، اما من گرفتن اذیت پیگیری از کمی تعداد، بنابراین اجازه دهید فقط آن را نفر. 

بنابراین اگر نیل حرکت یک گام به حداکثر هر زمان، و برای move 

نمایش دوباره و تجزیه و تحلیل نیل یکی گام، من را به این پاس واقعا خسته کننده عقب و جلو، این است که تقریبا انجام این کار، مراحل نفر، در مجموع از n بار، به دلیل آن را به من که بسیاری از مراحل را برای نیل تمام راه به جایی که او به آن تعلق دارد. اجازه دهید به تنهایی هر کس دیگری اگر شما بچه ها همه اشتباه دستور داده نیز هست. 

پس مرتب سازی حباب نفر مربع تماس بگیرید اجازه دهید. زمان اجرای این الگوریتم، عملکرد این الگوریتم، بهره وری از این الگوریتم، ما فقط باید بیشتر توصیف به طور کلی به عنوان مربع. کدام خوب است، چون من می تواند انجام دهد همان مثال با هشت نفر، نه مردم، یک میلیون نفر، و پاسخ نمی خواهید را تغییر دهید. 

بنابراین اگر شما بچه ها نمی خواهد ذهن، بیایید شما به جایی که شما شروع به تنظیم مجدد. و اجازه دهید سعی می کنید دو روش دیگر و ببینید اگر ما اساسا نمی تواند انجام دهد بهتر از این. بنابراین این زمان، من قصد دارم به پیشنهاد مرتب کردن بر اساس الگوریتم های مختلف. که بسیار هوشمندانه از ما بود در زمان گذشته، و شما بچه ها حق به غرایز راست فقط نوع از مبادله دو به دو. اما اگر من واقعا می خواستم به این روش به سادگی، و هدف من این است که حرکت همه از تعداد کمی از این راه، و فشار همه از اعداد بزرگ است که راه، چرا که من فقط می توانم که در ساده و بی تکلف ترین راه ممکن است و اگر من می تواند بهتر از آنچه بود الگوریتم نسبتا پیچیده؟ 

بنابراین اجازه دهید را ببینید. چهار عدد بسیار کوچک است، بنابراین من رفتن به شما ترک وجود دارد لحظه ای است. آه، شماره دو است و حتی بهتر است. بنابراین می تواند به شما قدم به جلو برای یک لحظه؟ این در حال حاضر کوچکترین شماره من نامزد، و من قصد دارم به خاطر داشته باشید که با، دوست، یک متغیر است. اما من قصد دارم برای نگه داشتن چک کردن. آیا کسی که وجود ندارد عدد کوچکتر است؟ شش، نه. آه، دوباره نیل وجود دارد. 

بنابراین من قصد دارم به شما عقب براند مرتب کردن بر اساس مفهومی. نیل به جلو خواهد آمد. و در حال حاضر، متغیر است که من با استفاده از پیگیری که کوچکترین تعداد به روز شده است شامل محل نیل. خوب، اجازه دهید را ببینید. سه، هفت، پنج. خوب، من می دانم که نیل کوچک بود. ساده ترین چیز چیست برای من در حال حاضر؟ من قصد ندارم وقت من به هدر فقط حباب نیل یک نقطه به سمت چپ. چرا من فقط با قرار دادن نیل جایی که او تعلق دارد، است که البته که در آن؟ 

تمام راه را در آغاز راه است. بنابراین نیل، با من آمده است. و نام خود را دوباره بود؟ 

GRACE: گریس. 

دیوید J. مالان: گریس. OK را بزنید. بنابراین گریس، متاسفانه، شما نوع در راه. پس چگونه می توانم این مشکل را حل کنیم؟ درست است؟ اگر این آرایه است، وجود دارد تنها هفت مکان. به یاد بیاورید که با راب، ما در مورد صحبت اعلام سنین، و ما فقط تا به حال تعداد متناهی از سنین؟ ایده در اینجا همان. ما فقط یک تعداد متناهی از نوع داده int است. گریس نوع ما راه، پس چگونه این مشکل را حل کنیم؟ 

ساده ترین راه این است که مانند، گریس، متاسفم. شما در حال رفتن به به بیش از وجود دارد، بنابراین ما می توانیم اتاق. در حال حاضر، اگر شما در این مورد فکر می کنم، شاید ما فقط مشکل را بدتر. و شاید ما انجام داد، چون چه می شود اگر گریس در جای مناسب بود؟ اما ما می دانیم او نیست، زیرا در غیر این صورت، او می شده اند به جای ایستادن به جلو نیل در این زمان، درست است؟ ما در حال حاضر بررسی تعداد خود را. 

بسیار خوب. بنابراین در حال حاضر، نیل را در جای مناسب، و من می توانم یک بهینه سازی جزئی انجام دهد. برای دقیقه بعد، من قصد دارم به چشم پوشی از نیل همه با هم، بنابراین نه به اتلاف وقت خود را، و یا به طور تصادفی مبادله او را به محل اشتباه. بنابراین در حال حاضر، چگونه می توانم پیدا کنم عنصری است که کوچکترین؟ دو. که تعداد بسیار خوب، اگر شما می خواهید به قدم به جلو و من شما را به یاد داشته باشید. شش، خوب. چهار، سه، هفت، پنج، خوب. پس اجازه دهید من شما را به حرکت جای مناسب خود را. و ما فقط خوش شانس در این زمان. 

در حال حاضر، من قصد دارم برای نادیده گرفتن این دو بچه، و در حال حاضر یکی بیشتر انجام دهد عبور از طریق این. شش که تعداد خیلی کوچک است. بیا جلو. اوه، ببخشید. تعداد گریس بهتر است، بنابراین گام رو به جلو. چهار. با عرض پوزش، گریس. بازگشت دوباره. شماره سه بهتر است. هفت. پنج. و در حال حاضر آنچه نام خود را دوباره؟ 

JASON: جیسون. 

دیوید J. مالان: جیسون. بنابراین جیسون در حال حاضر کوچکترین عنصر من را انتخاب کردید. او کجا برای رفتن؟ تا جایی که شش است. و نام خود را دوباره؟ 

گیب: گیب. 

دیوید J. مالان: گیب. گیب در راه است. ساده ترین چیزی که برای انجام چه خبر؟ تعویض این دو بچه و ادامه خواهد داد. بنابراین در حال حاضر اجازه دهید را ببینید. چه کسی کوچکترین؟ چهار. اجازه بدهید من فقط نوع از تقلب. پنج در حال رفتن به کوچکترین. پیدا کردن من بعد، اگر شما می خواهید به گام رو به جلو، آنچه را می توانم باید با این بچه ها، با گیب؟ دوباره تعویض. بنابراین در حال حاضر، هنوز هم کمی خارج از دستور. که من پیدا کردم گیب به کوچکترین، بنابراین من به او بپره، بچه ها شما حرکت. و انجام می شود. 

پس جواب همان است. نتیجه نهایی همان است. کدام یک از این دو الگوریتم بهتر است؟ دوم، من شنیده ام. چرا؟ 

SPEAKER 3: ازت گام [نامفهوم]. 

دیوید J. مالان: این مراحل نفر در اکثر. جالب است. پس از آن چند؟ پس چگونه من کوچکترین عنصر؟ چگونه بسیاری از مراحل من را به پیدا کردن کوچکترین عنصر؟ من تا به حال یک نگاه تمام راه در پایان، درست است؟ از آنجا که در بدترین حالت، چه اگر نیل بودند که اینجا هستید؟ پس فقط پیدا کردن کوچکترین عنصر من نفر مراحل، یا n منهای 1 طول می کشد. اما، خوب. بنابراین نیل را حل کنند. به یاد داشته باشید که، یک دقیقه یا بیشتر پیش. 

اما چگونه بعد از پیدا کردن من کوچکترین عنصر؟ این نفر، منهای 1، یا n منهای 2 واقعا، از تعداد مراحل. بنابراین OK. بنابراین من منهای 2 نفر بود. بسیار خوب. به طوری که احساس می کند کمی بهتر است. بسیار خوب. دفعه بعد چند مرحله برای پیدا کردن شماره سه؟ بنابراین N منهای 4. پس از آن کاهش یابد، یکی کمتر قدم در هر تکرار. بنابراین این احساس بهتر، درست است؟ اگر در زمان گذشته آن تقریبا n بار N، این بار آن را N منهای 1، به علاوه نفر منفی 2، به علاوه N منهای 3، به علاوه N منهای 4، نقطه، نقطه، نقطه. اما اگر شما از دبیرستان خود را به یاد کتاب های درسی، تقلب کوچک ورق در پشت است که فرمول، اگر اضافه کردن این سری از اعداد، تعداد کل مراحل رفتن به این باشد که من در اینجا؟ 

این یکی از آن، مثل، نفر منهای است 1 بار N، تقسیم بر 2. بنابراین من را ببینید اگر من می توانید بکشید این برای فقط یک لحظه. و دوباره، من نوع گرد کردن برخی از هستم اعداد فقط برای حفظ زندگی ما ساده است، اما من به یاد، آن را چیزی شبیه به اگر من N منهای 1 چیز، سپس n منهای 2، پس از N منهای 3، تقریبا چیزی شبیه به این بیش از 2، و اگر من تکثیر این، که N مربع واقع. این احساس نه چندان خوب. N منهای نفر بیش از 2. 

اما در اینجا چیزی نیست. در علم کامپیوتر، زمانی که مشکلات شروع به گرفتن جالب است وقتی N می شود واقعا بزرگ است. و هنگامی که نفر می شود واقعا بزرگ است، که از این ارزش ها در حال رفتن به تسلط همه از دیگران؟ این نوع نفر مربع است، درست است؟ بله، تقسیم بر 2 بسیار خوب است. اما اگر شما در حال صحبت کردن راجع به میلیاردها قطعه از داده ها، یا تریلیون قطعه از داده ها، بسیار خوب، پس شما دو برابر سریع. اما چه کسی واقعا مراقبت در صورتی که عدد بزرگ، در صورتی که این عامل همان چیزی است که می شود بزرگتر و بزرگتر. و مسلما، آن را می سازد بیشتر از تفاوت نسبت به این پسر. بنابراین حتی اگر شما بچه ها هستند، الگوریتم دوم، ما به آن تماس بگیرید مرتب کردن بر اساس انتخاب، است، در دنیای واقعی، کمی سریعتر بالقوه، چون من هستم مصرف کمتر و کمتر مراحل در هر زمان. 

این واقعا اساسا سریعتر نیست. از آنجا که اگر ما در واقع این بازی برای مقادیر زیادی از n، در پایان روز، برای n های به اندازه کافی بزرگ، آن را هنوز هم رفتن به احساس بسیار آهسته است. خوب، اجازه دهید من یک آخرین پاس که در آن. این چیزی است که من می خواهم تماس بگیرید مرتب سازی بر اساس انتخاب. می تواند به شما بچه ها تنظیم مجدد خودتان آخرین بار؟ و در این مورد آخر، من قصد دارم برای پیشنهاد کاری نام مرتب سازی بر درج شده است. مرتب سازی بر درج، مفهومی، کمی متفاوت است. 

به جای رفتن به جلو و عقب و انتخاب کوچکترین عنصر، من فقط رفتن برای مقابله با هر یک از این بچه ها که من آنها روبرو می شوند، و قرار دادن آنها را به محل صحیح خود. بنابراین من فقط رفتن با گریس را آغاز کنید، و من می بینم که او شماره چهار است. شماره چهار در کجا تعلق دارند؟ من را شروع کرده اند نیست مرتب سازی بر هر چیزی، بنابراین گریس می شود به ماندن در سمت راست وجود دارد. و در حال حاضر من رفتن به ادعا می کنند، اگر شما می توانید را یک گام به سمت راست خود را، این لیست طبقه بندی شده اند من، این است که من لیست باقی مانده نامرتب. بنابراین در حال حاضر من قصد دارم برای ادامه بعدی، و نام خود را دوباره؟ 

برانسون: برانسون 

دیوید J. مالان: برانسون. در برانسون شماره دو است. بنابراین من قصد دارم تا شما را از برای یک لحظه. و در حال حاضر، که در آن به شما تعلق در این آرایه؟ پس به حق گریس. پس دوباره، نوع ساخت گریس انجام بسیاری از کار در اینجا. کجا ما شما را قرار داده است؟ بنابراین ما قصد داریم به شما اسلاید به اسلاید را ترک کرد و وارد برانسون وجود دارد. اما در حال حاضر من ادعا می کنند که شما بچه ها انجام می شود. اما توجه کنید، من با استفاده از فضای اضافی نیست. این هنوز 2 عناصر در اینجا، 5 بیش از اینجا. حجم کلی آرایه 7 است، بنابراین من تقلب نیست، همه درست است؟ 

بنابراین در حال حاضر ما باید با گیب در اینجا، شماره شش، جایی که می توانم به شما تعلق دارند؟ شما خوش شانس دوباره. بنابراین شما می توانید به ماندن در سمت راست وجود دارد. فقط یک گام کمی به سمت راست فقط به روشن است که شما طبقه بندی شده اند. و در حال حاضر ما نیل دوباره، تعداد یک، کجا می روی؟ و در حال حاضر جایی است که ما شروع به دیدن که این الگوریتم، هر چند در اولین نگاه، احساس بسیار هوشمند، تماشای آنچه که مورد اتفاق می افتد. اگر شما می توانید به جلو گام. 

کجا ما می خواهیم برای قرار دادن نیل؟ بنابراین بدیهی است که در اینجا، پس چگونه ما نیل وجود دارد؟ بیایید این کار را گام به گام. گیب، که در آن شما نیاز به رفتن؟ جهت مشاهده فرم خرید، بنابراین یک گام بزرگ را، یا دو نیم گام برای رسیدن به یک قدم بیش از وجود دارد. گریس، جایی که شما بروید؟ خوب است. بنابراین گام دیگری. و در نهایت، برانسون؟ یکی دیگر از گام. و در حال حاضر ما می توانیم نیل به محل قرار داده است. 

بنابراین در حال حاضر، ادامه این منطق. حتی اگر ما در حال تغییر نیل بیش از، و بیش و بیش، به او قرار داده جایی که او می رود، در بدترین حالت، عدد بعدی ما ممکن است روبرو می شوند می تواند می شود که در تعداد، می گویند، یک عدد وجود دارد صفر، پس از آن ما در حال رفتن به تغییر همه این بچه ها. فرض کنید که یک عدد باشد، منفی وجود دارد یک، پس از آن ما مجبور به تغییر همه از این بچه ها. بنابراین ما واقعا فقط نوع از کوه در می رم مشکل در اطراف، به طوری که ما انتقال هزینه ها از فرآیند انتخاب به طوری درج فرایند، به طوری که شما بچه ها فقط به حال به حرکت تقریبا N منهای چیزی تعداد مرحله انجام شد. و که تعداد گام است تنها رفتن به افزایش که من را انتخاب کنید اعداد بیشتر، اگر من باید برای نگه داشتن تنه زدن شما بچه ها پشت، و پشت، و پشت. 

بنابراین چیزی غم انگیز در حال حاضر است همه از این الگوریتم مربع N. بیایید جلو بروید و با تشکر از این بچه ها، و تجسم این بیت متفاوت است. خیلی خوب انجام می شود. 

[تشویق حضار] 

بسیار خوب. شما بروید وجود دارد. با تشکر - 

برانسون: [نامفهوم] حفظ اعداد. 

دیوید J. مالان: نه، شما ممکن است نگه داشتن اعداد نیز هست. بسیار خوب. سادگی انجام می شود. بسیار خوب. بنابراین اجازه دهید ببینیم اگر ما در حال حاضر نمی تواند خلاصه با سرعت بیشتر، و بصری، دقیقا همان چیزی است که فقط اتفاق افتاده در اینجا به عنوان شرح زیر است. من قصد دارم به پیش بروید و بالا بکشد فایرفاکس. ما این تظاهرات را لینک کنید در وب سایت درس. جاوا است کمی آزار دهنده است به کار گرفتن در برخی مرورگرهای این روزها. بنابراین اگر شما با این بازی در خانه، متوجه شما ممکن است نیاز به استفاده از فایرفاکس می توانید آن را کار. و آنچه که من قصد دارم با این تظاهرات شرح زیر است. 

در پایین، من یک دسته کامل از گزینه های منو، از جمله شروع و دکمه را متوقف کند. همچنین، به عنوان یک کنار، به نظر می رسد وجود دارد اشکال در این برنامه، به موجب آن شما در واقع نمی تواند شروع و یا متوقف کردن را فشار دهید مگر اینکه شما فرماندهی یا Alt را نگه دارید plus و زوم، که جالب به شما نشان می دهد که دکمه های بیشتر است. پس فقط FYI اگر شما بازی با این در خانه. حالا من قصد دارم با کلیک بر روی شروع را فقط در لحظه، پس از تعیین تاخیر، مانند، 200 میلی ثانیه در اینجا، فقط بنابراین ما می توانید ببینید که چه اتفاقی می افتد. 

بنابراین من ادعا می کنند که این تجسم الگوریتم اول این بچه ها، مرتب سازی حبابی، به موجب آن ما مردم جفت عاقلانه عوض میکنه. بینش کلیدی این تجسم این است که ارتفاع میله ها نشان دهنده اندازه تعداد. بنابراین نوار بلندتر، بزرگتر تعداد. نوارهای کوتاه تر، کوچکتر تعداد. و اگر شما متوجه است، ما قصد داریم از طریق تکرار برای اولین بار از این الگوریتم، مبادله اعداد بزرگ و کوچک، به طوری که تعداد کمی می آید اولین و تعداد بزرگ می رود به سمت راست. 

و در اسرع وقت ما به پایان آرایه تعداد بسیاری از بیش از هفت، ما رفتن به بازگشت به آغاز است. و پیش بینی این. در سمت چپ، که پسر کوچک در رفتن به مبادله و به سمت، و این تکرار روند. در حال حاضر این تجسم به سرعت می شود خسته کننده است، بنابراین اجازه دهید من جلو بروید و توقف آن، بسیار تغییر چیزی تاخیر سریعتر فقط به در حال حاضر، یک احساس برای این الگوریتم. 

بنابراین حتی اگر من آن توپ رو کرده ام، این است که مانند ارتقاء پردازنده من، خرید یک کامپیوتر جدید. من اساسا تغییر نکرده است من الگوریتم، اما شما می توانید در واقع بیشتر ببینید به وضوح در مقایسه با انسان، که بزرگ اعداد حباب به بالا، و اعداد کوچک به حباب به پایین. و در حال حاضر این چیزی که در اینجا طبقه بندی شده اند. و به عنوان یک کنار، در میادین وجود دارد، فقط برخی از حسابداری وجود دارد کمک به شما تعداد دفعات مشاهده چگونه بسیاری از مقایسه، و یا چگونه بسیاری از سواپ در واقع انجام شده است. 

خوب، اجازه دهید یکی از سعی دیگران ما را دیدم. اجازه دهید من در مرتب سازی حبابی اینجا را کلیک کنید و اجازه دهید من را انتخاب کنید، و این کل صفحه وب کمی حشره دار است. اجازه دهید این خطر را قبول و دوباره آن را اجرا کنید. گرامی می رویم. بنابراین اجازه انجام مرتب سازی بر اساس انتخاب. من نمی دانم که چرا منو به نظر می رسد بیش از وجود دارد. بیایید زوم برای رفع آن اشکال، این را به 50 تغییر دهید. آه، اجازه دهید در واقع انجام که بسیار سریعتر. پنج میلی ثانیه یا بیشتر، و شروع می شود. 

بنابراین این نوع انتخاب شده است. تا دوباره، در مورد آنچه که ما فکر می کنم با انسان در اینجا انجام داد. ما را از طریق آرایه رفت و بعد از انتخابات کوچکترین عنصر دوباره، و دوباره، و دوباره. حالا من ادعا می کنند که هنوز هم خیلی بد بود. هنوز نفر مربع، دادن و یا گرفتن، اما آن، در دنیای واقعی، کمی سریع تر، چون من در واقع مصرف شد کمی کمتر مراحل در هر زمان. اما ما در حال صحبت کردن در چه؟ شاید 40 یا میله در اینجا؟ ما در حال صحبت کردن نیست 40 میلیون. پس از آن نه کاملا برای من روشن است که افزایش معنی دار بود در واقع. 

اجازه دهید من در حال حاضر به عقب رفتن و تغییر به ما الگوریتم سوم بود، که انتخاب کنید مرتب سازی بر درج. و در حال حاضر آن را واقعا حشره دار است زیرا منو واقعا نباید پایین وجود دارد. بنابراین در حال حاضر ما در اینجا حرکت خواهیم کرد و شروع این الگوریتم. فریاد، شروع و متوقف شود. بنابراین این یک نوع از یک الگوی زیبا به آن، به موجب آن ما دوباره قرار دادن انسان ها، و یا در این مورد، میله های زندان به محل مناسب خود. و آن را قبل از انجام من به اطراف تبدیل شده است. اما این یکی، بیش از حد، در تئوری، هنوز هم نفر مربع. 

بنابراین اجازه دهید ببینیم اگر ما نمی توانیم به طور خلاصه این به شرح زیر است. من قصد دارم به جلو بروید و فقط به دادن ما نوعی از یک روش مشترک برای صحبت کردن در مورد این چیزها، اجازه دهید به من معرفی فقط یک کمی از نماد در اینجا. شما در مورد چیزی به نام بزرگ هستیم O، دلیل آن است که به معنای واقعی کلمه بزرگ O. و این راهی است که یک کامپیوتر می باشد دانشمند یا یک ریاضیدان حتی با استفاده از برای توصیف زمان در حال اجرا برخی از الگوریتم. چگونه بسیاری از مراحل آن را در واقع می برد؟ 

حالا من قصد دارم به خودم شرمسار با دست خط من در اینجا فقط یک لحظه. اما اجازه دهید من جلو بروید و می گویند که این خواهد بود که O بزرگ بیش از اینجا. و اجازه دهید معرفی کنم یکی دیگر نماد امگا سرمایه. امگا است برای رفتن به مخالف، در اصل، از O. بزرگ در حالی که بزرگ O یعنی، در بدترین حالت، چقدر زمان ممکن است برخی از الگوریتم را در از نظر N، امگا در حال رفتن به چقدر زمان ممکن است آن را را در بهترین حالت. و خواهیم دید که آنچه ما به این معنی بهترین حالت فقط یک لحظه. 

بنابراین شروع به چیزی ساده بگذارید. اجازه دهید من با یک جستجوی خطی شروع. بنابراین مرتب سازی نیست. ما این جستجو خطی را خواهید تماس بگیرید. و در حال حاضر، را کمی جدول از این. و در حال حاضر، در مورد جستجوی خطی، در بدترین حالت، که چگونه بسیاری از مراحل است آن به من را برای پیدا کردن یک تعداد انتخاب دلخواه؟ و در کل درب های N وجود دارد یا n تعداد کل. بدترین حالت. چگونه بسیاری از مراحل من رفتن به را به عدد 50 در آرایه از N درب؟ و چرا؟ از آنجا که ممکن است همه راه را بر روی پایان. بنابراین بسیار شبیه جنیفر مواجه می شوند، شماره 50 بود تمام راه را بیش از، به طوری که در بدترین حالت جستجوی خطی بزرگ O از N، ما می گویم. 

چه در مورد بهترین حالت، اگر شما واقعا خوش شانس؟ این فقط رفتن به یک قدم، و یا یک عدد ثابت مرحله انجام شد. بنابراین ما به عنوان 1 توصیف است. بنابراین این بسیار خوب است. در حال حاضر آنچه اگر ما کاری انجام دادند مانند جستجوی دودویی؟ بنابراین جستجو دودویی، در بدترین مورد، در زمان چه مقدار زمان؟ 

[صدای INTERPOSING] 

دیوید J. مالان: پس در واقع، من آن را در مکان های زن و شوهر شنیده می شود. بنابراین آن را در واقع وارد بخش مدیریت شوید، N، دادن و یا گرفتن، چرا که همانطور که ما تقسیم لیست به نصف دوباره و دوباره، و دوباره، ما قادر خواهیم بود برای پیدا کردن، در نهایت، ارزش، اگر آن وجود دارد، اما گرفتن وجود دارد. این فرض که ما باید به چه را برای جستجوی دودویی اعطا شده؟ این است که باید طبقه بندی شده اند. این طبقه بندی شده اند نیست، شما می توانید چیزی تقسیم می در نیمه دوباره و دوباره، و شما می تواند به سمت چپ بروید، و شما می توانید بروید و شما می توانید چپ و راست بروید، اما شما قصد ندارم به پیدا کردن عنصر اگر لیست طبقه بندی شده اند نیست، زیرا شما ممکن است آن را از دست. از آنجا که اکتشافی خود را برای رفتن به سمت چپ یا راست رفتن به ناقص می شود اگر آن را در واقع طبقه بندی شده اند نیست. بنابراین مرتب کردن بر اساس هزینه های پنهان وجود دارد با استفاده از چیزی شبیه به این. 

در حال حاضر، اجازه دهید به مرتب سازی ما الگوریتم های جستجو - آه، در واقع اجازه دهید در این خالی. جستجو دودویی در بهترین حالت؟ این هم 1 اگر آن را فقط اتفاق می افتد در وسط آرایه، یا وسط دفترچه تلفن. حالا اجازه دهید انجام مرتب سازی حبابی. بنابراین دوباره، در حال حاضر ما در حال ورود به انواع، نه جستجوها. 

در بدترین حالت، که چگونه بسیاری از مراحل ما ادعای مرتب سازی بر حباب رفتن را به؟ N مربع. بنابراین من قصد دارم آن را به منظور جلب. آه، دست خط من به نظر می رسد حتی بدتر هنگامی که آن را پیش بینی که بزرگ است. بسیار خوب. به طوری که ازت مربع. و در بهترین حالت از مرتب سازی حبابی، چگونه بسیاری از مراحل آن را رفتن به گرفتن؟ 1، من شنیده ام. 

SPEAKER 1: N. 

دیوید J. مالان: N، من شنیده ام. 

SPEAKER 1: 2. 

دیوید J. مالان: 2، من شنیده ام. آیا 3 من می شنوم؟ بسیار خوب. بنابراین من شنیده ام 1، نفر، 2، اما بیایید انتخاب کنید جدا حداقل برای اولین بار از آن پیشنهادات، 1. این یک غریزه بد نیست، زیرا نوع زیر یک الگوی در اینجا. اما اگر آن را تنها طول می کشد 1 گام، چگونه در جهان می تواند ادعا کنم که این لیست طبقه بندی شده اند، چرا که اگر من تنها مجاز را به مرحله 1، که چگونه بسیاری از عناصر من در واقع چک کنید تا مطمئن شوید؟ خوب، فقط 1، که به معنی وجود ازت منهای 1 عنصر است که می تواند از نظم، و من فقط رفتن در ایمان پس از دنبال در 1 عنصر که چیزی که طبقه بندی شده اند. بنابراین 1 در اینجا درست نیست. تا حداقل، که چگونه بسیاری از لازم به نگاه؟ 

[صدای INTERPOSING] 

دیوید J. مالان: N منهای 1، یا در واقع، N، چون من نیاز به در هر نگاه عنصر مطمئن شوید که آن را خارج از دستور نیست. اما باز هم، ما را از موج ما مرتب سازی بر اساس دست در اعداد کوچکتر و فرض کنیم که، به عنوان نفر می شود بزرگ، آنها علاقه به هر حال. به طوری که مرتب سازی حبابی است. و در حال حاضر، اجازه دهید این کار را دو. مرتب کردن بر اساس انتخاب، و پس از آن خواهیم انجام مرتب سازی بر درج. و پس از آن ما خواهد شد خود را منفجر ذهن با چیزی بسیار بهتر از همه این است. بسیار خوب. 

بدترین حالت در حال اجرا است زمان مرتب سازی بر انتخاب؟ 

SPEAKER 4: N مربع. 

دیوید J. مالان: نفر مربع، دارم می شنوم. اما چرا نفر مربع، به طور ذاتی است؟ 

SPEAKER 4: از آنجا که ما فقط آن را انجام داد. 

دیوید J. مالان: از آنجا که ما فقط آن را انجام داد. OK را بزنید. خوب جواب. اما به طور مستقیم، به همین دلیل انتخاب شده است مرتب سازی بر اساس N مربع؟ چیزی که ما را به انجام دوباره و دوباره؟ ما تا به حال به نگه داشتن از طریق اسکن، شما کوچکترین، شما کوچکترین، کوچکترین شما. و اعطا شده، ما قادر به گرفتن N مراحل، سپس n منهای 1، سپس n منهای 2. اما اگر شما نوع از آن همه، و یا آن را در ایمان است که من اضافه شده است آنها را در پیشرفت، ما تقریبا N مربع منهای برخی از اعداد کوچکتر. بنابراین من قصد دارم به تماس این N مربع. اما با مرتب کردن بر اساس انتخاب در بهترین مورد، که چگونه بسیاری از مراحل آن است رفتن به من را؟ 

SPEAKER 5: [نامفهوم] 

دیوید J. مالان: متاسفانه هنوز نفر مربع، درست است؟ از آنجا که اگر من انتخاب کوچکترین عنصر است و ما تا به حال هفت نفر در اینجا، من فقط می دانم، یک بار من بسیار پایان، که من کوچکترین پیدا کرده ام تعداد، هر جا که او یا او ممکن است. اما چگونه می توانم پیدا کنم کوچکترین عدد؟ من را مجبور به انجام پاس دیگر. بنابراین در بهترین حالت، آنچه که ورودی به مرتب سازی بر انتخاب؟ این لیست در حال حاضر مرتب کردن، شماره یک، شماره دو، شماره سه، شماره چهار. اما من کامپیوتر هستم. من فقط می توانم در یک نگاه چیزی که در یک زمان. من نمی توانم مرتب سازی را یک گام مانند یک انسان و می گویند، آه، این درست به نظر می رسد. 

من فقط می توانم داوری صحت در مرتب کردن بر اساس انتخاب با انتخاب کوچکترین عدد. اما حتی اگر من شماره یک برای اولین بار، اگر من چیز دیگری نمی دانند اعداد دیگر، که من نمی، همه من می دانم که من تحویل داده شده است که یک آرایه یا مجموعه ای از درهای که در پشت آن هستند اعداد، تنها راهی که من می دانم که یک کوچکترین بود؟ اگر من تمام راه را در اینجا و ببینی، لعنتی، در واقع کوچکترین. 

اما چگونه می توانم پس از آن مشخص است که دو کوچکترین بعدی است؟ با انجام همان ناکارآمدی دوباره و دوباره. پس در نهایت، با مرتب سازی بر درج، چگونه، در بدترین حالت، آیا ما می گویند آن را انجام؟ این نیز نفر مربع. و چگونه در مورد با بهترین حالت؟ خواهیم ترک که به عنوان یک مطلب یا داستان جالب. ما در آن زمان بعدی خالی را پر کنید، اما اول اجازه دهید به من پیشنهاد است که ما اساسا بهتر از همه از این، همه درست است؟ 

پس به خاطر خود فکر می کنم چه درج مرتب سازی بر خواهد بود. خوب، که بسیار چشمگیر نیست، چون من تنها کسی هستم که تغییر را دیدم. وای. OK را بزنید. بنابراین در اینجا ما باید تا حدودی تظاهرات متفاوت است. اگر من در اینجا زوم، شما خواهید دید که در سمت چپ ما باید مرتب سازی حبابی، در وسط ما باید مرتب سازی بر انتخاب، و در سمت راست، ما چیزی را داریم هنوز نگاه به نام ادغام مرتب سازی بر اساس. اما در نظر گرفتن آنچه که ما بوده ام در اینجا انجام می دهند تا کنون امروز. هنگامی که جنیفر برای اولین بار روی صحنه آمد، ما را از طریق آرایه ای از اعداد رفت دوباره و دوباره، با جستجوی خطی، و ما رو هم خطی در حال اجرا، بزرگ O از n، پس به صحبت می کنند. 

هنگامی که ما در حال حاضر در هفته اول در نظر بگیرند طبقه، وقتی که ما تا به حال تقسیم و تسخیر، و ما تا به حال پاره کردن دفترچه تلفن، و جنیفر، و ما جمعی قوی تر است که بینش های کلیدی بود که به دوباره و دوباره تکرار خود را با به نحوی دور انداختن، دور انداختن، دور انداختن، نیمی از مشکل، و یا به طور کلی، تقسیم یک مشکل در نیمه، و سپس درمان قطعه کوچکتر از مشکل به عنوان مفهومی معادل از سوی دیگر، ما به نحوی بود اساسا بهتر است. اما با مرتب سازی حبابی، با انتخاب مرتب کردن، مرتب کردن بر اساس قرار دادن، ما ممکن است ام چنین بینش که جنیفر را انجام داد. ما تقریبا فقط راه می رفت و چهارم یک دسته کامل از زمان، و ما چیزهای پیچانده کمی، مبادله در این دستور، شاید قرار دادن و یا انتخاب. اما در پایان روز، من بسیاری بی دست و پا راه رفتن به عقب و جلو. ما در هیچ واقعا اهرم چیزی است هوشمند مانند جنیفر مانند تقسیم و فتح. 

بنابراین مرتب سازی بر ادغام، در مقابل، که ما تا هفته آینده را ببینید، آن را به اهرم که ایده اصلی تقسیم ورودی، و سپس نصف، و سپس نصف و نصف. و در هر تکرار از حلقه، مرتب سازی بر نیمه چپ و سمت راست نیم، سپس نیمه چپ از نیمی چپ، و نیمه سمت راست از سمت چپ، و سپس نیمه سمت چپ نیمه سمت راست، و نیمه سمت راست از نیمه سمت راست است. و تکرار دوباره و دوباره. 

بنابراین شما این دید را ببینید، اما این این است آنچه که ما در انتظار هفته آینده. و به طور کلی، زمانی که ما فکر می کنم کمی کمی سخت تر در مورد هر گونه مشکل از جمله. ما نفر مربع در سمت چپ، N مربع در وسط، و n n در سمت راست وارد سیستم شوید. پس مطلب یا داستان جالب واقعی خود وجود دارد. ما به شما در روز دوشنبه را ببینید. 

[تشویق حضار]