ყველა უფლება, ასე, გამოთვლითი სირთულის. უბრალოდ ცოტა გაფრთხილება სანამ ჩვენ ჩაყვინთვის ძალიან far-- ამ ყველაფერს, ალბათ, მათ შორის ყველაზე მათემატიკის მძიმე რამ ჩვენ ვსაუბრობთ CS50. იმედია ეს არ იქნება ძალიან დიდი და ჩვენ შევეცდებით და დაგეხმარებათ მეშვეობით პროცესში, მაგრამ უბრალოდ ცოტა სამართლიანი გაფრთხილება. არსებობს ცოტა მათემატიკის ჩართული აქ. ყველა უფლება, რათა გამოყენება ჩვენი გამოთვლითი რესურსების რეალურ world-- ეს მართლაც მნიშვნელოვანია გვესმოდეს, ალგორითმები და როგორ გადაამუშავებს მონაცემები. თუ ჩვენ მართლაც გვაქვს ეფექტური ალგორითმი, ჩვენ შეიძლება შეამციროს ოდენობით რესურსები ჩვენ გვაქვს გაუმკლავდეთ მას. თუ ჩვენ გვაქვს ალგორითმი, რომელიც აპირებს ბევრი მუშაობა დამუშავება ნამდვილად დიდი კომპლექტი მონაცემები, ეს აპირებს მოითხოვოს მეტი და სხვა რესურსები, რომელიც ფული, RAM, რომ ყველა სახის ნივთები. 

ასე რომ, მას შეუძლია ანალიზი ალგორითმის გამოყენებით ეს ინსტრუმენტი კომპლექტი, ძირითადად, სთხოვს კითხვა როგორ აკეთებს ამას ალგორითმი მასშტაბის როგორც ჩვენ იმისათვის, რომ უფრო და უფრო მეტი მონაცემები მას? In CS50, თანხის მონაცემები ჩვენ მუშაობს საკმაოდ მცირე. საერთოდ, ჩვენი პროგრამების ვაპირებთ აწარმოებს მეორე ან less-- ალბათ ბევრი ნაკლებად განსაკუთრებით დასაწყისში. 

მაგრამ ვიფიქროთ კომპანია, რომელიც ეხება ასობით მილიონი მომხმარებელს. და მათ უნდა დამუშავება რომ კლიენტების მონაცემები. როგორც რაოდენობის მომხმარებელს ისინი აქვს უფრო დიდი და უფრო დიდი, ის აპირებს მოითხოვს უფრო და უფრო მეტი რესურსი. კიდევ რამდენი რესურსი? ისე, რომ დამოკიდებულია იმაზე, რამდენად ჩვენ ანალიზი ალგორითმი, გამოყენებით ინსტრუმენტი ამ ყუთისთვის. როდესაც ვსაუბრობთ სირთულის ალგორითმი, რომელიც ზოგჯერ თქვენ მესმის, რომ ეს მოხსენიებული, როგორც დრო სირთულის ან ჰარით სირთულის მაგრამ ჩვენ უბრალოდ აპირებს მოვუწოდებთ complexity-- ჩვენ ზოგადად ვსაუბრობთ ყველაზე ცუდი სცენარით. იმის გათვალისწინებით, რომ ყველაზე უარესი წყობის მონაცემები, რომ ჩვენ შეიძლება სროლა მას, როგორ არის ეს ალგორითმი აპირებს დამუშავება და გაუმკლავდეთ, რომ მონაცემები? ჩვენ მოვუწოდებთ ზოგადად უარესი runtime ალგორითმი დიდი ო. ასე რომ, ალგორითმი შეიძლება ითქვას, რომ აწარმოებს ო ო ან O of n კვადრატში. და უფრო მეტი რა იმ ნიშნავს მეორე. 

