[موسیقی] 

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

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

DAVID J. مالان: بنابراین می تواند شما را به پیش رو و پیدا کردن برای ما مایک اسمیت، به همان سرعتی که شما می توانید؟ به همان سرعتی که شما می توانید. به معنای واقعی کلمه پاره شدن مشکل در نصف شما نیاز به. 

ALAN استرادا: ام. DAVID J. مالان: به معنای واقعی کلمه پاره شدن مشکل در نیم. 

ALAN استرادا: اوه. میلی متر. خیلی خوب. 

DAVID J. مالان: OK. خوب است. متشکرم. ALAN استرادا: بسیار خوب. باشه. 

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

[خنده] 

ALAN استرادا: بله، من فکر می 

DAVID J. مالان: ما چه بخش در؟ ALAN استرادا: مفلرس، به طوری که. 

DAVID J. مالان: OK. اما مایک اسمیت است که پس از اگزوز می شود. بنابراین-- 

[خنده] 

خیلی خوب. ALAN استرادا: از کجا دنبال چه هستیم؟ DAVID J. مالان: مایک اسمیت. ALAN استرادا: مایک اسمیت. DAVID J. مالان: در حال حاضر، ما در جراحی است. در حال حاضر، پزشکان. اکنون-- 

ALAN استرادا: Let's- اجازه دهید با واقعی است. واقعی است. 

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

ALAN استرادا: این راه. 

DAVID J. مالان: کدام راه؟ ALAN استرادا: صبر کنید. حق M is--؟ ما آغاز شده with-- 

DAVID J. مالان: آره. آنها سمت چپ در حال. حق خود را. 

ALAN استرادا: آره. 

DAVID J. مالان: به طوری که مایک در اینجا. ALAN استرادا: چه؟ 

[خنده] 

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

ALAN استرادا: اوه. آه. من به شما کردم. من به شما کردم. آه. آه. این is-- خوب، من به شما کردم. اسمیت حق در اینجا؟ 

DAVID J. مالان: اسمیت، از شما سپاسگزارم. بنابراین من به دنبال حفظ تا اسمیت؟ 

ALAN استرادا: اوه، آره. نه نه نه. وای نه. این مال منه. 

DAVID J. مالان: اوه، شما اسمیت است. باشه. 

ALAN استرادا: آره، من اسمیت کردم در اینجا ببینید. بچه ها متاسفم. من فکر کردم Michael-- ما برای مایکل به دنبال شدند. متاسف. 

DAVID J. مالان: این خوب است. همه حق است، در حال حاضر ما به Paccini و پسران. 

ALAN استرادا: Paccini و پسران. DAVID J. مالان: فقط شما و من در این. باشه. یافتن ما مایک اسمیت. اسمیت. 

ALAN استرادا: اسمیت. 

DAVID J. مالان: اسمیت. ما در R زباله است. ALAN استرادا: زباله. آه. این است که به را در حالی که. 

[خنده] DAVID J. مالان: کفش. ما در کفش است. 

ALAN استرادا: در حال حاضر ما در حال gonna-- 

DAVID J. مالان: خوب. ALAN استرادا: Which-- [خنده] آه، این بزرگ است. [خنده] 

DAVID J. مالان: این خوب است. 

ALAN استرادا: آه، این خوب است. من فکر نمی کنم من قصد دارم به دوستان PSAT دارند بعد از این. DAVID J. مالان: خوب. ورزشی. ALAN استرادا: ورزشی. ام، L، M، N، O، P. DAVID J. مالان: OK. بنابراین اجازه دهید این پاره در نیم. مشکلی نیست. این به پایان می رسد ضعیف هر حال، چون مایک اسمیت را نمی خواهد در صفحات زرد باشد. 

ALAN استرادا: AW. 

