[موسیقی] 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

در حال حاضر اجازه دهید یک پاس دیگر در این، از یک کمی بیشتر جنبه رسمی، فقط در مورد، این طنین انداز بهتر که بحث سطح بالاتر است. بنابراین در اینجا الگوریتم دوباره. بیایید از خودمان بپرسیم، ساعت هم در حال اجرا است این الگوریتم مراحل مختلف؟ اجازه دهید آن را به اولین تقسیم مورد و در مورد دوم. اگر و دیگری در مورد IF، اگر n کمتر از 2 است، فقط بازگشت. احساس می کند مانند زمان ثابت. آن، نوع، مانند دو مرحله، اگر n کمتر از 2 است، و سپس بازگشت. اما همانطور که ما در روز دوشنبه گفت، زمان ثابت، یا O بزرگ از 1، می تواند دو مرحله، سه مراحل، حتی 1،000 مرحله انجام شد. مهم این است که آن را یک عدد ثابت از مراحل. بنابراین رنگ زرد برجسته شبه در اینجا اجرا می شود در، ما آن را پاسخ، زمان ثابت. بنابراین بیشتر به طور رسمی، و ما قصد داریم این to-- خواهد بود که تا چه حد ما رسمی این حق now-- T از N، زمان در حال اجرا از یک مشکل که n چیزی را به عنوان ورودی، برابر O بزرگ یک، اگر n کمتر از 2 است. پس از آن مشروط به آن است. بنابراین به روشن، اگر n کمتر از 2، ما یک لیست بسیار کوتاه، پس از آن زمان در حال اجرا، T از n که در آن n است 0 یا 1، در این مورد بسیار خاص، آن را فقط به زمان ثابت است. آن را به یک گام به گام، دو مرحله، هر چه. این یک عدد ثابت از مراحل است. 

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

پس در واقع formulaically، ما می توانیم این بیان، البته scarily در ابتدا کمی نگاه، اما آن چیزی است که قطاری که دقیقا منطق. زمان در حال اجرا، T از n اگر n بزرگتر یا برابر با 2 است. در این مورد، مورد دیگری، T از n است تقسیم بر 2، به علاوه T از n تقسیم بر 2، به علاوه بزرگ O از N، برخی از تعداد خطی از مراحل، شاید دقیقا N، شاید 2 بار N، اما آن را تقریبا، منظور از n است. به طوری که، بیش از حد، چگونه ما می توانیم بیان این formulaically. در حال حاضر شما نمی این مگر اینکه مطمئن شوید شما آن را در ذهن خود ثبت کرده ام، و یا آن را در تماس از کتاب درسی، که ممکن است کمی دارند برگه تقلب در پایان، اما این است که، در واقع، رفتن به ما O بزرگ از n log n استفاده را، زیرا تکرار است که شما در اینجا دیدن بر روی صفحه نمایش، اگر شما در واقع آن را انجام داد از، با یک تعداد نامحدود از مثال ها، یا شما آن را formulaically انجام داد، شما را ببینید که این، چرا که این فرمول خود را بازگشتی، با تن N بیش از چیزی در سمت راست، و t از n بیش از در سمت چپ، این می تواند در واقع بیان می شود، در نهایت، برو به عنوان بزرگ N log n است. اگر قانع نشده، که خوب در حال حاضر، فقط را در ایمان، که که، در واقع، که منجر به عود، اما این فقط یک کمی بیشتر از یک روش ریاضی به دنبال در آن زمان در حال اجرا از ادغام مرتب سازی بر بر اساس شبه آن به تنهایی. 

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

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

اریک اشمیت: ما سوال، و ما سوال نامزدهای ما بپرسید، و این یکی از لری Schwimmer است. 

پرزیدنت اوباما: OK. 

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

پرزیدنت اوباما: Well-- اریک اشمیت: گاهی اوقات، شاید من متاسفم، maybe-- پرزیدنت اوباما: نه، نه، نه، نه، نه، من فکر می اریک اشمیت: این it-- نیست پرزیدنت اوباما: من فکر می کنم، من فکر می کنم حباب مرتب سازی بر اساس خواهد بود که راه را اشتباه رفتن است. اریک اشمیت: بیا. چه کسی او را در این گفت؟ باشه. من علوم کامپیوتر نه شماها 

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

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

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

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

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