ზოგჯერ, თუმცა, ჩვენ ზრუნვა შესახებ საუკეთესო სცენარია. თუ ეს მონაცემები ყველაფერი, რაც გვინდოდა ეს უნდა იყოს და ეს იყო აბსოლუტურად სრულყოფილი და ჩვენ გაგზავნის ამ სრულყოფილი მითითებული მონაცემების მეშვეობით ჩვენი ალგორითმი. როგორ უნდა გაუმკლავდეს, რომ სიტუაცია? ჩვენ ზოგჯერ ეხება, რომ როგორც დიდი Omega, ასე რომ განსხვავებით დიდი O, ჩვენ გვაქვს დიდი ომეგა. Big-Omega საუკეთესო სცენარია. Big-O უარესი სცენარით. საერთოდ, როდესაც ჩვენ ვსაუბრობთ სირთულის ალგორითმი, ჩვენ ვსაუბრობთ უარესი სცენარით. გააგრძელეთ, რომ გონება. 

და ამ კლასში, ჩვენ ზოგადად აპირებს დატოვება მკაცრი ანალიზი განზე. არსებობს მეცნიერებათა და სფეროებში მიეძღვნა ამ სახის ნივთები. როდესაც ვსაუბრობთ მიზეზის მეშვეობით ალგორითმები, რომელიც ჩვენ ყველაფერს გავაკეთებთ, ცალი მიერ ცალი მრავალი ალგორითმები ვსაუბრობთ კლასში. ჩვენ რეალურად მხოლოდ ვსაუბრობთ მსჯელობა საღი აზრი, არა ფორმულები, ან მტკიცებულებები, ან რამე მსგავსი. ასე რომ არ ინერვიულოთ, ჩვენ არ იქნება ნელა დიდი მათემატიკის კლასის. 

ამიტომ ვთქვი, რომ ჩვენ ვზრუნავთ სირთულის იმიტომ, რომ ეს სვამს კითხვას, თუ როგორ გთხოვთ ჩვენი ალგორითმები გაუმკლავდეს უფრო დიდი და უფრო დიდი მონაცემთა კომპლექტი მიმდინარეობს ესროლეს მათ. ისე, რა არის მონაცემთა ნაკრები? რა არ ვგულისხმობ, როცა განაცხადა, რომ? ეს იმას ნიშნავს, რაც ხდის ყველაზე გრძნობა კონტექსტში, უნდა იყოს პატიოსანი. თუ ჩვენ გვაქვს ალგორითმი, პროცესები Strings-- ჩვენ, ალბათ, ვსაუბრობთ ზომის სიმებიანი. სწორედ მონაცემები set-- ზომა, რაოდენობა გმირები, რომ შეადგინოს სიმებიანი. თუ ჩვენ ვსაუბრობთ ალგორითმი, რომელიც გადაამუშავებს ფაილი, ჩვენ შეიძლება საუბარი, თუ როგორ ბევრი kilobytes მოიცავს რომ ფაილი. და ეს მონაცემები კომპლექტი. თუ ჩვენ ვსაუბრობთ ალგორითმი რომელიც ამუშავებს კოლექტორები უფრო ზოგადად, როგორიცაა დახარისხება ალგორითმები ან ძებნას ალგორითმები, ჩვენ, ალბათ, ვსაუბრობთ ნომერი ელემენტები, რომელიც მოიცავს მასივი. 

ახლა, ჩვენ შეგვიძლია გავზომოთ ალგორითმი, კერძოდ, როდესაც ვამბობ, რომ ჩვენ შეგვიძლია გავზომოთ ალგორითმი, მე იმას ნიშნავს, რომ ჩვენ შეგვიძლია გავზომოთ როგორ ბევრი რესურსი სჭირდება მდე. თუ არა იმ რესურსების, რამდენი ბაიტი RAM-- ან მბ მეხსიერება იგი იყენებს. ან, თუ რამდენი დრო სჭირდება აწარმოებს. და ჩვენ შეგვიძლია ვუწოდოთ გავზომოთ, თვითნებურად, ვ ო. სადაც n რაოდენობის ელემენტების მონაცემები კომპლექტი. და ფ ო რამდენი somethings. რამდენი ერთეული რესურსების აკეთებს ის მოითხოვს დამუშავებას, რომ მონაცემები. 

