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

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

بنابراین اجازه انجام دست در بخش اول. پس فقط دست خود را کثیف با محیط زیست scratch.mit.edu نامیده می شود. این یک ابزار که استفاده می کنیم است در کلاس در مقطع کارشناسی است. حتی اگر آن را طراحی برای 12 سال به بالا، ما از آن استفاده برای تا بخشی از آن بسیار کمی از آنجا که یک زیبا، سرگرم کننده است راه های گرافیکی آموزش چیزی کمی در مورد برنامه نویسی. بنابراین به آن URL سر، که در آن شما باید یک صفحه کاملا شبیه به این را ببینید، و به جلو بروید و کلیک کنید پیوستن به خراش در بالا سمت راست و را انتخاب کنید یک نام کاربری و یک رمز عبور و در نهایت خود را دریافت کنید scratch.mit.edu account--. من فکر کردم من می خواهم این را به عنوان یک استفاده اولین فرصت برای نشان دادن این. یک سوال پیش در زمان استراحت، آمد در مورد آنچه که کد در واقع مانند به نظر می رسد. و ما صحبت می کردند در زمان استراحت، در مورد C، در particular-- به خصوص سطح پایین تر در یک زبان قدیمی تر است. و من فقط سریع گوگل جستجو برای پیدا کردن کد C برای جستجوی دودویی، الگوریتم که ما برای جستجو استفاده می که دفترچه تلفن پیش از آن. این مثال خاص، البته، یک دفترچه تلفن جستجو. این فقط جستجو یک دسته کامل از اعداد در حافظه کامپیوتر. اما اگر شما می خواهم برای فقط یک بصری حس چه برنامه نویسی واقعی زبان به نظر می رسد، به نظر می رسد چیزی کمی شبیه به این. پس از آن در مورد 20 به علاوه، 30 یا خط کد، اما گفتگو ما بیش از شکستن را دارا بودند در مورد چگونگی این در واقع می شود به صفر و آنهایی که بدل و اگر شما نمی توانید فقط برگرداندن که پردازش و از صفر و آنهایی که بازگشت به کد. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

کامپیوتر: آخ، آخ، آخ. 

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

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

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

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

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

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

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

آره، به طوری که برخی از وجود دارد "اگر" شرایط وجود دارد، بیش از حد. و آن را تبدیل out-- ما this-- را ببینید اما بلوک های دیگر در آن وجود دارد که وجود دارد می توان گفت، اگر شما لمس کردن یک چیز دیگر بر روی صفحه نمایش، اگر شما در حال لمس کردن پد لیلی، "و سپس" و پس از آن که هنگامی که ما به قورباغه دوم ظاهر می شود. بنابراین حتی اگر این بازی است که قطعا بسیار به تاریخ، حتی اگر در نگاه اول وجود دارد خیلی از رفتن بلیک کنین و این در دو دقیقه شلاق نیست، احتمالا در زمان او چند ساعت برای ایجاد این بازی بر اساس حافظه و یا فیلم های خود را از نسخه گذشته از آن. اما همه این چیزهای کوچک رفتن بر روی صفحه نمایش در انزوا جوش پایین به این بسیار ساده جنبش constructs-- و یا اظهارات مانند که بحث شد، حلقه ها و شرایط، و این در مورد آن. یک چند دیگر از ویژگی های خیال باف است. برخی از آنها صرفا زیبایی شناسی و یا صوتی، مانند تلفن های موبایل فقط با بازی. اما در بیشتر قسمت ها، به شما در این زبان، خراش داشته باشد، همه از اساسی بلوک های ساختمان که شما در C، جاوا، جاوا اسکریپت را داشته باشد، پی اچ پی، روبی، پایتون، و هر تعداد از زبان های دیگر. هر گونه سوال در مورد خراش؟ خیلی خوب. بنابراین ما نمی خواهد در عمیق تر به خراش شیرجه رفتن، هر چند قابلی ندارد این آخر هفته، به خصوص اگر شما بچه ها و یا خواهرزاده و برادرزاده و از جمله، به معرفی آنها به خراش. این در واقع یک زیبا و بازیگوش محیط زیست با، به عنوان نویسندگان آن می گویند، سقف بسیار بالا است. حتی اگر ما با آغاز بسیار جزئیات سطح پایین، شما واقعا می توانید انجام دهید بسیار کمی با آن، و این است که شاید نمایشی از که دقیقا. 

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

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

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

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

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

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

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

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

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

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

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

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

