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

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

رسید مری بث. SPEAKER: مری بث، در آمده است. اجازه بدهید میکروفون دریافت در اینجا برای شما. از ملاقات شما خوشبختم. 

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

رسید آه، این است رفتن به برای همیشه. 

SPEAKER: و ما را تماشا خواهد کرد عنوان شما این کار را، بدون فشار. رسید: نه، هیچ فشار و یا هر چیزی. 

SPEAKER: و برای تفریح، اجازه دهید قرار دادن یک تایمر. 

رسید سرگرم کننده بسیار، بسیار سرگرم کننده است. 

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

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

رسید آره. 

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

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

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

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

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

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

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

در حال حاضر این نقطه، نقطه، نقطه نوع از امواج آن دست در برخی از جزئیات juicier، اما اجازه دهید فقط به جلو و ساده. اگر شما از بالا به یاد مدرسه، رک و پوست کنده، که بسیاری از شما کتاب های ریاضی به حال است که حال بازی ورق کمی بر روی جلد جلو یا پشت جلد است که شما نشان داد جمع آنچه که سری مانند این در نهایت به اضافه شده است. در حالت کلی، اگر شما یک متغیر مانند نفر، و در واقع این یکی، اگر شما در نگاه شما کتاب ریاضی مدرسه قدیمی، شما می توانید ببینید که این در واقع اضافه می کند تا این مبلغ در اینجا، n بار نفر منهای 1 تمام 2 تقسیم شده است. بنابراین در حال حاضر اجازه دهید تصریح این درست است، به همین ترتیب کبیسه از ایمان، این چیزی است که این مبالغ تا، و ما می توانیم ثابت کنند که در یک حالت کلی است. اما در حال حاضر اجازه دهید این گسترش است. بنابراین اجازه دهید این را چند برابر می کند، به طوری که تعداد مربع، منهای نفر، تقسیم بر 2. این واقعا ازت مربع، تقسیم بر 2، منهای نفر بیش از 2، به طوری که همه خوب و جالب است. اما چه اتفاقی می افتد اگر ما در حال حاضر پلاگین در ارزش؟ فرض کنید من هشت ندارد مردم، اما می گویند یک میلیون نفر است. و یک میلیون فقط به خاطر آن تعداد بسیار بزرگ است، اجازه دهید که در به برق وصل کنید و ببینید چه اتفاقی می افتد. بنابراین اگر من به برق وصل از یک میلیون به آن فرمول من قصد دارم به یک میلیون مربع، تقسیم بر 2، منهای یک میلیون، تقسیم بر 2. در حال حاضر چه چیزی است که رفتن به یکسانند؟ بنابراین 500 میلیارد، منهای 500،000. و اگر من در واقع انجام که ریاضی را، که به معنی که مرتب سازی بر یک میلیون افراد مبتلا به نوعی حباب ممکن است من را 499،999،500،000 مراحل و یا مقایسه در پایان، ما فقط برونیابش. 

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

[VIDEO پخش] 

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

-Well-- 

-I'm عرض پوزش، maybe-- 

نه، نه، نه. من فکر می کنم نوعی حباب خواهد بود که راه را اشتباه رفتن است. 

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

-We've جاسوس ما در وجود دارد. 

-OK، اجازه دهید بپرسم مختلف پرسش مصاحبه. 

[END VIDEO پخش] 

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

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

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

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

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

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

رسید پیدا کردن بزرگترین عدد در یک لیست؟ 

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

بنابراین اگر به جای من پیشنهاد کرد که الگوریتم در این جهان وجود دارد که یک زمان در حال اجرا است که محدود O بزرگ log n است، ورود نفر؟ از کجا این دیده می شود که قبل از؟ آره؟ 

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

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

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

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

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

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

رسید حباب مرتب کردن بر اساس؟ 

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

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

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

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