ახლა, ჩვენ რეალურად არ მაინტერესებს იმაზე, თუ რა ვ N არის ზუსტად. ფაქტობრივად, ჩვენ ძალიან იშვიათად will-- რა თქმა უნდა, არასდროს ამ კლასის მე ჩაყვინთვის შევიდა ნებისმიერი მართლაც ღრმა ანალიზი, თუ რა ვ ო. ჩვენ უბრალოდ აპირებს ვისაუბროთ, თუ რა ვ n დაახლოებით ან რა ეს ტენდენცია. და ტენდენცია ალგორითმი ნაკარნახევი მისი უმაღლესი ჯილდო ვადით. და ჩვენ ვხედავთ, რაც მე ნიშნავს, რომ ხდება შევხედოთ უფრო კონკრეტული მაგალითი. 

მოდით ვთქვათ, რომ ჩვენ გვაქვს სამი სხვადასხვა ალგორითმები. პირველი, რომელიც იღებს n კუბი, რამდენიმე ერთეული რესურსები დამუშავებას მონაცემები კომპლექტი ზომა n. ჩვენ გვყავს მეორე ალგორითმი, რომელიც იღებს n cubed პლუს n კვადრატში რესურსები დამუშავებას მონაცემები კომპლექტი ზომა n. და ჩვენ გვაქვს მესამე ალგორითმი, რომელიც ეშვება შიგნით რომ იკავებს n cubed მინუს 8n კვადრატი პლუს 20 n ერთეული რესურსები დამუშავებას ალგორითმი მონაცემები მითითებული ზომა n. 

ახლა, ჩვენ ნამდვილად არ ვაპირებთ შეღწევას ამ დონის დეტალურად. მე ნამდვილად უნდა ამ up აქ როგორც ილუსტრაცია წერტილი რომ მე ვაპირებ მიღების მეორე, რომელიც არის, რომ ჩვენ მხოლოდ ნამდვილად აინტერესებს შესახებ ტენდენცია რამ როგორც მონაცემების კომპლექტი დიდია. ასე რომ, თუ მონაცემები კომპლექტი არის პატარა, არსებობს რეალურად საკმაოდ დიდი განსხვავება ამ ალგორითმები. მესამე ალგორითმი არსებობს იღებს 13-ჯერ აღარ, 13-ჯერ თანხა რესურსების აწარმოებს ნათესავი პირველი. 

თუ ჩვენი მონაცემები კომპლექტი არის ზომა 10, რომელიც არის დიდი, მაგრამ არ არის აუცილებელი დიდი, ჩვენ ვხედავთ, რომ იქ რეალურად ცოტა განსხვავება. მესამე ალგორითმი უფრო ეფექტური. ეს არის რეალურად 40% - ან 60% -ით უფრო ეფექტურია. იგი იღებს 40% დროის. ეს შეიძლება პერსპექტივაში მას შეუძლია მიიღოს 400 ერთეული რესურსების დამუშავებას მონაცემები კომპლექტი ზომა 10. ვინაიდან პირველი ალგორითმი, პირიქით, იღებს 1,000 ერთეული რესურსები დამუშავებას მონაცემები კომპლექტი ზომა 10. მაგრამ შეხედეთ, რა ხდება, ჩვენი ციფრები კიდევ უფრო დიდი. 