در این مورد سریع بود، اما چه مدت طول می در واقع را؟ اجازه دهید آن را به نظر می رسد و احساس می کنم کمی خسته کننده تر. بنابراین یک، دو، سه، چهار، پنج، شش، هفت، هشت، نه، 10، 11، 12، 13، 14، 15، 16-- تعداد دلخواه. من فقط می خواستم بیشتر این زمان از چهار. بنابراین اگر من یک کل کردم دسته از اعداد آن now-- حتی مهم نیست آنچه آنها are-- اجازه فکر می کنم در مورد آنچه این الگوریتم واقعا مانند است. 

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

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

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

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

و به این ترتیب اجازه دهید در مورد فکر می کنم چگونه بسیاری از مراحل من در واقع دارم ، جستجو از طریق در هر زمان. در وضعیت اول ما 16 عدد بود، و به همین ترتیب maximally-- اجازه دهید فقط انجام این کار برای یک discussion-- من تا به حال از طریق 16 نگاه اعداد به پیدا کردن کوچکترین. اما یک بار من کنده خارج کوچکترین عدد، چگونه طولانی لیست باقی مانده، البته بود؟ فقط 15. بنابراین چگونه بسیاری از اعداد بن یا من از طریق بار دوم در اطراف نگاه می کنید؟ 15، فقط برای رفتن و پیدا کردن کوچکترین. اما در حال حاضر، البته، در این لیست است، بیش از حد، کوچکتر از قبل از آن بود. بنابراین چگونه بسیاری از مراحل من باید در کنار هم؟ 14 و پس از آن 13 و پس از آن 12، به علاوه نقطه، نقطه، نقطه، تا زمانی که من تنها با یک ترک کرد. بنابراین در حال حاضر یک دانشمند کامپیوتر بپرسید، خوب، چه که همه مساوی؟ این در واقع برابر برخی بتن تعداد که ما می توانیم قطعا انجام حساب شده است، اما ما می خواهم به بحث در مورد بهره وری از الگوریتم کمی formulaically بیشتر، مستقل از چه مدت این لیست است. 

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

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

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

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

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

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

بنابراین 1000 صفحه کتاب تلفن ممکن است ما را 500 صفحه نوبت، به علاوه یک اگر ما دو برابر تماس کمی. بنابراین اگر یک دفترچه تلفن دارای صفحات N، اما ما در حال انجام دو صفحه در یک زمان، که تقریبا چه؟ N بیش از دو، به طوری که مانند N بیش از دو. اما من یک ادعای لحظه پیش که n بیش از two-- این نوع از همان را به عنوان تنها N. این فقط یک ضریب ثابت است، دانشمندان کامپیوتر می گویند. بیایید تنها در تمرکز متغیرها، really-- بزرگترین متغیر در معادله است. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

دانشجو: آنها را به منظور. 

دیوید مالان: OK. من یک مثال مشخص تر می دهد. 

دانشجو: صعودی چیدمان. دیوید مالان: صعودی مرتب. عبارت دقیق تر. من نمی دانم چه چیزی شما را با صعودی بود. چی شده؟ 

دانشجویی: کوچکترین اعداد است در فضای اول نیست. 

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

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

دانشجو: به علاوه یک است. 

دیوید مالان: آن چیست؟ 

دانشجو: به علاوه یک است. 

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

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

دیوید مالان: چه خبر در جای مناسب نیست؟ 

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

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

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

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

آن است، چرا که ما این ثابت اشتباه نکنید، ما ثابت این اشتباه، و ما این اشتباه را ثابت شده است. بنابراین ما ثابت سه اشتباه مسلما. هنوز هم واقعا به نظر نمی مرتب شده اند، اما آن است عینی به مرتب نزدیک تر چرا که ما ثابت برخی از این اشتباهات است. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

و بنابراین من می تواند چهار عدد در اینجا قرار دهید. یک دو سه چهار. یا من می تواند چهار حرف یا علامت قرار داده است. "هی!" می تواند حق وجود دارد، زیرا هر یک از حروف، ما بحث شد، می تواند به نمایندگی با هشت بیت یا ASCII یا یک بایت. بنابراین به عبارت دیگر، شما می توانید قرار 8 میلیارد همه چیز در داخل این یک چوب از حافظه است. در حال حاضر چه معنی است به قرار دادن همه چیز برگشت به پشت به پشت در حافظه مثل این؟ این چیزی است که یک برنامه نویس به یک "آرایه." پاسخ در یک برنامه کامپیوتری، شما فکر نمی کنم در مورد سخت افزار اساسی، در هر سه. شما فقط از خودتان به عنوان داشتن فکر می کنم دسترسی به کل میلیارد بایت، و شما می توانید هر چیزی که با آن را می خواهم. اما برای راحتی به طور کلی مفید برای حفظ حق حافظه خود را در کنار یکدیگر مثل این. بنابراین اگر من زوم بر روی this-- چرا که ما قطعا در حال رفتن به منظور جلب یک میلیارد squares-- کمی بیایید فرض کنیم که این هیئت مدیره نشان دهنده که چوب از حافظه در حال حاضر. و من فقط رسم به عنوان بسیاری از من نشانگر پایان می رسد تا به من در اینجا. بنابراین در حال حاضر ما باید یک چوب حافظه در هیئت مدیره که کردم یک، دو، سه، چهار، پنج، شش، یک، دو، سه، چهار، پنج، شش، seven-- تا 42 بایت حافظه در کل صفحه نمایش. متشکرم. بله، آیا حساب من است. بنابراین 42 بایت حافظه است. پس چه چیزی این در واقع چیست؟ خوب، یک برنامه نویس کامپیوتر در واقع به طور کلی این حافظه به عنوان آدرس فکر می کنم. به عبارت دیگر، هر یک از این مکان در حافظه، در سخت افزار، دارای یک آدرس منحصر به فرد. 

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

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

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

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

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

