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

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

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

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

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

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

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

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

بنابراین اجازه دهید می گویند که ما سه الگوریتم های مختلف. اولین بار است که طول می کشد N نبات، برخی از واحدهای منابع برای پردازش یک مجموعه داده با اندازه n. ما یک الگوریتم دوم که طول می کشد N نبات به علاوه منابع N مربع برای پردازش یک مجموعه داده با اندازه n. و ما باید یک سوم الگوریتمی که قابل اجرا in-- که طول می کشد تا N 8N منهای نبات مربع به علاوه 20 نفر واحد از منابع برای پردازش یک الگوریتم با مجموعه داده با اندازه n. 

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

اگر مجموعه داده ما اندازه 10 است که بزرگتر است، اما لزوما بزرگ است، ما می توانید ببینید که وجود دارد در واقع یک بیت از یک تفاوت. الگوریتم سوم کارآمد تر می شود. این مورد در واقع 40 درصد است - یا 60٪ کارآمد تر. این 40٪ مقدار زمان طول می کشد. آن را می توانید run-- می کشد 400 واحد از منابع برای پردازش یک مجموعه داده اندازه 10. در حالی که اولین الگوریتم، در مقابل، 1،000 واحد از منابع طول می کشد برای پردازش یک مجموعه داده اندازه 10. اما نگاه آنچه اتفاق می افتد به عنوان شماره ما را دریافت کنید حتی بزرگتر. 

در حال حاضر، تفاوت بین این الگوریتم ها شروع به تبدیل شدن به یک کمی کمتر آشکار است. و این واقعیت است که وجود دارد پایین را terms-- یا نه، با exponents-- پایین شروع به تبدیل شدن بی ربط است. اگر یک مجموعه داده است از اندازه 1،000 و الگوریتم اول در یک میلیارد مراحل اجرا می شود. و الگوریتم دوم اجرا می شود در یک میلیارد و یک میلیون مرحله انجام شد. و الگوریتم سوم اجرا می شود در فقط خجالتی از یک میلیارد مراحل. این تقریبا یک میلیارد مراحل. آن عبارات مرتبة پایین تر شروع برای تبدیل شدن به واقعا بی ربط. و فقط به واقعا چکش خانه point-- اگر داده های ورودی است از اندازه million-- هر سه این بسیار یکی quintillion-- اگر ریاضی من مراحل correct-- است به روند داده های ورودی اندازه یک میلیون. که بسیاری از مراحل است. و این واقعیت که یکی از آنها ممکن یک زن و شوهر 100،000، 100 و یا یک زن و شوهر میلیون حتی کمتر که ما در حال صحبت کردن در مورد تعداد که big-- این نوع از بی ربط است. همه آنها تمایل به حدود N، نبات، و بنابراین ما در واقع مراجعه به همه از این الگوریتم ها به عنوان در دستور N نبات و یا بزرگ-O از N نبات. 

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

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

پس از آن چیز یک more-- کمی کمی کمتر بزرگ از وجود دارد. شما باید زمان خطی ریتمیک، گاهی اوقات نام ورود به سیستم زمان خطی و یا فقط N log n است. و ما به عنوان مثال از یک الگوریتم است که اجرا می شود در n log n استفاده، که هنوز هم بهتر از time-- درجه دوم N مربع. یا زمان چند جمله ای، N دو هر تعداد بیشتر از دو. و یا زمان نمایی که حتی worse-- C به N. بنابراین برخی از عدد ثابت مطرح شده به قدرت از اندازه ورودی. بنابراین اگر 1،000-- اگر وجود دارد داده های ورودی از اندازه 1،000، آن C به قدرت 1000 است. این خیلی بدتر از زمان چند جمله ای. 

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

بنابراین، اجازه دهید یک کمی بیشتر نگاه بتن در برخی از ساده کلاس پیچیدگی محاسباتی. بنابراین ما باید یک example-- یا دو مثال here-- از الگوریتم های زمان ثابت، که همیشه یک عملیات واحد در بدترین حالت. بنابراین example-- اول ما باید یک تابع به نام 4 برای شما، که آرایه ای از اندازه طول می کشد 1،000. اما پس از آن ظاهرا در واقع به نظر نمی در it-- واقعا نمی مراقبت چه در داخل آن، که آرایه. همیشه فقط چهار گرداند. بنابراین، این الگوریتم، با وجود این واقعیت است که آن را 1،000 عناصر طول می کشد نمی انجام هر کاری با آنها. تنها چهار گرداند. این همیشه یک قدم. 

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

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

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

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

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

بنابراین اگر ما یک حلقه بیرونی که P بار که در داخل آن است اجرا می شود یک حلقه درونی که P times-- چیزی است که اجرا می شود بدترین حالت زمان اجرا این قطعه از کد را؟ آیا شما حدس می زنم بزرگ-O P از مربع؟ 

من داگ لوید هستم. این CS50 است.