ახლა, განსხვავება შორის ამ ალგორითმები დაიწყოს გახდეს ცოტა ნაკლებად აშკარა. ხოლო ის ფაქტი, რომ არსებობს ქვედა რათა terms-- უფრო სწორად, ვადები, ქვედა exponents-- დაიწყოს გახდეს შეუსაბამო. თუ მონაცემები კომპლექტი არის ზომა 1000 და პირველი ალგორითმი გადის მილიარდი ნაბიჯები. და მეორე ალგორითმი ეშვება მილიარდი და მილიონი ნაბიჯები. და მესამე ალგორითმი გადის მხოლოდ shy მილიარდი ნაბიჯები. ეს საკმაოდ ბევრი მილიარდი ნაბიჯები. ისინი ქვედა წესრიგის თვალსაზრისით დაიწყოს გახდეს ნამდვილად შეუსაბამო. და მხოლოდ ნამდვილად ჩაქუჩი მთავარი point-- იმ შემთხვევაში, თუ მონაცემების შეტანის არის ზომა million-- სამივე საკმაოდ ბევრი მიიღოს ერთი quintillion-- თუ ჩემი მათემატიკის correct-- ნაბიჯები დამუშავებას მონაცემების შეტანის ზომა მილიონი. ეს არის ის, ბევრი ნაბიჯები. ხოლო ის ფაქტი, რომ ერთ-ერთი მათგანი, შესაძლოა, მიიღოს რამდენიმე 100,000 ან რამდენიმე 100 მილიონი კიდევ უფრო ნაკლები, როდესაც ჩვენ ვსაუბრობთ ნომერი რომ big-- ეს არის სახის შეუსაბამო. ისინი ყველა ტენდენცია მიიღოს დაახლოებით n cubed, და ასე რომ, ჩვენ რეალურად ეხება ყველა ეს ალგორითმები როგორც ბრძანებით n კუბი და დიდი ო ო cubed. 

აქ არის სია ზოგიერთი უფრო საერთო გამოთვლითი სირთულის კატეგორიები ის, რომ ჩვენ ვაწყდებით ალგორითმები, ზოგადად. და ასევე კონკრეტულად CS50. ეს დავალება ზოგადად სწრაფად ზედა, ზოგადად ნელი ბოლოში. ასე რომ, მუდმივი დრო ალგორითმები, როგორც წესი, იყოს სწრაფი, მიუხედავად იმისა, ერთი ზომა მონაცემთა შეყვანის გაივლის. ისინი ყოველთვის ერთი ოპერაციის და ერთი ერთეული რესურსების გამკლავება. ეს შეიძლება იყოს 2, შესაძლოა, 3, ეს შეიძლება იყოს 4. მაგრამ ეს მუდმივი ნომერი. ეს არ იცვლება. 

ლოგარითმული დრო ალგორითმები ოდნავ უკეთესი. და ძალიან კარგი მაგალითია ლოგარითმული დრო ალგორითმი თქვენ აუცილებლად ჩანს ახლა არის tearing გარდა სატელეფონო წიგნი მოძიების მაიკ სმიტი სატელეფონო წიგნი. ჩვენ გაჭრა პრობლემა ნახევარი. ასე რომ, როგორც ო იღებს დიდი და უფრო დიდი და larger-- ფაქტობრივად, ყოველ დროს, თქვენ გაორმაგდება n, ეს მხოლოდ იღებს, კიდევ ერთი ნაბიჯი. ასე რომ, ბევრი უკეთესი ვიდრე, ვთქვათ, ხაზოვანი დრო. რა არის თუ ორჯერ n, ის იღებს ორმაგი რაოდენობის ნაბიჯები. თუ თქვენ გასამმაგებას n, სჭირდება გასამმაგებას რაოდენობის ნაბიჯები. ერთი ნაბიჯი თითო ერთეული. 