اما اجازه دهید در نظر کن که حتی که برنامه فوق العاده ساده، hello.c، بنام تابع است. آن را به نام printf است. اما من تابع () printf نوشتن نیست، در واقع، که همراه با ج، پس به صحبت می کنند. این فراخوان تابع است که اعلام در io.h استاندارد، که یک فایل هدر، که یک موضوع است ما در واقع شیرجه رفتن به عمق بیشتری قبل از اینکه طولانی. اما یک فایل هدر است به طور معمول همراه توسط یک فایل کد، فایل کد منبع، به طوری که بسیار شبیه به وجود io.h. استاندارد وجود دارد 

چندی پیش، کسی، و یا دیگران، همچنین نوشته یک فایل به نام io.c استاندارد، در که تعاریف واقعی، و یا پیاده سازی تابع () printf، و مجموعه ای از توابع دیگر، در واقع نوشته شده است. با توجه به این، اگر ما در نظر داشتن اینجا در سمت چپ، hello.c، که زمانی که وارد شده، به ما می دهد hello.s، حتی اگر صدای جرنگ جرنگ می کند صرفه جویی در یک مکان را خسته نکنید ما می توانیم آن را ببینید، و این که کد اسمبلی می شود به hello.o، مونتاژ که ، در واقع، نام پیش فرض است داده هر زمان که شما منبع کامپایل کد را به کد شیء، اما نمی کاملا آماده است تا آن را اجرا نشده است، به دلیل یک گام دیگر است اتفاق می افتد، و شده است برای چند گذشته اتفاق می افتد هفته، شاید به شما نادانسته. 

به طور خاص جایی در CS50 IDE، و این، بیش از حد، خواهد بود یک بیت از یک ساده برای یک لحظه، وجود دارد، و یا پس از یک زمان، یک فایل به نام io.c استاندارد، که کسی را به وارد io.s استاندارد و یا معادل آن، که کسی پس از آن مونتاژ به io.o استاندارد، و یا آن را تبدیل کردن به یک فایل کمی متفاوت فرمت است که می تواند مختلف داشته فرمت فایل در دسترس نباشد، اما در تئوری و مفهومی، دقیقا این مراحل تا به حال در بعضی از فرم اتفاق می افتد. که است که می گویند، که در حال حاضر زمانی که من برای نوشتن یک برنامه، hello.c، که فقط می گوید، سلام جهان، و من با استفاده از کد شخص دیگری مانند printf، که یک بار بر بود زمان، در یک فایل به نام io.c استاندارد، پس از آن به نحوی من را به من کد شیء، صفر و آنهایی که من، و هدف آن شخص کد، و یا صفر و آنهایی که، و به نوعی آنها را با هم پیوند به یک فایل نهایی، به نام سلام، که همه از صفر و آنهایی که از تابع اصلی من، و همه از صفر و آنهایی که برای printf است. 

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

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

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

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

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

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

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

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

خیلی خوب. که آن را برای هفته سه. ما به شما وقت بعدی را ببینید. این CS50 بود. 

[موسیقی] 

SPEAKER 1: او در میان وعده بود نوار خوردن بستنی و مغز گردو شکلات داغ. او آن را بیش از همه چهره خود را داشتند. او با پوشیدن که شکلات مانند ریش SPEAKER 2: چه کار می کنید؟ SPEAKER 3: هممم؟ چی؟ 

SPEAKER 2: آیا شما فقط شیب دو؟ شما دو روش غوطه وری تراشه. SPEAKER 3: ببخشید. SPEAKER 2: شما غوطه ور تراشه، شما در زمان گاز گرفتن، و شما دوباره کاهش یافت. SPEAKER 3: SPEAKER 2: به طوری که مانند قرار دادن حق دهان طیف خود را در شیب. دفعه بعد هم که شما را به یک تراشه، فقط آن را شیب یک بار، و پایان دادن به آن. 

SPEAKER 3: شما می دانید چه، دن؟ شما شیب راه که می خواهید به شیب. من راه که من می خواهم به شیب را فرو.