DAVID J. مالان: نه، آن را OK. اما اجازه دهید مانند وانمود او در این صفحه است. بنابراین در حال حاضر، شما مشکل محدودتر به پایین به یک صفحه، و ما مایک اسمیت. 

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

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

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

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

و اگر اردن در واقع می تواند به ما بپیوندید تا در اینجا در مرحله. بیا تا برای فقط یک لحظه. نام شما چیست؟ CAROLINE: کارولین. DAVID J. مالان: کارولین، در آمده است. و به شما امکان پیوست توسط من و اردن در اینجا. کارولین، از شما سپاسگزارم. خیلی خوب. بنابراین آنچه که ما در اینجا برای کارولین 26 کتاب آبی است که با استفاده از FAS به اداره برخی از امتحانات نهایی. این سخت شدن برای پیدا کردن، اما آنچه که ما در پیش انجام داده ام این است که ما نام کسی قرار داده ام در مقابل هر یک از این، اما ما آن را ساده نگه داشته ام پس از آن قرار دادن نام کامل. بنابراین ما می فرد با نام قرار L، D، J، B، تمام راه را از طریق Z، اما آنها به صورت تصادفی است. و بنابراین اگر شما می توانید، صحبت کردن خود را راه را از طریق این مشکل به عنوان شما آن، می تواند به شما جلو بروید و مرتب سازی بر اساس این برای ما، از الف تا ی 

مخاطبان: خوب، پس L مانند وسط است. C شروع شده است. B. J قبل L. B، Q. 

DAVID J. مالان: نگه دارید که برای یک ثانیه فکر می کردم. از آنجا که در غیر این صورت، این تنها جالب را به شما، من، و اردن. ما میرویم آنجا. مخاطبان: [نامفهوم]. R. DAVID J. مالان: OK. چه کار می کنی؟ 

CAROLINE: M می آید پس از O. 

DAVID J. مالان: OK. 

CAROLINE: O. DAVID J. مالان: O، خوب است. 

CAROLINE: E. 

DAVID J. مالان: E، F. آره. 

CAROLINE: T، U، V. 

DAVID J. مالان: V، T، U، V. پس از آن به نظر میرسد شما making-- رفتن است. به نظر می رسد شما در حال ساخت یک توده بزرگ در اینجا، و نوع یک توده بزرگ بیش از وجود دارد. بنابراین نیمه اول از حروف الفبا، نیمه دوم از حروف الفبا. باشه. خوب است. نوع تفکیک مسئله در دو. M، N، X. آره. CAROLINE: K. DAVID J. مالان: OK. K. بنابراین شما نوع انتخاب آنها را یکی پس از دیگری، قرار دادن آن یا چپ یا راست، و یا Z رفتن بر روی زمین. باشه. 

CAROLINE: Z رفتن بر روی زمین. 

DAVID J. مالان: OK. Y است که بر روی زمین. حالا ما می توانیم X. قرار 

CAROLINE: G. DAVID J. مالان: در G رفتن به سمت چپ. S است که راست. همه راست، در حال رفتن تمام راه را به سمت چپ. 

CAROLINE: A، B، C، D، 

DAVID J. مالان: در حال حاضر، خوب است. ما باید A، B، C. W رفتن به پایین وجود دارد. همه حق است، T. 

CAROLINE: H، I، J. DAVID J. مالان: H، I، J. خوب. CAROLINE: در مرکز، من gonna-- DAVID J. مالان: OK. بنابراین در حال حاضر، ما قصد داریم به نوع از ادغام این شمع های مختلف. بنابراین A تا C، پس از آن من D، و E، F و، و G و H و I خوب. J، K. و پس از آن، این شمع وارونه، اما این OK. به روی چشم. ما می توانیم برخی از گوشه را کاهش دهد. باشه. و سپس ما باید W، X، Y، Z. 

CAROLINE: آره. 

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

[تشویق] 

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

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

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

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

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

این دموی one-- می رویم به یک سریعتر و سریعتر است. بیا پایین. نام شما چیست؟ ترور: ترور. 

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

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

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