მაშინ რამ კიდევ ცოტა more-- ცოტა ნაკლები დიდი იქიდან. თქვენ ხაზოვანი რიტმული დროს, ზოგჯერ სახელად შესვლა ხაზოვანი დროს ან უბრალოდ N შეხვიდეთ n. და ჩვენ, მაგალითად ალგორითმი, რომელიც ეშვება N შესვლა N, რომელიც ჯერ კიდევ უკეთესი მეტი კვადრატული time-- n კვადრატში. ან მრავალწევრის დროს, n ორი ნებისმიერი რაოდენობის აღემატება ორ. ან ექსპონენციალური დრო, რომელიც კიდევ worse-- C ო. ასე რომ, გარკვეული მუდმივი დააყენა, რათა ძალა ზომა შეყვანა. ასე რომ, თუ იქ 1,000-- თუ მონაცემთა შეყვანის ზომა 1000 დასჭირდება C რომ 1,000th ძალა. ეს გაცილებით უარესია, ვიდრე მრავალწევრის დროს. 

Factorial დრო არის უარესი. და სინამდვილეში, იქ ნამდვილად გააკეთებს არსებობს უსასრულო დრო ალგორითმები, როგორიცაა, ე.წ. სულელური დალაგება რომლის სამუშაო შემთხვევით shuffle მასივი და მაშინ შეამოწმეთ თუ არა ეს დახარისხებული. და თუ ეს ასე არ არის, შემთხვევით shuffle მასივი ერთხელ და შეამოწმეთ თუ არა ეს დახარისხებული. და როგორც თქვენ ალბათ imagine-- თქვენ წარმოიდგინეთ სიტუაცია სადაც ყველაზე უარესი, რაც უზრუნველყოფს არასოდეს რეალურად იწყება მასივი. ეს ალგორითმი, რომ აწარმოებს სამუდამოდ. და ისე, რომ იქნება უსასრულო დრო ალგორითმი. იმედია თქვენ არ უნდა წერა ნებისმიერი factorial და უსასრულო დრო ალგორითმები CS50. 

ასე რომ, მოდით ცოტა მეტი კონკრეტული შევხედოთ ზოგიერთი მარტივი გამოთვლითი სირთულის კლასი. ასე რომ, ჩვენ გვაქვს მაგალითად ან ორი მაგალითები აქ მუდმივი დრო ალგორითმები, რომელიც ყოველთვის ერთი ოპერაცია უარეს შემთხვევაში. ასე რომ, პირველი მაგალითად ჩვენ გვაქვს ფუნქცია მოუწოდა 4 თქვენთვის, რომელიც იღებს მასივი ზომა 1000. მაგრამ შემდეგ, როგორც ჩანს, ფაქტობრივად არ ჰგავს განთავსებულია it-- ნამდვილად არ აინტერესებს რა არის შიგნით, რომ მასივი. ყოველთვის მხოლოდ ბრუნდება ოთხ. ასე რომ, ალგორითმი, მიუხედავად იმისა, რომ ეს იღებს 1,000 ელემენტები არ არაფერი მათთან. უბრალოდ ბრუნდება ოთხ. ის ყოველთვის ერთი ნაბიჯი. 

ფაქტობრივად, დავუმატოთ 2 nums-- რომელიც ჩვენ ვნახეთ ადრე, როგორც well-- მხოლოდ ამუშავებს ორი რიცხვებით. ეს არ არის ერთი ნაბიჯი. ეს, ფაქტობრივად, რამდენიმე ნაბიჯი. თქვენ, თქვენ b, თქვენ დაამატოთ მათ ერთად და გამომავალი შედეგები. ასე რომ, ეს 84 ნაბიჯები. მაგრამ ეს ყოველთვის მუდმივი, მიუხედავად იმისა, ან ბ. თქვენ უნდა მიიღოს, კიდევ ბ, დაამატოთ მათ ერთად, გამომავალი შედეგი. ასე რომ, მუდმივი დროის ალგორითმი. 