رسید تابع () printf؟ SPEAKER: آن چیست؟ رسید تابع () printf؟ SPEAKER: تابع () printf. OK، اطمینان حاصل کنید. بنابراین به تعداد ثابت از مراحل. و من در حال حاضر که باید now-- ما در حال صحبت کردن در مورد کد C و نه خراش، چیزی مثل مثلا با تابع () printf، ما باید شروع به گرفتن دقیق. از آنجا که تابع () printf نمی کشد ورودی، آن را به یک رشته است، و رشته ها را به لحاظ فنی طول داشته باشد. بنابراین اگر ما در حال حاضر می خواهید انتخاب کنید بر شما، اگر برای شما مهم نیست، از لحاظ فنی ما می تواند که تابع () printf استدلال می کنند اختصاص یک ورودی با طول متغیر، و قطعا ممکن است بیش را زمان برای چاپ یک رشته در این مدت، از این طولانی است. 

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

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

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

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

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

رسید نفر مربع. SPEAKER: نفر مربع. چرا؟ 

رسید از آنجا که شما برای تعریف [نامفهوم]. 

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

چه در مورد نوع قرار دادن، که در آن من در زمان که I، داده شد و پس از آن من به او plopped و یا او را در جای مناسب؟ سپس من به نفر دوم اقدام، او در جای مناسب plopped. سپس نفر بعدی، plopped او در جای مناسب. توجه کنید که این بسیار خطی، پس به صحبت می کنند. من یک خط راست، من هستم رفتن به جلو و عقب، من به دنبال هرگز به عقب واقعا، اما چه اتفاقی می افتد زمانی که من به او وارد و یا او را به آغاز لیست که ما در روز دوشنبه بود؟ چه اتفاقی افتاد؟ آره؟ رسید [نامفهوم]. SPEAKER: آره، که گرفتن بود، درست است؟ شما ممکن است از یاد همکلاسی های خود، در صورتی که هر حرکت با ساخت شد پای خود را، که یک عملیات بود. بنابراین اگر سه نفر اینجا و آنجا فرد جدید راه را بر داشت وجود دارد، در یک مرحله طولانی مثل این، مطمئن، او و یا او فقط می تواند به پایان است. اما اگر ما در حال فکر کردن در مورد کامپیوتر و مجموعه ای از حافظه، این افراد می رویم به به زدن بیش از به اتاق را برای آن شخص. و به طوری که نفر منهای 1 shufflings، نفر منهای 2 shufflings، نفر منهای 3 shufflings است فقط نوع اتفاق می افتد پشت سر من، نه در مقابل من مانند قبل، از بعضی جهات. در حال حاضر به عنوان یک به کنار، و به عنوان شما ممکن است را دیده اند، به صورت آنلاین اگر شما شروع به مجبور باشید در مورد انواع، در بسیاری از آنهایی که متفاوت وجود دارد خارج وجود دارد، برخی از آنها بهتر از دیگران است. در واقع، bogosort است این نوع از سرگرم کننده را به نگاه کردن است. Bogosort طول می کشد مجموعه ای از اعداد و یا می گویند یک دست ورق بازی، به طور تصادفی آنها را shuffles، و چک اگر آنها طبقه بندی شده اند. و اگر نه، آن را دوباره. و اگر نه، آن را دوباره. اگر نه، آن را دوباره. باور نکردنی احمق. 

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

رسید پیتر. 

SPEAKER: آن چیست؟ 

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

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

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

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

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

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

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

[تشویق حضار] 

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

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

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

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

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

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

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

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

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

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

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

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

رسید دارن. 

SPEAKER: دن. دن به جلو پا کرده است. 

رسید دارن. SPEAKER: دارن، انجام می شود. آیا شما می گویند دارن یا دن؟ 

رسید دارن. 

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

رسید لوقا. 

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

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

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

رسید آدریانو. 

SPEAKER: آدریانو. آدریانو در حال حاضر طبقه بندی شده اند. و چه نام شما چیه؟ 

رسید الکس. 

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

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

رسید عمر. 

SPEAKER: عمر، گام به گام رو به جلو، انجام می شود. نیمه سمت چپ طبقه بندی شده اند است. و چه نام شما چیه؟ 

رسید کریس. 

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

رسید مارینا. 

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

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

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

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

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

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

رسید ورود به نفر. 

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

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

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

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