TREVOR: این یکی. 

DAVID J. مالان: شماره 

TREVOR: OK. این یکی. 

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

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

TREVOR: OK. 

DAVID J. مالان: چه خبر الگوریتم خود را برای رفتن به؟ 

TREVOR: خوب، اگر آن را طبقه بندی شده اند، آن را یا رفتن به be-- اگر به بزرگترین بزرگترین، نزولی، آن را یکی از اولین، و یا اگر آن مخالف است، آن خواهد بود که یکی از آخرین. بنابراین من فقط شیر این درب، و پس از آن فقط شیر آخرین درب. DAVID J. مالان: بسیار عالی است. خیلی خوب. بنابراین ما تعداد 50 پیدا شده است. تا در اسرع وقت شما را می دانستند آنها طبقه بندی شده اند شد، ما قادر به اهرم این فرض بود. به طوری که آنها بیش از حد مانند هستید به عنوان مثال دفترچه تلفن. به محض این که شما، حتی با یک مشکل کوچک مانند این، ورودی خود را قبل از طبقه بندی شده اند، ما می توانیم در واقع ارزش پیدا مسلما موثر تر است. 

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

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

-روز تعداد 50؟ 

-روز تعداد 50. و شما می توانید نشان می دهد چه پشت هر یک از این درها به سادگی با لمس آن را با یک انگشت. لعنتی. 

[خنده] 

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

-باشه. 

البته اگر شما آن را پیدا کنید، شما این فیلم را نگه دارید. اگر شما آن را پیدا کند، شما آن را به عقب. 

-انسان. 

اوه! 

- [نامفهوم] OK. بنابراین من قصد دارم به بررسی به پایان می رسد برای اولین بار برای تعیین اینکه آیا there's-- اوه. 

[تشویق حضار] 

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

[پخش ویدئو] 

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

[خنده] 

این یک سوال ترفند نیست. یکی. 

[خنده] در این نقطه، نمره خود را بسیار نیست خوب، پس شما نیز ممکن است ادامه دهم. سه. 

[خنده] 

ادامه دادن. صادقانه بگویم، من نمی تواند کمک کند اما تعجب می کنم آنچه را که شما حتی فکر کردن در مورد، so-- 

[خنده] فقط ردیف بالا، به طوری که شما سه سمت چپ کردم. بنابراین من هفت پیدا کنید. 

[خنده] 17. هفت. 

[تشویق حضار] 

خیلی خوب. 

[END پخش] 

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

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

بنابراین یکی در سبز turquoise-- در آن است؟ آیا شما به ارتکاب؟ دو. بیا پایین. باشه. سه. چهار. اجازه دهید me-- OK، پنج. شما توسط دوست شما نامزد شده است. شش، هفت و هشت. بیا بالا. خیلی خوب. خیلی از شما ممنونم. بیا بالا. بیا بالا. 

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

عنان: عنان. 

DAVID J. مالان: عنان. دیوید. نام شما چیست؟ 

یوسف: یوسف. 

DAVID J. مالان: یوسف، شما شماره دو هستند. 

سرنا: سرنا، شماره ی سه. استفان، شماره چهار. CYNTHIA: سینتیا. DAVID J. مالان: سینتیا، شماره پنج. [نامفهوم] DAVID J. مالان: [نامفهوم]. دیوید، شماره شش. MATT: مت. DAVID J. مالان: تعداد مت هفت. و؟ 

WAVERLY: ویورلی. 

DAVID J. مالان: ویورلی، شماره هشت. خیلی خوب. اگر شما could-- اوه. اگر همه شما، به عنوان خود را اولین چالش، وجود دارد هشت غرفه موسیقی در اینجا رو به مخاطبان. اگر شما می توانید شماره خود را در قرار داده این موسیقی می ایستد در چنین راهی که آنها مطابق با همان تعداد در هیئت مدیره. بنابراین خودتان را که کنید و با ایجاد قرار دادن شماره های خود را در این موسیقی می ایستد در اینجا. عالی تا کنون. 

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

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

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

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

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

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

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

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

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

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

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

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

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