აი, მაგალითად, ხაზოვანი დროს ალგორითმი ალგორითმი, რომელიც gets--, რომელიც იღებს დამატებით ერთი ნაბიჯი, შესაძლოა, როგორც თქვენი შეყვანის იზრდება 1. ასე რომ, ვთქვათ, ჩვენ ვეძებთ ნომერი 5 შიგნით მასივი. ალბათ სიტუაცია, სადაც თქვენ შეგიძლიათ იპოვოთ ის საკმაოდ ადრეულ. მაგრამ თქვენ შეიძლება ასევე აქვს სიტუაცია, სადაც ის შეიძლება იყოს ბოლო ელემენტს მასივი. In მასივი ზომა 5, თუ ჩვენ ვეძებთ ნომერი 5. დასჭირდება 5 ნაბიჯები. და სინამდვილეში, წარმოვიდგენდი, რომ იქ არა 5 სადმე ამ მასივი. ჩვენ ჯერ კიდევ რეალურად უნდა შევხედოთ თითოეული ელემენტის მასივი რათა დადგინდეს, თუ არა 5 არის. 

ასე რომ, უარეს შემთხვევაში, არის ის, რომ ელემენტი არის ბოლო მასივი ან არ არსებობს. ჩვენ კვლავ უნდა შევხედოთ ყველა n ელემენტებს. ასე რომ, ეს ალგორითმი გადის ხაზოვანი დრო. თქვენ შეგიძლიათ ადასტურებენ, რომ ექსტრაპოლაციის ცოტა განაცხადა, თუ ჩვენ გვქონდა 6-ელემენტს მასივი და ჩვენ ეძებდნენ ნომერი 5, ეს შესაძლოა 6 ნაბიჯები. თუ ჩვენ გვაქვს 7-ელემენტს მასივი და ჩვენ ვეძებთ ნომერი 5. ეს შეიძლება მიიღოს 7 ნაბიჯები. როგორც ჩვენ კიდევ ერთი ელემენტია ჩვენი მასივი, სჭირდება კიდევ ერთი ნაბიჯი. სწორედ ხაზოვანი ალგორითმი უარეს შემთხვევაში. 

Couple სწრაფი კითხვებზე თქვენთვის. რა არის runtime-- რა არის უარესი runtime ამ კონკრეტულ მონაკვეთში კოდი? ასე რომ, მე მაქვს 4 loop აქ, რომ გადის საწყისი j უდრის 0, ყველა გზა მდე მ. და რა მე ვხედავთ აქ, ის არის, რომ ორგანოს loop გადის მუდმივ დრო. ამიტომ გამოყენებით ტერმინი, ჩვენ უკვე ვისაუბრეთ ამაზე რა იქნება უარესი runtime ამ ალგორითმი? მიიღეთ მეორე. შიდა ნაწილი loop გადის მუდმივ დრო. და გარე ნაწილი loop აპირებს აწარმოებს მ ჯერ. რა არის უარესი Runtime აქ? ხომ იცი, დიდი O მ? ნეტავ იყოს სწორი. 

როგორ შესახებ კიდევ ერთი? ამჯერად ჩვენ გვაქვს loop შიგნით loop. ჩვენ გვყავს გარე მარყუჟის რომელიც ეშვება ნულიდან გვ. და ჩვენ გვაქვს შიდა loop, რომელიც ეშვება ნულიდან p, და შიგნით რომ, ვაცხადებ, რომ სხეულის loop გადის მუდმივ დრო. რა არის უარესი Runtime ამ კონკრეტულ მონაკვეთში კოდი? ისე, კიდევ ერთხელ, ჩვენ გვაქვს გარე loop, რომელიც ეშვება p ჯერ. და თითოეული time-- იტერაციული რომ მარყუჟი, საკმაოდ. ჩვენ გვყავს შიდა loop რომელიც ასევე გადის p ჯერ. და შემდეგ შიგნით რომ, არსებობს მუდმივი time-- მცირე მონაკვეთში არსებობს. 

ასე რომ, თუ ჩვენ გვაქვს გარე მარყუჟის, რომ გადის p ჯერ შიგნით რაც არის შიდა მარყუჟის, რომ გადის p times-- რა არის უარესი runtime ამ მონაკვეთში კოდი? ხომ იცი, დიდი O პ კვადრატი? 

მე Doug Lloyd. ეს არის CS50.