بنابراین در حال حاضر اجازه دهید بپرسید دیگر درخواست استفاده از حافظه، چرا که در پایان از روز را در واریانس است. مهم نیست که چه ما ممکن است با انجام کامپیوتر، در پایان روز سخت افزار است که هنوز هم همان زیر هود. چگونه می توانم یک کلمه ذخیره در اینجا؟ خوب، یک کلمه در یک کامپیوتر مانند "سلام!" می شود درست مثل این ذخیره می شود. و اگر شما می خواهید یک دیگر کلمه، می توانید به سادگی بازنویسی که و می گویند چیزی مانند "سلام" و فروشگاه که در اینجا. 

و بنابراین در اینجا، بیش از حد، این contiguousness است که در واقع یک مزیت است، به دلیل یک کامپیوتر فقط می توانید از راست به چپ. اما در اینجا یک سوال است. در زمینه این کلمه، ساعت-E-L-L-O، علامت تعجب، چگونه ممکن است کامپیوتر دانید که در آن کلمه آغاز می شود و در آن کلمه به پایان می رسد؟ در زمینه اعداد، چگونه کامپیوتر می دانید چه مدت دنباله ای از اعداد است و یا که در آن شروع می شود؟ خب، معلوم out-- و ما نمی خواهد بیش از حد به به این سطح از detail-- کامپیوتر حرکت چیزهای اطراف در حافظه به معنای واقعی کلمه از طریق این آدرس ها. بنابراین در یک کامپیوتر، اگر شما نوشتن کد برای ذخیره چیزها مانند کلمات، آنچه شما واقعا انجام شده است تایپ کردن عبارت که به یاد داشته باشید که در آن در حافظه کامپیوتر این کلمات هستند. بنابراین به من اجازه انجام بسیار، به عنوان مثال بسیار ساده است. 

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

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

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

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

پس بیایید سعی کنیم که. من قصد دارم به آن را ذخیره کنید. و این است که، دوباره، بسیار محیط مدرسه قدیمی. من نمی توانم کلیک کنید، من نمی توانم بکشید. من باید به نوع دستورات. بنابراین من می خواهم برای اجرای برنامه من است، پس من ممکن است این مثل hello.c انجام دهید. که فایل من فرار است. اما صبر کنید، من گم شده یک گام. چیزی که ما می گویند لازم است گام برای یک زبان مانند C؟ من فقط منبع نوشته ام کد، اما چه چیزی نیاز دارم؟ آره، من نیاز به یک کامپایلر. A SO بر روی مک من در اینجا، من برنامه ای به نام شورای همکاری خلیج فارس، کامپایلر GNU C، که اجازه می دهد به من برای انجام this-- به نوبه خود کد منبع من به، ما آن را پاسخ، کد ماشین. 

و من می توانید ببینید که، دوباره، به شرح زیر، این صفر و آنهایی که من فقط ایجاد شده از کد منبع من، همه از صفر و آنهایی که. و اگر من می خواهم برای اجرای من program-- آن اتفاق می افتد به فایلهای دو دویی a.out برای نام reasons-- تاریخی "سلام." من می توانم آن را دوباره اجرا. سلام سلام سلام. و به نظر می رسد به کار شود. 

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

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

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

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

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

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

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

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

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

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

مسابقه سوم که می آید تا، من قصد دارم برای گفتن، هی، کامپیوتر، من تکه دیگری از حافظه است. و من قصد دارم برای قرار دادن پایین هر چه بود، مثل 75، و من به زنجیره ای دارند هم در حال حاضر به نحوی. مسابقه چهارم می آید همراه، و شاید که به سمت پایان ترم است. و در آن نقطه برنامه من ممکن است با استفاده از حافظه همه جا، بیش از همه از لحاظ جسمی. و به این ترتیب فقط برای ضربات، من رفتن به قرعه کشی این جلو quiz-- من فراموش کرده ام آنچه در آن بود؛ من فکر می کنم شاید 80 یا something-- راه را در اینجا. 

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

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

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

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