بنابراین بدون سقوط کردن مرحله این سال، من قصد دارم برای گرفتن تعداد one-- و چه نام خود را دوباره بود؟ 

عنان: عنان. 

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

استفان: استفان. 

DAVID J. مالان: استفان در راه است. بنابراین قبل از استفان حل این مشکل، چه باید کرد؟ چه ما با استفان انجام دهد؟ 

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

مخاطبان: [نامفهوم]. 

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

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

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

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

یوسف: یوسف. 

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

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

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

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

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

یوسف: یوسف. 

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

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

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

عنان: عنان. 

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

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

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

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

[تشویق حضار] 

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

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

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

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

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

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

اما به طور کلی، اگر n است برای رفتن به یک ارزش بزرگ، من قصد دارم به ادعا می کنند که N مربع در حال رفتن به عامل غالب. این فقط رفتن به یکی از عوامل بزرگتر به تعداد مراحل از / 2 N. بنابراین چه چیزی منظورم این است که؟ بیایید سعی کنید یک مثال ساده، حتی هر چند ریاضی می شود بزرگ است. 

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

بنابراین ما از همان فرمول به عنوان قبل از. من می خواهم یک میلیون پلاگین، به طوری که من یک میلیون تقسیم مجذور 2، منهای یک میلیون تقسیم بر 2. اگر من که ریاضی در پیش در اینجا، ما 500 میلیارد منهای 500،000، که به ما می دهد 499999500000، که است که رفو بزرگ است. 

در واقع، اگر شما مقایسه کن 499000000000، 999 میلیون، 500،000 برابر ارزش اصلی ما، 500 میلیارد، آن را بسیار لعنتی نزدیک. درست؟ N 2 تقسیم می دهد مجذور us-- یا نه، N مربع تقسیم بر 2 به ما 500 میلیارد. که زیبا رفو نزدیک به 499999500000، است که می گویند کم کردن 500،000، یا به طور کلی، کم کردن کردن N مربع، واقعا یک معامله بزرگ است. از N مربع باعث می شود این شماره رشد واقعا سریع است. 

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

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

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

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

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

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

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

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

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

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

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

بنابراین اولین بار، هزینه آن من یک قدم به حل همه چیز، سپس آن را به من هزینه دو مرحله به حل همه چیز. چگونه بسیاری از مراحل آن است رفتن به به رفع همه چیز را به قرار دادن پنج را در جای مناسب. سه. از آنجا که در حال حاضر من به حرکت یک، دو، سه. چگونه بسیاری از مراحل آن رفتن است را به برای قرار دادن چهار در جای مناسب. 4 به علاوه 5، به علاوه 6، به علاوه 7. 

و پس از آن به یکسان ریاضی آنچه که ما برای مرتب سازی انتخابی است. در حال حاضر این مجموعه که فقط به افزایش است. 1 به علاوه 2 به علاوه 3 به علاوه 4، و یا برعکس، به همراه 6 7 به علاوه 5 به علاوه 4 اضافه می کند تا برای امروز اهداف به در دستور N مربع. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[بوق] 

به موجب آن شما در حال استفاده از یک فرکانس بر اساس ارتفاع نوار نوار. این نوع حباب دیگر است. 

[بوق بزند تاب خورده] 

آینده آینده is-- آینده تا در کنار مرتب سازی بر انتخاب is--، که در آن باز هم، ما انتخاب کوچکترین عنصر بعدی، و ما می توانید ببینید آن در حال رشد از چپ به راست. 

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

و از آن است. ما به شما وقت بعدی را ببینید. 

[WHOOSHING و موسیقی]