صفر، یک، دو، سه، چهار، پنج، شش، هفت. به نظر می رسد 90 در حافظه شماره هفت. همه این فلش می باشد مانند یک تکه کوچک کاغذ که جهت به دادن برنامه ای است که می گوید این نقشه را دنبال برای رسیدن به محل هفت. و شما را به پیدا نمره آزمون دوم دانش آموز است. در همین حال، 75-- اگر من این ادامه، این هفت، هشت، نه، 10، 11، 12، 13، 14، 15. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

بنابراین شما می دانید چه چیزی؟ به جای قرار دادن تمام سخنان من در همان سطل، پس به صحبت، مانند در یک لیست بزرگ، چرا من حداقل سعی کنید بهینه سازی و ایجاد لیست من 1/26 تا زمانی. بهینه سازی قانع کننده ممکن است چرا نمی I-- هنگام قرار دادن یک کلمه به این ساختار داده ها، به حافظه کامپیوتر، به همین دلیل می توانم همه 'A' کلمات قرار داده نشده در اینجا، همه ب `کلمات در اینجا، و همه 'C' کلمات در اینجا؟ بنابراین این پایان می رسد تا با قرار دادن یک سیب در اینجا، موز در اینجا، طالبی در اینجا، و غیره. 

و اگر من اضافی کلمه like-- چه دیگر؟ سیب، موز، گلابی. هر کسی از یک میوه فکر می کنم که با A، B، و C شروع می شود؟ کامل Blueberry--. است که برای پایان دادن به اینجا. و بنابراین ما به نظر می رسد به یک حاشیه راه حل بهتر، زیرا در حال حاضر اگر من می خواهم به جستجو برای اپل، من first-- من فقط شیرجه نمی به ساختار داده من من را به حافظه کامپیوتر من شیرجه رفتن نیست. من برای اولین بار در حرف اول را نگاه کنید. 

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

در حال حاضر این کاهش زمان ما به طور بالقوه به اندازه یک نفر از 26، چرا که اگر شما فرض کنیم که شما به عنوان بسیاری از "A" کلمات به عنوان "الف" کلمات به عنوان "Q" کلمات، که واقعا realistic-- نیست شما در حال رفتن به انحراف در سراسر حروف خاص از alphabet-- اما این امر می تواند یک افزایشی رویکردی است که اجازه نمی دهد شما برای رسیدن به کلمات بسیار سریع تر. و در واقع، پیچیده برنامه، گوگل از جهان، فیسبوک از world-- آنها را به یک جدول هش استفاده برای بسیاری از مقاصد مختلف. اما آنها نمی خواهد تا به عنوان ساده و بی تکلف فقط در حرف اول نگاه در سیب یا موز یا گلابی و یا طالبی، چرا که به عنوان شما می توانید این را ببینید لیست هنوز هم می تواند طولانی. 

و این هنوز هم ممکن است نوع باشد از linear-- بنابراین نوع آهسته، مانند با O بزرگ از n که ما قبلا بحث شده است. پس چه یک جدول هش خوب واقعی خواهد شد do-- آن را به یک آرایه بسیار بزرگتر است. و آن را به استفاده از یک بسیار بیشتر تابع هش پیچیده، به طوری که آن را نه تنها در نگاه "است." شاید آن را در به نظر می رسد "A-P-P-L-E" و به نحوی تبدیل آن پنج حرف به مکانی که در آن اپل باید ذخیره شود. ما فقط ساده لوحانه با استفاده از حرف 'a' تنهایی، به دلیل آن را خوب و ساده است. 

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

اما متوجه چگونه به سرعت این نوع از بحث تشدید، یا تا کنون است که آن را به نوعی بیش از در این نقطه سر را که خوب است. اما ما آغاز شده، به یاد بیاورید، با واقعا چیزی سطح پایین و الکترونیکی. و این باز هم این موضوع موضوع انتزاع، که در آن هنگامی که شما شروع به گرفتن اعطا شده، خوب، من it-- کردم وجود دارد حافظه فیزیکی، OK، آن را کردم، هر مکان فیزیکی است آدرس، خوب، من آن را کردم، من می تواند نشان دهنده کسانی که آدرس به عنوان arrows-- شما می توانید به سرعت شروع به مکالمات پیچیده تر که در پایان به نظر می رسد اجازه می دهد می شود ما برای حل مشکلات مانند جستجو و مرتب سازی موثر تر است. و مطمئن باشند، too-- چون من فکر می کنم این عمیق ترین ما به برخی از رفته است از این موضوعات CS proper-- ایم در این انجام شده در یک روز و نیم اشاره آنچه شما به طور معمول ممکن است انجام بیش از دوره هشت هفته در یک ترم. 

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