[Powered by Google Translate] [კვირა 3 გაგრძელდა] 

[დევიდ ჯ Malan - ჰარვარდის უნივერსიტეტი] 

[ეს არის CS50. - CS50.TV] 

ყველა უფლება. კეთილი იყოს. ეს არის CS50 და ეს ბოლომდე კვირაში 3. 

ასე რომ იმ უცნობ, გასულ წელს ჰარვარდის დაიწყო რასაც ინოვაცია ლაბორატორია, ან I-ლაბორატორია, რომელიც მშვენიერი შენობის გასწვრივ მდინარე HBS-ს კამპუსში რომ ღიაა კოლეჯის სტუდენტები, GSAS სტუდენტები, სტუდენტები მასშტაბით კამპუსში, მათ შორის ფაკულტეტი, და ეს ადგილი უნდა გავერთიანდეთ, რომ მუშაობა ინოვაციური რამ, განსაკუთრებით სამეწარმეო რამ თუ თქვენ და 0 ან მეტი მეგობრები ფიქრობენ კეთების რაღაც სამეწარმეო ან ამ კლასის, შემდეგ ამ კლასში, ან მის ფარგლებს გარეთ. 

ასე რომ ერთი რამ ისინი მეტი J ვადა არის ამ მოგზაურობის დროს, რომელთაგან ერთი ნიუ იორკში, რომელთაგან ერთი უნდა სილიკონის ველის. ფართი არის ძალიან შეზღუდულია, მაგრამ ეს შესაძლებლობა RUB უნდა ერთად MBAs და ასპირანტების მასშტაბით კამპუსში და რეალურად დროის იმ შესაბამის სფეროებში chatting up startups, chatting up მეწარმეებს და ასე შემდეგ. ასე რომ, თუ დაინტერესებული, შეამოწმეთ ეს მისამართი აქ. ეს არის ასევე ხელმისაწვდომია სლაიდები ხაზზე. 

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

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

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

და ასე თუ როგორ რეალურად პრობლემების შესახებ, რომ მასშტაბის საბოლოოდ შეამცირებს to იდეები ჩვენ შევხედეთ წელს კვირაში 0 და უფრო მეტი დღეს. ჩვენ არ ხელახლა შესრულდეს ეს ალგორითმი, მაგრამ გავიხსენოთ, რომ ჩვენ ასევე გააკეთა კვირაში 0 ამ exercise აქ ჩვენ ყველას აღუდგეს, იღებს ხმების 1, და მაშინ ჩვენ გვქონდა ყველას თვითმმართველობის რაოდენობა მიერ pairing off და დასძინა, თქვენი ნომრები ერთად, მაშინ ნახევარი ბანდა დაჯდა ყოველ iteration. ამიტომ წავედით 500 სტუდენტებს 250 დან 125 და სხვ. თუმცა, როგორც ჩვენ განაცხადა ორშაბათს, ძლიერი იდეა არსებობს ის იყო, რომ თუ ჩვენ გაორმაგდა ზომის რომ პრობლემა და ყველა ბავშვები იუსტიციის ან ევროკომისიის 10 დაბრუნდა ოთახში და შემოგვიერთდნენ, ასევე, შეიძლება ალბათ ითვლიან, რომ მთელი აგრეგატი ჯგუფი მხოლოდ 1 დიდი iteration of loop რადგან ისინი მხოლოდ იქნებ გაორმაგება ზომა ან ევროკომისიის 10 საქმე ცოტა ორჯერ მეტი ზომა. და ამიტომ ჩვენ უნდა დახარჯოს ცოტა მეტი დრო, მაგრამ ჩვენ არ უნდა დახარჯოს 400 ან 700 მეტი ნაბიჯები. 

უბრალოდ ხატვა ამ სურათს ისე, რომ ცოტა ნაკლები აბსტრაქტული, მოდით არ ყველას აღუდგეს. მაგრამ, თუ აღნიშნული, ვინც არჩია იჯდეს ორკესტრი დღეს არ იბადება იდგა up, მოდით ვნახოთ, თუ შევძლებთ გაერკვნენ შორის, ვინც ყველაზე მაღალ პირი ამით იმავე სახის შედარებითი ალგორითმი. ასე რომ, თუ თქვენ იჯდა ორკესტრი, ჩემი ბოდიში, მაგრამ ნაბიჯი 1, აღუდგეს; ნაბიჯი 2, წყვილი off არავისთან მიმდებარე თქვენ, გაერკვნენ, რომელიც გრძელია, და დასხდნენ თუ თქვენ მოკლე. მაშინ ვიმეორებ. [სტუდენტი murmuring] 

Okay. Okay. ერთი დარჩა იდგა. რა არის შენი სახელი? >> ენდრიუ. 

ანდრია, თქვენ ყველაზე მაღალი პირი ორკესტრი მონაკვეთზე დღეს. 

გილოცავთ. [ტაში და cheering] Okay. Have ადგილს. ამიტომ, ჩვენ ი ენდრიუ. მაგრამ რამდენ ხანს უნდა ჰქონოდა ჩემთვის, მაგალითად, იპოვოს ენდრიუ ამ ორკესტრმა მონაკვეთზე 50 + ან ხალხმა? მე შეეძლო აღებული საკმაოდ მარტივი მიდგომა და დაიწყება აქ. და მე 2 ადამიანი აღუდგეს და მე უბრალოდ შედარება, და მაშინ მე ვიტყვი, რომ ვინც ოდნავ მოკლე, "Okay, თქვენ დასხდნენ," და მე ვაპირებ მახსოვს ვინ გრძელია პირი იყო. მაშინ ვიმეორებ, ვიმეორებ, ვიმეორებ, და მე გათიშეთ შესახებ, რომ ყველაზე მაღალი პირი სანამ მიწერ ოდნავ გრძელია, ვიდრე მათ, სადაც წერტილი ოდნავ მოკლეა ადამიანს აქვს შემდეგ დასხდნენ. მაგრამ რომ ალგორითმი ამ ორკესტრის მონაკვეთზე, თუ არსებობს N თქვენგანს, რამდენი ნაბიჯების რომ ალგორითმი აპირებს? >> [სტუდენტი] ნ 

ის აპირებს N, უფლება, რადგან უარეს შემთხვევაში, ასე ვთქვათ, ყველაზე მაღალი ადამიანი არის ძალიან ბოლო პირი, რომ მივიღო, რათა მხოლოდ შემთხვევითი ცუდი იღბალი. ასე რომ, უარეს შემთხვევაში, გაშვებული დრო, რომ ალგორითმი არის წრფივი, ეს N, სადაც n საერთო რაოდენობის ხალხი სივრცეში, ზომა პრობლემა. რაც შეეხება ამ ალგორითმი? ის, რომ თქვენ ყველა წამოდგა და ისევ ნახევარი თქვენ დაჯდა, ნახევარი თქვენ დაჯდა, ნახევარი თქვენ დაჯდა. რამდენი ნაბიჯები უნდა რომ აქვთ აღებული, თუ არსებობს N თქვენგანი აქ? [სტუდენტი] N შესვლა n. >> ეს იქნება უარესი. შესვლა n. 

ასე რომ შედით N, მაშინაც კი თუ თქვენ არ საკმაოდ გახსოვთ რა logarithm არის, ახლა, უბრალოდ ვაფასებ, რომ ეს ეხება რატომღაც ამ საჯელის განახევრებას და საჯელის განახევრებას და საჯელის განახევრებას. იგი არ უნდა იყოს ფაქტორი 2. ეს შეიძლება იყოს ფაქტორი 3. მაგრამ ამ გამეორებას მსგავსი ფაქტორი ისეთი, რომ ზომა პრობლემა აქ იწყება მაგრამ შემდეგ მაშინვე მიდის აქ, მაშინ აქ, მაშინ აქ, მაშინ აქ. თქვენ არ იღებენ პატარა ნაკბენები გარეთ პრობლემა, თქვენ ნამდვილად chopping away at it დიდი დაეცა swoop ყოველ ჯერზე. ამიტომ ჩვენ გვქონდა 50 ადამიანი, მაშინ 25, მაშინ 12 ½ ან 13 ადამიანი იდგა, მაშინ 6 ½ და ა.შ. სანამ საბოლოოდ მხოლოდ ენდრიუ დარჩა იდგა. ამიტომ, ჩვენ ვაპირებთ, რომ მოვუწოდებთ შესვლა of n, და თქვენ შეგიძლიათ ვიზუალიზაციისთვის ეს შემდეგნაირად. შეგახსენებთ, ამ სურათის აქ სადაც ხაზოვანი ალგორითმი ჰგავს წითელი ხაზი არსებობს, ყვითელი ხაზი იყო დათვლა მიერ 2S ალგორითმი რომ ჩვენ გამოიყენება დათვლის სტუდენტები წარსულში, მაგრამ დღეს წმიდა გრაალი აპირებს დარჩეს ამ მწვანე ზოლის აქ თუ ჩვენ გაორმაგდა რაოდენობის ხალხი ორკესტრი მონაკვეთზე ან უბრალოდ განაცხადა, ჯოჯოხეთი, მოდით ყველას მთელი ოთახი აღუდგეს, არ ასეთი დიდი გარიგება იმიტომ, რომ ჩვენ დაახლოებით გაორმაგდება რამდენი ადამიანი ქვემოთ აქ, 1 მეტი iteration, პრობლემას არ წარმოადგენს. 

ჩვენ ნაპოვნი ენდრიუ ან ვინც ხდება იყოს გრძელია ვიდრე ენდრიუ წელს ანტრესოლით ან აივანი. ასე რომ, ეს მარტივი იდეა, რომ ავიღეთ იმდენად თავისთავად სატელეფონო წიგნი, გააცნობიეროს, რომ არსებობს ამდენი სხვადასხვა ადგილას, სადაც ჩვენ შეიძლება მიმართოს მას. მხოლოდ Slap გარკვეული jargon - რეალურად, ვიდრე jargon პირველი, ნება მომეცით წასვლა ამ სურათს აქ. ამ დროისათვის ჩვენ ვისაუბრეთ N და N / 2 და შემდეგ შედით of n, მაგრამ შეგვიძლია თქმა ამუშავება, როგორც ჩვენ მეტი კურსი სემესტრის სხვა სახის მათემატიკური ფორმულები აღწერს ამ ზოგადი ცნება ქრონომეტრაჟი. ეს არის გარეთ კონტექსტში, რადგან ჩვენ ვხედავთ, სანამ ხანგრძლივი ალგორითმები, რომ ეს რეალურად წარმოადგენენ. 

მაგრამ შეამჩნევს აქ ხაზოვანი ხაზი N, სწორი ხაზი, არის ძალიან დაბალი მიუთითებს ახლავე. სწორედ ერთგვარი ოპტიკური ილუზია, რომ ჩვენ უბრალოდ შეცვალეთ რა x ღერძი წარმოადგენს და Y ღერძი და ჩვენ შეგვიძლია სწორი ხაზის წერტილი ნებისმიერი მიმართულებით გვინდა. მაგრამ იმ მიზეზით, რომ ეს ასე ჩანს, ბინა არის არის იმიტომ რომ ჩვენ საჭიროა რათა ოთახში ამ გრაფაში ამისთვის ბევრად ნელი გაშვებული ჯერ. ახლა ვიცი, რომ არსებობს საკმაოდ ცუდი ალგორითმები ცხოვრებაში, რომელთაგან ზოგიერთი არ იღებს N ნაბიჯები, ან კიდევ უკეთესი, შეხვიდეთ N ნაბიჯები, მაგრამ კიდევ უფრო. ამიტომ ხაზს ზემოთ n აქ ბოლოში გაფრთხილების არსებობს N ჯერ შესვლა of n, და ვნახავთ, რას ნიშნავს ადრე ხანგრძლივი. ზემოთ რომ არის n კვადრატში, და ჩვენ არ მინახავს არც ერთი N კვადრატში ალგორითმები გაუკეთებია, მაგრამ ჩვენ შესახებ. და რომ გამოიყურება მართლა ცუდია. არსებობს 2 დან N, რაღაც exponential, რომელიც გრძნობს უარესი. და მაინც, საინტერესოა, მაშინ არსებობს N cubed, რომელიც თუ თქვენ ერთგვარი ფიქრი ადრე, თუ სახის გავაკეთოთ მათემატიკის, 2 დან N რეალურად ხდება ბევრად straighter, ბევრად უფრო მაღალია, ვიდრე up n cubed თუ გადავხედავთ ცულები შორს საკმარისი აღმოჩნდა. ასე რომ შეამჩნია ახლავე ამ ცულები არიან თვითნებურად 2 დან 10 წლის x ღერძი. 

და რას ნიშნავს ეს? ეს იმას ნიშნავს, 2 ადამიანს 10 ადამიანი ოთახში. სულ ეს x საშუალებები: ზომა პრობლემა, რაც კონტექსტში. და ვერტიკალური ღერძი ახლავე არის რიცხვი, ან მთელი რიგი ზომების - ზოგიერთი ერთეულის დრო. მაგრამ შეამჩნია, რომ 0 დან 60 და 0 დან 10. მაგრამ თუ ჩვენ სახის დააშორებს, როგორც თქვენ შეიძლება Excel-ან დიაგრამების აწყობა პროგრამული უზრუნველყოფა, და ჩვენ ახვიდეთ 200,000 შეამჩნევთ, რომ რაღაც 2 დან N აპირებს მთლიანად overwhelm გაშვებული ჯერ N კვადრატში, N cubed, N შესვლა N - ყველაფერი ჩვენ ვისაუბრეთ დღემდე. და მაინც დაჭერა არის, როდესაც თქვენ დავიწყოთ ლაპარაკი რამ, როგორიცაა Facebook სადაც თქვენ ბევრი, ბევრი, ძალიან ბევრი ადამიანი ყველა ურთიერთდაკავშირებული, თქვენ არ n ადამიანი, თითოეული მათგანი შეიძლება იმდენი როგორც n მეგობრები თუ ყველას სახის buddy-buddy მსოფლიოში, კარგად, რომ N ჯერ N უკვე, ასე რომ n კვადრატში შესაძლო მეგობრობას, ყოველ შემთხვევაში 1 მიმართულებით, N კვადრატში შესაძლო მეგობრობას. ასე რომ უკვე ვარაუდობს, რომ ჩხრეკის Facebook სოციალური გრაფაში, ასე ვთქვათ, შეგიძლიათ დაიწყოთ უნდა გამოიხატოს ასეთი ფორმულები. 

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

მოდით ახლა გადავიდეთ შემდეგ ეს მაგალითი. ჩვენ ვნახეთ შონ ბრძოლაში ეს კამერა, ძალიან უხერხულად on video. მაგრამ რეალობა იყო, როცა შონ დაევალა მოძიებაში on მონიშნე მოსწონს ეს ნომერი 7, გავიხსენოთ, რომ მე ვთქვი, რომ "არსებობს სადღაც მიღმა ამ ცალი ქაღალდის ან თეთრი კარები "ნომერი 7. შონ, ის ჩვენთვის." და ეს იყო შესანიშნავად უხერხულია უყუროთ რადგან იგი მართლაც ბრძოლა ამ პრობლემის. მაგრამ რეალობა იყო შონ გააკეთა ასევე ვინმეს ოთახში შეეძლო. მან პატარა აღარ, ვიდრე ტიპიური პირი შესაძლოა, მაგრამ ის ვარაუდი, რომ გარკვეული შეასრულა ამ პრობლემას, მან აიღო, რომ მას აკლია რაღაც. და ეს არ დაეხმარება, რომ ასობით თვალები ნოტარიულად down on მას. 

მაგრამ რეალობა იყო თუ შეყვანის რომ პრობლემა არის bunch of შემთხვევითი ნომრები და თქვენ მიმდინარეობს სთხოვა მოძიების 1 ასეთი ნომერი, საუკეთესო შეგიძლიათ გააკეთოთ ხაზოვანი ძებნა. დაწყება at მარცხენა გადატანა უფლება, ან დაიწყება უფლება გადატანა მარცხენა. Retroactively, ჩვენ შეიძლება ფიქრი ", შონ, რატომ არ დავიწყო მეორე ბოლოს?" ისე, 7 შეეძლო ასევე ადვილად აქ შემთხვევით, მაგრამ მე შეგნებულად თქვა იქ რადგან I figured ის არ აპირებს დაიწყოს დასასრულს. ასე, რომ სახის მანიპულირება სიტუაცია, არამედ შემთხვევითი შანსი 7 შეიძლებოდა ყოფილიყო სადმე. ასე დაწყებული უფლება ბოლომდე შეიძლება უკეთესია, მაგრამ რა, თუ მომავალ წელს მე გადაადგილება 7 სხვაგან? ეს არ არის ფუნდამენტურად ახალი გადაწყვეტა პრობლემა - დაწყებული 1 ბოლოს ან სხვა - როდესაც თქვენ და საერთოდ არ სხვა ვარაუდები. ასე შონ დაიწყო გადახედეთ ნომრები და განაცხადა მან, "5. ეს არ აქ." შემდეგ იგი წავიდა აქ და ვნახე 19, მაშინ ის ათვისება დაახლოებით 20 წამი, შემდეგ მან გახსნა ეს 13, და შემდეგ ნათელი გახდა რომ იქ არ ჩანს, ეს ნიმუში აქ. ეს არ იყო 1, 2, 3, 4 ან ანალოგიური. იყო ხარვეზები ციფრები, რომლებიც არ უშველა. და ძალიან, ის ფაქტი, რომ მე გამოიყენება ამ იაფი ცალი ქაღალდის რათა დაფაროს ნომრები ფაქტიურად მიზანმიმართული, რადგან თუ მე ამოღებულ ყველა ამ ცალი ქაღალდის, ყველაზე მეტად ჩვენს შონ შედის, ალბათ არ მოხვდა სახის macroscopically ზე დაფაზე და თქვა: "ოჰ, 7 აშკარად უფლება არსებობს." ჩვენ ეს გავაკეთეთ მყისიერად. 

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

ასე რომ, ყველა სხვა საიდან შეიძლება ასევე იყოს დაფარული რაიმე ნაჭერი ქაღალდი იმიტომ, რომ ჩვენ ვერ ვხედავთ მაინც. ჩვენ შეგვიძლია მხოლოდ 1 რამ დროს. ასე რომ ამ შემთხვევაში, შონ საქმე, წავედით აქ და მერე წავედით აქ და მერე წავედით აქ, აქ, აქ, აქ, მიიღო ჭკვიანი ბოლოსთვის და მხოლოდ სახის გამოტოვებენ ამ ერთი თვითნებურად და ნაპოვნია 7 არსებობს. ეს ერთი არ იყო განსაკუთრებით სპეციალური. ეს ძალიან იყო მწყობრიდან. მაგრამ მან საბოლოოდ ნაპოვნია 7. მაგრამ ახლა takeaway მართლაც რომ საუკეთესო შეგიძლიათ გააკეთოთ, როდესაც მოცემული ინფორმაცია არ არის გარდა შემთხვევით დახარისხებული ციფრები უნდა დაიწყოს მარცხნიდან ან დაიწყება უფლება. ან heck, შეგიძლიათ შემთხვევით გახსენით კარები, მაგრამ მაშინაც რას ნიშნავს უნდა იყოს შემთხვევითი? ისე, ჩვენ გვინდა უნდა როგორღაც formalize რას ნიშნავს დაიწყოს აქ, მერე აქ, მერე აქ. შონ გააკეთეს დიდი, და ეს მხოლოდ გართობა უყუროთ. რა მოხდება, თუ ნაცვლად შევცვლით პრობლემა ცოტა და ზრდიან ამ წლის შონ, თუ გნებავთ? რომ ვინმე იყოს კომფორტული ახლოვდება სცენაზე და გადაჭრის ოდნავ განსხვავებული პრობლემა და გამოჩენა კამერა? 

მოდით სცილდება ორკესტრი იმიტომ, რომ თქვენ ბიჭები უკვე საკმაოდ ჩართული დღეს უკვე. როგორ შესახებ წელს ვარდისფერი, წელს ქუდი? Come on ქვემოთ. რა არის შენი სახელი? >> ალექსი. >> ალექსი. Okay. ასე რომ ალექს იქნება ამ წლის შონ და გამოჩნდება შემდეგი რამდენიმე წლის ღირებულების CS50 ლექციებს. ალექს, კარგია თქვენთან შეხვედრა. >> Nice შეხვდება თქვენც. გამოწვევა ხელთ თქვენთვის არის, რომ თქვენ გაქვთ ცოტა ადვილი ამ მე გეუბნებოდით იგივე ციფრები აქ, მაგრამ ისინი ახლა დახარისხებული. ახლა თქვენი მიზანია ვიპოვოთ ნომერი 7. და ფაქტობრივად, ჩვენ უნდა ნამდვილად რომ ეს - you're სახის მოტყუების, როგორიცაა კომპიუტერი არა, მიერ ეძებს რა ციფრები იყო მომენტი წინ. With ცარცის ამ რეალურად არ აპირებს დაეხმაროს ყველა რომ ბევრი რამ, მაგრამ მოდით ვიტყვი, რომ თქვენ არ იცით, რა ორიგინალური წყობა. ყველა თქვენ იცით ახლა ის არის, რომ თქვენ გაქვთ მასივი დახარისხებული ნომრები რომ შესაძლოა ხარვეზები, მათ შორის, და თქვენი მიზანია ვიპოვოთ ნომერი 7. რა, გონივრული ადამიანის, წასვლა დაახლოებით მოძიებაში ნომერი 7? 

გადასვლა დაბლიდან მაღალი? >> Okay. გადავიდეთ დაბალი მაღალი. და არ გაანადგურეს ისინი. მოდით უბრალოდ გააუქმოს ისინი ასე შეგვიძლია reuse მათ. Okay, ასე 1. დაელოდეთ. სანამ შენარჩუნებას აპირებს, რომ იყო 1, აშკარად არასწორია. ასე რომ, რა ხდება საშუალებით თქვენი გონება შემდეგი? რა არის თქვენი მომავალი ნაბიჯი? შემდეგი ერთი. >> Okay. შემდეგი ერთი. კარგი. 3, ასე რომ არასწორია. რა არის თქვენი მომავალი ნაბიჯი? შეინახეთ მიმდინარე. >> ყველა უფლება. შეინახეთ მიმდინარე. 5. გააგრძელეთ მიმდინარე და ნება მომეცით გადასცემს თქვენ ამ შთამომავლობას. 7. >> შესანიშნავი. ძალიან კარგი. ნაპოვნია ნომერი 7. [ტაში] ასე რომ კარგი იყო, მაგრამ შონ ძალიან ი ნომერზე 7. მე ამტკიცებენ, რომ თქვენ არ ნამდვილად ისარგებლა ამ დამატებითი ნაჭერი ინფორმაციას, რაც არის, რომ ეს ციფრები დახარისხებული. ასე გავაკეთოთ უკეთესი? რაიმე შემოთავაზება აქ? ჰო, წელს უკან. [სტუდენტი] ორობითი ძებნა. >> არ ვიცი რა ორობითი ძებნის. 

[სტუდენტი] დაწყება შუა. >> დაწყება შუა. Okay. მოდით ვნახოთ, თუ შევძლებთ იქ. ასე რომ, თუ ნაცვლად თქვენ განუცხადა იწყება შუა, წავიდეთ წინ და ქმნის შუა კარი. არსებობს 8 მათგანი, ასე რომ თქვენ აპირებთ უნდა თვითნებურად აირჩიოს ერთი ოდნავ მარცხნივ ან მარჯვნივ. Okay. 7! [ტაში] ძალიან ლამაზი. Okay, მაგრამ სადაც ჩვენ ვაპირებთ ამ? დავუშვათ უბრალოდ შესვენება ჰალსტუხი თქვენ დაიწყო აქ იმიტომ, რომ თანაბრად შეიძლება მომხდარიყო, ისევე. ჩვენ უბრალოდ მოხდა ვიცით, რომ 7 იყო. ასე რომ, ეს არის 13. ასე რომ, თუ ისინი დახარისხებული და ჩვენ უბრალოდ დაიწყო ახლო, რა ოპტიმალური შემდეგი ნაბიჯი უკვე? ზემოთ მარცხენა. და ა.შ. აქ მოდის სატელეფონო წიგნი მაგალითად ერთხელ. თუ 13 აქ არის და ჩვენ ვიცით სია დალაგებულია, მაშინ ყველა ამ ცალი ქაღალდის არიან uninteresting ჩვენთვის არის იმიტომ, რომ ჩვენ უკვე ვიცით, რომ 7 უნდა იყოს მარცხენა თუ ეს ციფრები დახარისხებული და აღმოვაჩინეთ 13. 

რა არის თქვენი შემდეგი ნაბიჯი აქ? >> გადადი მარცხენა. >> Okay, კარგი. ასე მარცხნივ, და - დაველოდოთ, Hey, Hey, Hey. რომ პატაშური. ასე რომ თქვენ ი 7, მაგრამ რა იყო ალგორითმი ჩვენ უბრალოდ გამოიყენება? დაწყება შუა. >> კარგი. რა არის ლოგიკური გაგრძელების იმავე იდეას? ოჰ, მხოლოდ ამ. >> ზუსტად. >> ასე რომ დავიწყოთ აქ. >> კარგი. ახლა წავედით ოდნავ მარცხნივ ისევ. ეს 3. მაგრამ საინტერესო takeaway ახლა არის რაც ერთი თუ არ აინტერესებს? ეს 2. >> ეს 2. ახლა ამ ადამიანს შეუძლია წავიდეს, ეს შეიძლება წავიდეს. არის პრობლემა, რომელიც იყო 8 მაშინ იყო ზომა 4 ახლა არის ზომა 2. ჩვენ ვიღებთ საკმაოდ ახლოს. ერთხელ, წასვლა შუა ამ 2 ელემენტებს. 

Okay. ასე რომ სახის სამწუხაროა, რომ ახლა ჩვენ მუდმივად მიმდინარეობდა დაუტოვებიათ რადგან ჩვენ დამრგვალება ქვემოთ. მაგრამ ეს ჯარიმა, რადგან ახლა ჩვენ გადაყარეთ ამ მოშორებით და ყველაფერი, რის გამოც ჩვენთვის მხოლოდ 7. მოდით მივცეთ რაუნდი ტაში. ჩვენ ვნახეთ 7 ერთხელ. [ტაში] Okay. დარწმუნებული. Hang on მხოლოდ 1 მეტი მეორე. მიუხედავად იმისა, რომ შემდეგი პროცესი სახის აიღო პატარა აღარ, ვიდრე ჩვენ გრძნობდა ხოლმე, გულწრფელად, თქვენი პირველი ინსტინქტები იყო საუკეთესო, არა? ჩვენ ვნახეთ 7 მომენტალურად. მაგრამ ჩვენ რომ არ ი 7 უფრო სწრაფად, არ აქვს მნიშვნელობა, რა, ამ მაგალითში წინააღმდეგ ამ ერთი რადგან თუ ციფრები ყველა დახარისხებული, ჰგავს გვერდების სატელეფონო წიგნი, შეგიძლიათ მართლაც Chop ნახევარში პრობლემა ისევ და ისევ და ისევ. და ეს არ არის საკმაოდ მარტივი, რომ ეს მხოლოდ 8 ნომრები როგორც ეწინააღმდეგებოდა 1000 გვერდი სატელეფონო წიგნი, სადაც თქვენ ნამდვილად ჩანს ვიზუალურად, მაგრამ ამ შემთხვევაში აქ როცა შონ იყო ეძებს 7, რამდენი ნაბიჯები უარეს შემთხვევაში უნდა ჰქონოდა მას? >> [სტუდენტი] 7. 7 ყველაზე ცუდ შემთხვევაში. ისე, ყველაზე ცუდ შემთხვევაში არ 7 თუ არა 8 კარი აქ. ეს იქნებოდა მიღებული მისთვის 8 ნაბიჯები. 

ასე რომ, თუ არსებობს N კარები, მას ჰქონოდა შონ რამდენიმე წლის წინ N ნაბიჯები. ახლა კი, თქვენი საქმის, ალექსი, თუ გავითვალისწინებთ, რომ ეს ციფრები დალაგებულია - და ჩვენ შეგვიძლია სახის infer ამ საიდანაც ჩვენ დღემდე ამ სიუჟეტი - რა ქრონომეტრაჟი ალექს ბევრად უფრო ინტელექტუალური ალგორითმი დაწყების შუა და შემდეგ იმეორებს? [სტუდენტი] 3. >> ამიტომ იქნება 3, უხეშად, თუ თქვენ გადასვლა 8 დან 4 დან 2 მდე 1. ასე 3 ნაბიჯები ან, უფრო ზოგადად, რომ შესვლა n ერთხელ. ნებისმიერ დროს თქვენ საჯელის განახევრებას და საჯელის განახევრებას და საჯელის განახევრებას და საჯელის განახევრებას, რომ გამოხატვის ამ იდეას შესვლა n. და ასე რომ აქვთ აღებული თქვენ მხოლოდ 3 ნაბიჯებს, და მართლაც ასე იყოს ერთხელ გავხსენით კარები საჯელის განახევრებას და საჯელის განახევრებას, ხოლო ამ იქნებოდა მიღებული შონ დაახლოებით 7 ან 8 ნაბიჯები. მადლობას მოგახსენებთ იმისთვის, რომ ჩვენთან ამ წელიწადში. >> გმადლობთ. Nice შეხვედრა თქვენ. გმადლობთ, რომ ალექსი. >> ანალოგიურად. [ტაში] 

რა არის მაშინ რეალური გავლენა ამ? ახლა წარმოიდგინეთ, რომ ის 8 კარი, რომელიც, სიმართლე გითხრათ, ყველა ჩვენგანის იპოვა რაღაც უკან 8 კარები საკმაოდ სწრაფად მხოლოდ tearing ცალი ქაღალდის და ვაპირებთ ჩვენს ინსტინქტებს. მაგრამ მერე რა, რომ მილიონი კარები? მერე რა, რომ 4 მილიარდი კარები? იმ შემთხვევაში, თუ 4 მილიარდი კარები, თქვენ მართლაც აპირებს მინდა დავუკავშირდეთ Alex-ს ალგორითმი, ორობითი ძებნა როგორც დავიწყებთ უწოდა ან გათიშე და დაიპყროთ, ზოგადად, აქ თქვენ გაქვთ საჯელის განახევრებას და საჯელის განახევრებას პრობლემა, რადგან თუ თქვენ გაქვთ 4 მილიარდი კარები, რამდენჯერ შეგიძლიათ Chop 4 მილიარდი ნახევარი? [სტუდენტი] 32. >> სინამდვილეში 32. თქვენ შეგიძლიათ იმუშაოთ ამ წლის ნაჭერი ქაღალდი ან თქვენს უფროსს. თქვენ გადასვლა 4 მილიარდი 2 მილიარდი 1 მილიარდი ნახევარი მილიარდი, რომ 250 მილიონი აშშ დოლარი, dot, dot, dot. და თუ გარეთ მათემატიკის, თქვენ აპირებს მართლაც მიიღოს 32, და რომ რეალურად ეხება კომპიუტერული მეცნიერებისა რადგან ჩვენ, როგორც წესი, დათვლის უფლებამოსილება 2. 2 დან 32 ხდება იქნება 4 მილიარდი. ასე რომ არსებობს ბევრი შესაბამისობა ამ სახის უფლებამოსილება 2 კომპიუტერულ მეცნიერებაში. 

მაგრამ რა დაახლოებით 8 მილიარდი? რამდენი ნაბიჯების რომ აპირებს თუ არსებობს 8 მილიარდ კარები? [სტუდენტი] 33. >> ასე 33. რა მოხდება თუ არსებობს 16 მილიარდი კარები? რამდენი ნაბიჯების რომ აპირებს? [სტუდენტი] 34. >> 34. ჩვენ შეგვეძლო სახის გაგრძელდება განცხადებაზე nauseam. მაგრამ ამით ძლიერი რამ. შეგიძლიათ გააცნობს მილიარდობით უფრო საშუალებებით თქვენს პრობლემა, მაგრამ, არ დიდი გარიგება, უბრალოდ მიიღოს 1 დამატებითი bite გარეთ და ამით გვაძლევს რაღაც ორობითი ძებნა ან გათიშე და დაიპყროთ, უფრო ზოგადად. მაგრამ მე სახის პატაშური აქ, არა? იმ შემთხვევაში, ალექს ს ალგორითმი, მას უპირატესობა შონ. მან იცოდა, რომ ეს ციფრები იყო დახარისხებული, მაგრამ ალექს არ უნდა დასალაგებლად მათ თავად. მე წინასწარ მოვიდა დაფაზე და სახის გააკეთა დარწმუნებული რომ მე მიიპყრო მათ ყველა გარეთ დახარისხებული მიზნით, მაშინ მე დაფარული მათ ქაღალდზე. თუმცა, რამდენად მუშაობა საერთოდ რომ Take Me? თუ ჩვენ დაიწყო off ერთად ამ ნომრებზე ზოგიერთ შეხედვით შემთხვევითი მიზნით - ამ შემთხვევაში ეს უფრო მარტივი რიცხვები, 1 მეშვეობით 8 აქ - როგორ უნდა წავიდეს შესახებ დახარისხება ამ ღირებულებებს? თუ იყო ადამიანის მოცემული ამ ამოცანის, რა სახის ინტუიციური მიდგომა იქნებოდა თუ არა to დახარისხება მთელი bunch of ციფრები? ეს ყველაფერი იყო ასახული, როგორც თავსატეხი ცალი. Yeah. 

[სტუდენტი] მინდა მიიღოს თითოეული ნომრის და შეადაროთ იგი თითოეული შენარჩუნებას და აპირებს მარცხნივ. >> Okay, კარგი. ასე რომ მიიღოს თითოეული ნომერი, შეადაროთ იგი ერთი შემდეგი მას, და მაშინ უბრალოდ შეინახოს მოძრავი გასწვრივ სიაში, სახის rejiggering რამ როგორც თქვენ გადასვლა. ასე რომ აქ გვაქვს შანსი იქნებ კიდევ რამდენიმე FOLKS ჩაერთოს. გვაქვს 8 მეტი მოხალისეები ვინც რომ მიყვარს ამუშავება? ცოტა ნაკლები ზეწოლა რადგან თქვენ არ მხოლოდ ერთი. 1, 2, 3, 4, 5, 6, 7, 8. Come on ქვემოთ. თქვენ ბიჭები ვაპირებთ იყოს ციფრები 1 მეშვეობით 8. ვნახოთ, შევძლებთ თუ არა ამის გაკეთება დახარისხება ამისთვის ალექს გაცილებით ისევე მე ეს წინასწარ. 1, 2, 3, 4. წავიდეთ წინ და თუ, გამოდიან სცენაზე შორის მუსიკა სტენდი და მე აქ იმავე მიზნით, როგორც slide ეკრანზე. Uh-Oh. ჩვენ ვიმუშავებთ თქვენ შევიდა შემდეგი მაგალითი. ოჰ, დაველოდოთ, დაველოდოთ. Here We Go. დაელოდეთ. შემდეგი მაგალითი არის. აი ისიც. ხმების 8. Come on up. ყველა უფლება. დალაგების თქუენგან მიხედვით ამ. Slide უბრალოდ ცოტა იმ მხარეს მუსიკა დავდგეთ აქ. ასე რომ, ჩვენ გვაქვს 4, 2, 6 - მიიღონ იქ, მეტი აქ, უფლება არსებობს - 3. Yeah. Okay. თქვენ გადასვლა ზე მეტი აქ. არა, თქვენ იქ. ჰო, უფლება არსებობს. მე ვარ არასწორია. უფლება არსებობს. Okay, ძალიან კარგი. Okay. ახლა მოდით დასალაგებლად მათ იზრდება ბრძანებით. 

როგორ შემიძლია წასვლა შესახებ ამით? ალგორითმი, რომ შემოთავაზებული იყო მომენტში წინ იყო, რატომ არ ვართ, უბრალოდ შევადარებთ FOLKS რომლებიც სახის შემდეგი ერთმანეთს და შემდეგ დააფიქსირონ ნებისმიერი შეცდომები, მოძრავი მარცხნიდან მარჯვნივ. ასე რომ აქ გვაქვს 4 და 2, აშკარად მწყობრიდან. მოდით სვოპ თქვენ. Okay. ახლა მე ვაპირებ ქვევით ხაზი. 4 და 6, nope. [სიცილის] 6 და 8, საკმაოდ კარგი. 8 და 1 ნება მიბოძეთ, სვოპ თქვენ ბიჭები. ყველა უფლება. ასე რომ 8 და 3, სვოპ თქვენ ბიჭები. 8 და 7, ნება მომეცით სვოპ თქვენ ბიჭები. 5 და 8, შესანიშნავი. მე გაძლევთ დახარისხებული სია. ყველა უფლება. ასე რომ არ საკმაოდ. მაგრამ სჯობს, რადგან უფრო დიდი ციფრები, - მაგალითია 8 - არ სახის bubbled მდე მარცხენა მეტი უფლება. ამიტომ მე მივიღე 1 მათგანი უფლება, მაგრამ ეს იგრძნობა ამ არ საკმაოდ პრობლემის მოგვარებას. 

ასე რომ რას შესთავაზოს გავაკეთოთ შემდეგი? >> [სტუდენტი] ნუ ვაკეთებთ. >> ჩვენ გვაქვს ვაკეთებთ. და გააცნობიეროს, კიდევ ერთხელ, ჩვენ დავსახეთ რამ მიერ მხოლოდ მქონე ყველა ადამიანისა სახის ჭკვიანურად მოწყობა თავად ეფუძნება, რომ სურათი, მაგრამ ახლა ჩვენ უფრო მეთოდური. ჩვენ უნდა ვიყოთ ალგორითმული ამის შესახებ, თითქოს ჩვენ წერილობით კოდი - ამ შემთხვევაში სიტყვიერი pseudocode. ნება მომეცით, სცადეთ რომ ერთხელ. რომ მუშაობდა კარგად. ეს არ გადაჭრის იგი. მაგრამ როდესაც ეჭვი, სცადეთ და სცადეთ კიდევ ერთხელ. ასე რომ 2 და 4, არ უშველა უქმნით. 4 და 6. Ah! 6 და 1, ოდნავ უკეთესი არის. 6 და 3, კარგი. 6 და 7, 7 და 5, 7 და 8, კარგი. და თქვენ იცით, მე ალბათ შეუძლია იგნორირება 8 არის, რადგან ის დასასრულს სიაში. იქნებ ჩვენ არ გვაქვს ფიქრი ვინმე აპირებს წარსულში მას. მაგრამ ვნახოთ, თუ რომ უსაფრთხო ვარაუდი. ახლა სია - Damn - არ დახარისხებული. მოდით ვეცადოთ ეს კიდევ ერთხელ. ასე რომ 2 და 4, 4 და 1, 4 და 3. 4 და 6, კარგი. 6 და 5, კარგი. 6, 7, 8 და, კარგი. მაგრამ ცნობა, შემიძლია მხოლოდ შეწყვიტოს აქ არის და შეწყვიტოს აქ არის? [სტუდენტი] დიახ. >> Yeah? რა მოხდება, თუ ერთი თქვენგანი იყო ნომერი 9 ყველა გზა იქ? ეს იქნებოდა დახარისხებული. >> კარგი. ეს იქნებოდა დახარისხებული პირველად გარშემო. კარგი. მოდით დავუბრუნდეთ ისევ. ჩვენ თითქმის იქ. 1 და 2, 2 და 3, 3 და 4, 4 და 5, 5 და 6, 6 და 7, 7 და 8. 

მე კეთდება ახლა მაგრამ, ისევ, მე კომპიუტერი, რომელიც მხოლოდ რა მე მითხრეს, რომ გააკეთოს, და ჩემი ერთადერთი მოგონებაა ახლა ის არის, რომ მე რეალურად მხოლოდ გააკეთეს ცოტა მუშაობა. რაღაც შეცვლილა. ასე რომ მე არ ტექნიკურად დაადასტურა ვიზუალურად ან algorithmically რომ ამ სიაში მართლაც დახარისხებული. ასე რომ მხოლოდ კარგი ღონისძიება, უბრალოდ უნდა იყოს anal შესახებ, მოდით ეს 1 მეტი დრო. ასე რომ 1 და 2, 2 და 3, 3 და 4. და თქვენ იცით, რა ხდება? მხოლოდ კარგი ღონისძიება, მე ვაპირებ შენარჩუნება სიმღერა ჩემს მხრივ, ეს დრო რამდენი სვოპების მე მხოლოდ ისე, რომ მე ვიცი, რამდენად იმუშავებს მე კეთდება. 3 და 4, 4 და 5, 5 და 6, 6 და 7, 7 და 8. არარის გაცვლებს. ახლა მინდა ლეგიტიმურად იყოს იდიოტი, რომ ეს კიდევ ერთხელ გავაკეთოთ რადგან მე რომ არ მუშაობდა ამ უღელტეხილზე ადამიანები, მაშინ ნათლად რომ აპირებს განმეორდეს, თუ არც ერთი მათგანი არ არის ერთგვარი შემთხვევით adversarially მოძრავი თავად გარშემო. ახლა შემიძლია შეწყვიტოს. ახლა მოდით ვთხოვოთ კითხვაზე, რამდენად მუშაობა ეს პრაქტიკულად me? რამდენი ნაბიჯები საერთოდ რომ მიიღოს? >> N კვადრატში. ჰო, ისე N კვადრატში. სად იღებთ N კვადრატში საწყისი? თქვენ უნდა შეამოწმოთ თითოეულ num - არსებობს N ციფრები, და თქვენ უნდა შეამოწმოთ თითოეული ნომერი სხვა N ნომრები. კარგი. >> ამიტომ n კვადრატში. >> კარგი. 

ასე რომ იგრძნობა ეს შეიძლება ძალიან კარგად იყოს N კვადრატში, არა? აქ ნ ეს ბიჭები, 8 კონკრეტულად ამ შემთხვევაში, მაგრამ ყოველ ჯერზე, მე გაიარა ამ სიაში მე შედარებით პირველი პირი წინააღმდეგ მეორე, მეორე წინააღმდეგ მესამე ისევ და ისევ და ისევ, და როცა ბოლომდე, რა გავაკეთო? მე redid იგი. ასე რომ, თუ ჩვენ განზოგადება ამ განმარტებით, ჩვენ n ხალხი და მე მიღების, ცხადია, 8 ნაბიჯები, N ნაბიჯები, ყოველ ჯერზე მე გავლა ეს ალგორითმი. მაგრამ როგორ ბევრჯერ უარეს შემთხვევაში უნდა გაიაროს ამ სიაში ხალხს? [სტუდენტი] N ჯერ. >> ალბათ N, უფლება, რადგან უარეს შემთხვევაში, რა ალბათ უარეს შემთხვევაში მოწყობა ამ ბიჭებს საწყისი მიიღოთ-go? თუ ისინი სრულიად საპირისპიროა მიზნით რადგან მხოლოდ ვივარაუდოთ გონებრივად, let's - რა არის თქვენი სახელი? >> Bowen. Bowen. Okay. ამიტომ Bowen, მოდის, აქ მხოლოდ ერთი წუთით. 

ვარაუდობენ, რომ Bowen იყო აქ დასაწყისში ალგორითმი, და ჩვენ არ ვიცით, რა ყველას არის, მაგრამ აქ Bowen თანახმად, ეს ალგორითმი - და თუ გნებავთ უბრალოდ სეირნობა ჩემთან - აპირებს ბუშტი up, როგორც მან პირველად გარშემო, ყველა გზა ბოლომდე. მაგრამ ვარაუდობენ, რომ პირის შემდეგ Bowen იყო ნომერი 7. მე უნდა დაბრუნდეს და მიიღეთ ნომერი 7, რაც იმას ნიშნავს, მე უნდა წავიდეთ ყველა გზა უკან აქ. ახლა კი უნდა ჰქონდეს, რომ იგივე სეირნობა ერთად პირს, რომელიც ხმების 7. მაგრამ რა, თუ შემდეგ ნომერზე 6 იყო შემდეგი მისთვის ისევე? მაშინ მე უნდა დაბრუნდეს და კიდევ 6. ასე რომ კიდევ ერთხელ, ყოველ iteration ამ loop ვსაუბრობ თითოეულ N ადამიანი, და ალბათ უნდა გააკეთოთ n ამ სეირნობა რომ დავრწმუნდეთ მე გამწევ ყველა უმსხვილესი ელემენტების უკან და უკან და უკან, ძალიან სიის ბოლოში. ამიტომ N რამ N ჯერ მხოლოდ N ჯერ n ან N კვადრატში. 

ასე რომ აქ უკვე გვაქვს ალგორითმი რომ აღარ N, რომ აღარ შესვლა N, სინამდვილეში უარესი არაფერი ჩვენ გავაკეთეთ ადრე. ასე რომ ალექს სახის მიიღო გაუმართლა, რომ მე ყველა სამუშაო სავარაუდოდ up წინა მისთვის, ყველა ძვირი მუშაობა, რათა მან შეიძლება ისარგებლოს ამ ბინარული ძებნის ალგორითმი, რაც შესვლა of n. მაგრამ ეს შეესაბამება ორშაბათს თემა. მივეცით ცოტა მეტი სივრცე, ჩვენ გამოყენებული მეტი ბიტი, რათა დაჩქარდეს ჩვენი გაშვებული დრო. ასე ჰგავს არსებობს ამ შორის ვაჭრობის დრო და სივრცე, შეიძლება ასევე მხოლოდ ვაჭრობის ღ შორის გატარებული დრო up წინა სახის მიღების რამ მზად ვართ წავიდეთ და ფაქტობრივად შესრულებაში ალგორითმი მოსწონს ძებნა. მოდით ვეცადოთ კიდევ ერთი. თუ ბიჭები არ იბადება უბრალოდ სწრაფად rearranging თქუენგან ემთხვევა, რომ კიდევ ერთხელ, მოდით ძიებასა ოდნავ განსხვავებული, სადაც ეს არ საკმაოდ მარტივია როგორც მხოლოდ დაფიქსირება ყველა pairwise შეცდომები, რაც სუპერ ინტუიციური. მოდით ნაცვლად იყოს უფრო მიზანმიმართული და ამის გაკეთება. ეს ერთი ძალიან მინდა შესთავაზოს ალბათ საკმაოდ ინტუიციური. 

მოდით აირჩიეთ პატარა პირის სიიდან ისევ და ისევ. ასე რომ აქ ჩვენ მივდივართ. 4, თქვენ პატარა პირი მე რითაც ჩანს ჯერჯერობით ამიტომ მე ვაპირებ სულიერად გვახსოვდეს, რომ მხოლოდ მიუთითებს თქვენ ახლა. 2. Ooh! დაივიწყეთ ნომერი 4. მე უბრალოდ ი ახალი პატარა ელემენტს ამ სიაში. მე ვაპირებ სახის გვახსოვდეს, რომ. 6, 8. Ooh! 1. Goodbye. ახლა მე ვაპირებ გვახსოვს ნომერი 1. ჩვენ ვიცით, რომ 1 არის ყველაზე მცირე, მაგრამ მე კომპიუტერში. რა მოხდება თუ არსებობს 0? რა მოხდება თუ არსებობს -1? მე შენარჩუნება აპირებს. ასე რომ 3, 7, 5, nope. Okay. ამიტომ ნომერი 1 იყო პატარა. ნება მომეცით აირჩიეთ თქვენ სიიდან - we'll ამ გზით - და ამით თქვენ თვითნებურად დასაწყისში სიაში. ახლა დაველოდოთ წუთში. I ტიპის იწყებენ. თუ ეს ბიჭები წარმოადგენენ არა სიაში 8 ადამიანი მაგრამ მასივი, 8 მოცულობით მიმდებარე მეხსიერება - თქვენ იბადება სტეპინგზე უკან მხოლოდ ამ მომენტში? არსებობს რეალურად არ სივრცე თქვენ უფლება აქ. ასე როგორ უნდა გააკეთოს ფართი - რა გქვია? >> Sammy. >> Sammy. როგორ ვაწარმოებთ ფართი Sammy? 

ჩვენ გადაადგილება N, რომლებიც ჩემ წინაშე. >> Okay. ამიტომ ვერ გადავა N ადამიანები, რომლებიც მის წინაშე, ასე რომ, თუ თქვენ ბიჭები სურს 1 მიზანმიმართული და დრამატული ნაბიჯი მარცხნივ. ისინი ყველა გააკეთეს, რომ უნისონში, მაგრამ ბოლო დროს დავწერე რაღაც კოდი, ვერ სახის გადაადგილება ბევრი რამ ერთდროულად. ჩვენ შეგვეძლო ამას მარყუჟის, მოძრავი ყველას ერთხელ დროს. ასე რომ, თუ თქვენ ბიჭები არ იბადება სტეპინგზე თავში უფლება, და Sammy, თუ შეიძლება უკან დახევას, რადგან იქ მაინც არ ოთახი თქვენთვის, ახლა მოდით ეს. სად იყო Sammy მომენტში წინ? უფლება არსებობს. ასე რომ არსებობს შეუსაბამობა არსებობს. ასე, რომ თქვენ შეიძლება გადაინაცვლოს Sammy ნახვა ადგილზე. ახლა შემდეგი პირი up და ახლა შემდეგი პირი, ახლა შემდეგი პირს. ახლა ჩვენ გვაქვს ოთახში Sammy. ახლა, ვინმე აუდიტორიის - ეს იყო კარგი, რომ იყო ზუსტი, ეს იგრძნო პატარა შრომატევადი - რა სწრაფად? Yeah. [სტუდენტი] ახალი მასივი? >> რა არის რომ? >> [სტუდენტი] ახალი მასივი? >> Okay, კარგი. 

ასე რომ შეესაბამება ამ თემაზე მხოლოდ ვაჭრობის ღ, რატომ არ მე უბრალოდ მიიღოს ახალი მასივი  და შემდეგ Sammy იქნება საცურაო სივრცეში წინაშე ეს ადამიანები, მაგალითად, და ჩვენ შეგვიძლია დავიწყო შევსების ახალი array საერთოდ. რომ ძალიან იმუშავებს. მაგრამ მე არ აინტერესებს ხარჯვის მეტი სივრცე დღეს. რა არის კიდევ ერთი მიდგომა? [სტუდენტი] სვოპი. >> Okay. ჩვენ შეგვეძლო მხოლოდ სვოპ ამ 2 guys. რა არის შენი სახელი? Mario. >> Mario. ამიტომ Mario, იყავით გაკეთებული აქ. Sammy, შეგიძლიათ უკან up მხოლოდ ამ მომენტში? მარიო იყო აქ. ჩვენ არ გვაქვს ოთახში თქვენ აღარ ასე რომ, თუ თქვენ არ იბადება აპირებს, სადაც Sammy არის, ჩვენ დააყენა Sammy აქ და ახლა მინდა ამტკიცებენ, რომ Sammy ს შევცვალე ოპერაცია იყო ბევრად უფრო სწრაფად. ჩვენ 1 ოპერაცია სვოპ ამ ბიჭებს, ან იქნებ 2 to სვოპ ამ ბიჭებს, მაგრამ ჩვენ არ 1, 2, 3, 4, ისე, რომ თავს კარგად გრძნობს. ახლა დაველოდოთ წუთში. I ტიპის გააკეთა პრობლემა უარესი იმიტომ ნომერი 4 იყო სახის ახლოს დასაწყისია. ახლა ნომერი 4 არის პატარა დაახლოება ამ მიზნით, მაგრამ მე არ ვიცი ან აინტერესებს, რომ. ასე რომ, ეს უბრალოდ ცუდი იღბალი რომ ნომერი 4 არის ოდნავ მოშორებით დაშორებით თავისი განკუთვნილი ადგილი. მოდით ახლა ვიმეორებ ეს ალგორითმი. 

To recap, რადგან, რომ ამბავი იყო, ყველა ჩვენ არ იყო გავლა სია ეძებს პატარა დანომრილი პირი. ახლა მოდით ეს კიდევ ერთხელ. ჩვენ არ გვაქვს ფიქრი Sammy უქმნით. ჩვენ შეგვიძლია უბრალოდ აქ. Ooh! ხმების 2. სწორედ საკმაოდ მცირე რაოდენობით. 6, 8, 4, 3, 7, 5. Okay, კარგი. და საბედნიეროდ, დაემთხვა, მე არ უნდა გადავიდეთ - >> Willie. Willie რადგან ის თავის ადგილს მიუჩენს ახლა. მოდით ეს კიდევ ერთხელ გავაკეთოთ და იგნორირება ამ 2 guys. 6. სწორედ საკმაოდ მცირე რაოდენობით. Ooh! 8 ნამდვილად დიდია. 4. მოდით ფოკუსირება 4. Ooh! 3 არის უფრო უკეთესი. 7 და 5. ასე რომ რას ვაკეთებთ ახლა - >> როჯერ. >> როჯერ? მოდით სვოპ მას ხმების 6. ასე რომ, თუ 6 და 3 მინდა სვოპ, ჩვენ ახლა სახის მიღებული გაუმართლა, რომ 6 უფრო ახლოსაა, სადაც იგი უნდა იყოს, მაგრამ ეს მხოლოდ დამთხვევა აქ. მოდით ეხლა აქ. 8 არის საკმაოდ მცირე რაოდენობით. Ooh! 4 პატარაა. 6, 7, 5. რას ახლა? >> სვოპი. >> ზუსტად. ახლა მოდით ეს ერთგვარი სწრაფად. 8, 6, 7, 5. სად 5 წავიდეთ? კარგი. Okay. 6, 7, 8. 6 იღებს დარჩენა, სადაც ის არის. რა არის შენი სახელი? >> Rosalie. Rosalie იღებს დარჩენა, სადაც ის არის. 7 იღებს - ვნახოთ. 7, 8. Okay. ასე რომ 7 იღებს დარჩენა, სადაც ის არის. რა არის შენი სახელი? >> Amna. >> Amna. 

ამიტომ Amna იღებს დარჩენა, სადაც ის არის, და ნომერი 8 უკვე სადაც ახლა უნდა იყოს. Okay, კარგი. მიდრეკილება ჩვენ უბრალოდ შექმნის სამუშაოები ვდებთ აქ, თუმცა. რა არის საბოლოოდ ქრონომეტრაჟი ამ ალგორითმი? თუ ჩვენ ვფიქრობ ამ ადამიანებს არა როგორც 8 მაგრამ, როგორც N? >> ეს n. ეს n ნაბიჯები, მაგრამ ჩვენ შემოწმების თითოეული დრო. Okay. N მაგრამ თქვენ შემოწმების თითოეულ დროს? Okay, მაგრამ თუ ის n ნაბიჯები, არ უნდა მე ვერ დასალაგებლად თქვენ მიერ მხოლოდ აპირებს 1, 2, 3, 4? Oh! Okay, რომ დიდი განსხვავება. ამიტომ N კვადრატში რატომ? რა ხდება რეალურად? არსებობს N ხალხი ამ სიაში, მაგრამ იპოვონ ყველაზე მცირე პირი სია ყველაზე ცუდ შემთხვევაში, თუ რამდენი ნაბიჯები უნდა გადადგას? >> ნ 

N, უფლება, რადგან უარეს შემთხვევაში, ნომერი 1 არის ყველა გზა იქ, ამიტომ უნდა წახვიდე კიდევ მას. და მაშინ როდესაც მე საბოლოოდ გააცნობიეროს 1 იყო პატარა, მაშინ იგი საკმაოდ სწრაფია სვოპ მათ. მაგრამ ახლა უნდა დაიწყოს თავიდან და ვეძებთ ვინ? შემდეგი ყველაზე პატარა პირი, რომელიც 2. სადაც უარეს შემთხვევაში არის 2? ოჰ, ღმერთი ჩემი. ეს ყველა გზა აქ დასასრულს. ახლა მე უბრალოდ გაკეთდეს კიდევ ერთი N ნაბიჯები, მეორე n ნაბიჯები. და თუ გვაქვს N ხალხს და უარეს შემთხვევაში პატარა პირი N ნაბიჯის მოშორებით, რომ კვლავ N ჯერ N, და ამიტომ ჩვენ ისევ არ n კვადრატში. ეს არ არის შეგრძნება იმდენად კარგი. ფაქტია, მაშინაც კი, საუკეთესო შემთხვევაში - ვივარაუდოთ, რომ ისინი დაიწყება off დახარისხებული - რამდენი ნაბიჯები სჭირდება ჩემთვის გამოყენებისას ალგორითმი დასალაგებლად ამ N ხალხს? N კვადრატში. >> გავიგე N კვადრატში. რატომ N კვადრატში? იმიტომ, რომ თქვენ კვლავ უნდა შეამოწმოს თითოეული დრო. >> Yeah. და თქვენ უნდა სვოპ მათ. >> მიუხედავად იმისა, რომ ჩვენ ადამიანები ვართ სახის omniscient იმ გაგებით, ვიზუალურად, რომ ჩვენ უბრალოდ სახის ვნახავთ, რომ ეს დახარისხებული, კომპიუტერი არაა, რომ smart. იგი აპირებს გამოიყურებოდეს აქ და აქ და აქ, მაგრამ თუ რასაც ის ეძებს ყველაზე პატარა ელემენტის, თქვენ მხოლოდ ვიცი, რომ თქვენ ი ყველაზე პატარა ელემენტს რა წერტილი? ერთხელ თქვენ დასასრულს. მაგრამ იმ ეტაპზე თქვენ მხოლოდ გაკეთებული პატარა ელემენტს. თქვენ არ აუცილებლად ვიცი არაფერი მდგომარეობის შესახებ მსოფლიოში. ასე რომ თქვენ არ წასვლა ისევ და ისევ და ისევ. 

ასე რომ, ეს დრო მართლაც გამოიყურებოდეს მუნჯები რადგან მე შემოწმების, okay, 2, თქვენ ყველაზე პატარა, მაგრამ არ ვიცი, რომ სულ არ არის. 3, 4, 5, 6, 7, 8. Okay, კარგი. 2 მართლაც ყველაზე პატარა. ახლა მოდით მოვძებნოთ შემდეგი პატარა. Okay. 3, თქვენ გაკეთებული პატარა. ვნახოთ. 4, 5, 6, 7, 8. Okay, მივიღე გაუმართლა ერთხელ. 3 მართლაც სწორი ადგილი. მაგრამ მე ვაპირებ აკეთეთ ეს კიდევ ერთხელ და ისევ და ისევ. როგორ გავაკეთოთ ოდესმე ისე ოდნავ უკეთესი? იმის მაგივრად რომ ხალხს ბუშტი up pairwise საწყისი პატარა რომ უდიდესი და ნაცვლად აპირებს უკან და მეოთხე მეშვეობით სიის შერჩევის შემდეგ ყველაზე პატარა პირი, რატომ არ გვაქვს ნაცვლად ჩადეთ ეს ადამიანები ახალ სიაში ეტაპობრივად? მოდით ცდილობენ ამ. ახლა ნება მომეცით დაარქვით რამ Insertion ჯიშია. ასე რომ აქ ვართ აქ. ხმების 1. მე არ აინტერესებს ვინმეს ამ სიაში. ჩემი მიზანი სწორედ ახლა არის დააყენოს ნომერი 1 წლის დასაწყისში დახარისხებული სია. და მე ვაპირებ შესთავაზოს რადგან მე მხოლოდ 8 მოცულობით მეხსიერება, თვითნებურად ახლავე ვარ კედელს ჩემი სავარაუდოდ არასორტირებული სია, და ვინც არის ჩემს უკან მე ვაპირებ პრეტენზია არის დახარისხებული. ახლა ჩვენ გვაქ რიცხვი 1. მინდა ჩადეთ მას ჩემი დახარისხებული სია, ასე რომ მე უბრალოდ აპირებს გადავიდეს ჩემი კედლის მეტი აქ, და ახლა ადასტურებენ, რომ ამ სიაში დალაგებულია, ამ სიაში არასორტირებული - მინიმუმ რამდენადაც ვიცი. მე ვერ ვხედავ ყველა ნომრები ერთდროულად. 

ახლა კი მოხდეს ექმნებათ ნომერი 2. რა ვუყოთ მას? მე ჩადეთ თქვენ ახლა შევიდა დახარისხებული სია. მაგრამ შეამჩნია რა ადვილი რომ იყო. მე უბრალოდ უნდა გამოიყურებოდეს. ხმების 1 არის. ოჰ, აშკარად 2 ღებულობენ მხარეს ნომერი 1. ახლა რა ვუყოთ 3? მე ჩადეთ თქვენ შევიდა დახარისხებული სია. მაგრამ ეს იყო სუპერ მარტივია. ეს არის სუპერ მარტივია, ეს არის სუპერ მარტივია, ეს არის სუპერ მარტივი, სუპერ მარტივია, სუპერ მარტივია. და ახლა ყველაფერი დალაგებულია ჩემს უკან, და რამდენი ნაბიჯები საერთოდ რომ მიიღოს? [სტუდენტი] ნ >> ამიტომ მხოლოდ n. ჩვენ გაუმართლა. ეს იყო მხოლოდ N რატომ? >> [სტუდენტი] იმიტომ სია დახარისხებული. სიაში უკვე დახარისხებული. ამიტომ მივიღეთ გაუმართლა. მაგრამ ჩვენ შემუშავებული ალგორითმი ამ დროს harnesses რომ სახის წარმატებას, რომ საუკეთესო შემთხვევაში სცენარი, რომელსაც არ კარგვაა ზედმეტი დრო. ამიტომ, ჩვენ ახლა რა ჩვენ მოვუწოდებთ ბუშტი ჯიშები სადაც ადამიანებს სახის ბუშტი up pairwise. ჩვენ ახლა აქვს შერჩევის დალაგების სადაც ჩვენ pluck გარეთ პატარა პირი ისევ და ისევ. და ახლა ჩვენ გვაქვს Insertion დალაგების სადაც ჩვენ ერთგვარი აქტიურად დააყენა ხალხი, სადაც ისინი მიეკუთვნებიან მზარდი დახარისხებული სია. თუ შეგვეძლო, რაუნდი ტაში ამ ბიჭებს აქ. [ტაში] ავიღოთ ჩვენი 5 წუთიანი შესვენება აქ. და როდესაც ჩვენ დავბრუნდებით, ჩვენ აფეთქება ყველა ამ ალგორითმები წყლიდან რაღაც უკეთესი. ყველა უფლება. მადლობა ძალიან. თქვენ შეგიძლიათ შენარჩუნება იმ სახით სუვენირები. ყველა უფლება. ჩვენ უკან. 

და recap რეალური სწრაფი, ჩვენ გვქონდა ამ 3 სხვადასხვა მიდგომების დაფასოების, მთელი წერტილი იყო მისაღებად წერტილში, სადაც ვინმე მოსწონს ალექს შეიძლება ძებნის სიაში ნომრები უფრო სწრაფად, ვიდრე ვინმეს მოსწონს შონ შეეძლო. და მიუხედავად იმისა, რომ გვაქვს ასეთი მარტივი მაგალითები, 8 ნომრები, თქვენ შეიძლება extrapolate ადვილად 8 ვებ გვერდები, 8 მილიარდ ვებ გვერდები, ან 800 მილიონი მეგობრები Facebook-ზე. ასე რომ ეს ალგორითმები შეიძლება თქმა მასშტაბის იმ სახის ღირებულებები, და იდეები საბოლოოდ იგივე. ამიტომ ბუშტი დალაგების იყო პირველი, სადაც ჩვენ ერთგვარი bubbled up ყველაზე დიდი პირი ყველა გზა უფლება მიერ შევცვალე ხალხი pairwise. მაშინ ჩვენ გვქონდა რა ჩვენ მოვუწოდებთ შერჩევის დალაგების სადაც მე ცოტა მეტი განზრახ ინახება გადახედეთ სიას, შერჩევა ყველაზე პატარა ნომერი ისევ და ისევ და ისევ, ლოგიკური შედეგია, რომელიც არის ის, რომ სიაში საბოლოოდ დახარისხებული. მერე მესამე, მე ჩასმული ადამიანები თავიანთ შესაბამის ადგილზე, და ჩვენ ძალიან contrived მაგალითად, რომ სიაში უკვე დახარისხებული, მაგრამ, რომ მან გამოაგზავნა გაგზავნა, რომ Insertion დალაგების საქმე, შეგიძლიათ მიიღოთ გაუმართლა. თუ ციფრები უკვე დახარისხებული, ეს მხოლოდ აპირებს თქვენ N ნაბიჯები, რათა დაადასტუროს იმდენი, ხოლო შერჩევის დალაგების თქვენ ცოტა მეტი გვირაბი ხედვა და თქვენ არ ოდესმე მიხვდებიან, რომ სიაში უკვე დახარისხებული. ასე რომ ვნახოთ bubble sort მოქმედებაში აქ. მიმდინარე მაგალითში, ჩვენ შესახებ, რომ ნახოთ ვერტიკალური ბარები რომლის სიმაღლეებზე წარმოადგენენ ციფრები ისე, რომ ჩვენ შეგვიძლია სახის ვიზუალიზაციისთვის დახარისხება მოხდეს. პატარა ბარი, პატარა ნომერი; უფრო დიდი ბარი, მით უფრო დიდია რიცხვი. 

და ჩვენ ითამაშოთ ამ ნაგულისხმევი სიჩქარე. იგი აპირებს გადავიდეს ცოტა სწრაფად, მაგრამ წითელი არის რა გვიჩვენებს 2 ბარები მიმდინარეობს შედარებით თალიზში. და თუ თქვენ უყურებთ მჭიდროდ, რა მოხდება, თუ ბარები მწყობრიდან გამოსულია, პატარა ერთი იღებს გადავიდა მარცხენა, მით უფრო დიდია ერთი მარჯვნივ, და მაშინ თქვენ გაქვთ მიიწევს. ასე რომ, თუ ჩვენ ამას ვაკეთებთ, ისევ და ისევ შეამჩნევთ, რომ პატარა ბარები ვაპირებთ შენარჩუნება inching მათი გზა მარცხენა და ყველაზე დიდი ბარები ვაპირებთ შენარჩუნება inching მათი გზა უფლება. მართლაც, ჩვენ ვიწყებთ ვხედავთ ნიმუში ყველა გზა ზე მარჯვენა მხარეს ისევე, როგორც დავინახეთ, 8 და შემდეგ 7 საბოლოოდ bubbling მდე შორს ბოლოს ჩვენი ადამიანის სიაში. ასე რომ, ეს აპირებს ძალიან სწრაფად მიიღოთ ცოტა რუტინული, ნება მომეცით, შეაჩერონ ეს ერთი მომენტი. ნება მომეცით შეცვალოს სიჩქარე უნდა იყოს ბევრად უფრო სწრაფად. მე არ იცვლება ალგორითმი, მე უბრალოდ მიღების ანიმაცია მოხდეს სწრაფად. უძრავი bubble sort, იმავე ალგორითმი, მაგრამ ახლა ხედავთ ბევრად უფრო სწრაფად, ვიდრე ჩვენი სიტყვიერი დემონსტრაცია რომ ყველაზე დიდი ელემენტები მართლაც bubbling მდე დაბრუნება. 

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

როგორც კი გადავიდა ნომერი 1 აქ - Sammy ამ შემთხვევაში - რა უნდა გავაკეთოთ, მასთან შემდგომში? >> [სტუდენტი] დატოვეს. დატოვეს, არა? არაფერი. მე არ უნდა ოდესმე გაიგო Sammy ერთხელ რადგან მე რომ შერჩეული პატარა ელემენტს და მას აქ, რატომ ნარჩენები დრო აპირებს ბოლომდე ჩემი მთელი სია? მეორე iteration ნება მომეცით რეალურად გადაადგილება მხოლოდ რიცხვი 2, მხოლოდ ნომერი 3. ასე რომ, რეალურად, მე არ აკეთებს N რამ N ჯერ. მე აკეთებდა N რამ, მაშინ N - 1 რამ, მაშინ N - 2 რამ, მაშინ N - 3 რამ, მაშინ N - 4, dot, dot, dot. ჩვენ გვყავს ცოტა გეომეტრიული სერია, რომელიც უბრალოდ ნიშნავს თქვენ დასძინა up თანდათანობით პატარა ნომრები. არ N + N + N + N მაგრამ N + 7 + 6 + 5 + 4 + 3 + 2 + 1. და რა, რომ ზოგადად მუშაობს აღმოჩნდება - მე ვაპირებ mess up ჩემი მონიშნე აქ მხოლოდ მომენტში - რომ იმუშავებს აღმოჩნდება რაღაც n (n - 1) / 2 თუ ჩვენ მხოლოდ სახის შევხედოთ უკან მათემატიკის წიგნი, სადაც თქვენ ყველა მოტყუებას sheets ამისთვის ფორმულები. თუ თქვენ მხოლოდ დასძინა რაღაც N + N - 1 + N - 2, მუშაობს აღმოჩნდება მსგავსი რამ. და თუ ჩვენ მხოლოდ სახის გავამრავლოთ ამ გარეთ, რომ n კვადრატში მინუს N / 2. მე ამბობდა N კვადრატში, თუმცა, და ეს იმიტომ, რომ მე ვიყავი სახის აღების გონებრივი მალსახმობი რადგან რეალურად, N კვადრატში მინუს n იყოფა 2 მართლაც ჭეშმარიტი რაოდენობის ნაბიჯები რომ ალგორითმი მოსწონს შერჩევის დალაგების მიიღებს თუ ჩვენ მართლაც დათვლილი მდე ყველა იმ პარალელებისა და ყველა პატარა დატვირთული მუშაობის ვაკეთებდით. მაგრამ გულწრფელად ვამბობ, ერთხელ N იღებს უნდა იყოს ერთი მილიონი ან მილიარდი, რომელიც heck ზრუნავს თუ თქვენ აკეთებთ მილიარდი კვადრატში მინუს მილიარდი იყოფა 2? მილიარდი კვადრატში არის დიდი რაოდენობით. შეგიძლიათ მიიღოს სხვა მილიარდი გამორთვა იგი - ო. ეს არ არის ისეთი დიდი გარიგება. ასე უფრო დიდი ციფრები კიდევ, ნაკლებად მნიშვნელოვანია ამ ქვედა უბრძანა პირობები. ვინ ზრუნავს თუ დაყოფის მიერ 2 თუ თქვენ ვსაუბრობთ quadrillions ნომრები ნაბიჯები? 

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

მაგრამ თუ სიაში იყვნენ რეალურად უკან - მაგალითად, ამ შემთხვევაში აქ - მაშინ შეამჩნია ჩვენ რეალურად უნდა გავაკეთოთ ბევრი მუშაობა ამ შემთხვევაში. უნდა სახის გრძნობენ თქვენ მოსწონს ეს ერთი სახის სამუშაო რთული მიიღოს იმ პატარა ელემენტები მარცხენა, და ეს იმიტომ, რომ ჩვენ მივიღეთ უიღბლო. სია დალაგებულია შემთხვევით წელს საპირისპირო. პირიქით, ერთად Insertion დალაგების თუ ჩვენ mimic რა გავაკეთეთ ჩვენს ადამიანებში აქ მიერ დაწყებული ყველას დახარისხებული და შემდეგ დაიწყება, ეს საკმაოდ კარგი ალგორითმი, არა? უკვე, ფაქტობრივად, დახარისხებული. მოდით ცდილობენ შეაჯამოს ზუსტად რამდენ დროს ეს ყველაფერი ხდება ჩვენს შემოღების უბრალოდ ცოტა jargon ან ნოტაცია, რომ სინამდვილეში ბევრად უფრო მარტივია ვიდრე fanciness სახის გვთავაზობს. ეს რამ აქ, ამ დიდ O ეკრანზე, არის ის, რაც კომპიუტერის მეცნიერი, ზოგადად გამოიყენოთ აღწერისთვის უარეს შემთხვევაში გაშვებული დრო ალგორითმი. 

ერთხელ, რომელსაც უარეს შემთხვევაში, ეს სრულიად კონტექსტში დამოკიდებული. რა ვგულისხმობთ უარეს შემთხვევაში სრულიად განსხვავდება ეფუძნება პრობლემა ჩვენ ვსაუბრობთ. მაგრამ იმ შემთხვევაში, დახარისხება, რა ყველაზე უარესი სცენარით? ყველაფერი უკან, რადგან ის უბრალოდ იგრძნობა, რაც იმას ნიშნავს ბევრი სამუშაოა ჩვენთვის. მე jotted ქვემოთ რამდენიმე ალგორითმები, რომ ჩვენ ვნახეთ დღემდე: ხაზოვანი ძებნა, ორობითი ძებნა ისევე, როგორც სატელეფონო წიგნი ან ცალი ქაღალდის, მაშინ ბუშტი დახარისხების, შერჩევის დალაგების, და Insertion დალაგების მოსწონს დავინახეთ ჩვენს ადამიანებში, და შემდეგ 1 სხვა რომ საბოლოოდ აპირებს ეწოდოს შერწყმა ჯიშია. ასე ხაზოვანი ძიება უარეს შემთხვევაში, რამდენი ნაბიჯები სჭირდება იპოვოს ნომერი 7 თუ არსებობს N კარები მოსწონს შონ სახიანი? >> [სტუდენტი] ნ ნ ამიტომ, ჩვენ ვაპირებთ დავწეროთ დიდი O of n. მე უბრალოდ აპირებს შეავსოთ ზოგიერთ ბლანკები. ეს არის უბრალოდ ქსელში ბლანკები. მაგრამ საუკეთესო შემთხვევაში ხაზოვანი ძებნა, 7 შესაძლოა ზუსტად იმ დაწყების სია, და შონ შესაძლოა დაიწყო ეძებს დაწყების სიაში. ასე რომ, თუ თქვენ იყენებთ ხაზოვანი ძებნა და მხოლოდ შემოწმების მარცხნიდან მარჯვნივ ან იქნებ მარჯვნიდან მარცხნივ - ისინი ექვივალენტი - საუკეთესო შემთხვევაში რამდენი ნაბიჯები შეიძლება ხაზოვანი ძებნა, მოსწონს შონ ს ალგორითმი, მიიღოს? მხოლოდ 1 ნაბიჯი. 

ამიტომ მე ვაპირებ ვთქვა, რომ არის ომეგა ნოტაცია. ეს არის მხოლოდ დედაქალაქში omega. Omega მხოლოდ sexy გზას ვამბობ, საუკეთესო შემთხვევაში ქრონომეტრაჟი. ასე რომ, საუკეთესო შემთხვევაში ქრონომეტრაჟი არის ერთი ნაბიჯი ან მუდმივი რიგი ზომების - 1 ამ შემთხვევაში - მაგრამ უარეს შემთხვევაში, დიდი O, ეს არის რეალურად N ნაბიჯები. და ეს ერთი აქ, Theta, ჩვენ რეალურად არ აპირებს შევხედოთ ახლავე. ეს არ არის შესაბამისი ამ კონკრეტულ მაგალითს. მაგრამ ახლა მოდით შევეცადოთ ორობითი ძებნა. ყველაზე ცუდ შემთხვევაში ორობითი ძებნა, რამდენი ნაბიჯების იგი აპირებს მოძიების ნომერი 7 ან რასაც ჩვენ ვეძებთ? >> [სტუდენტი] შესვლა n. კვლავ აპირებს შესვლა N რადგან ისევე, როგორც ალექს მიიღო უიღბლო როდესაც ჩვენ მართლაც მუშაობდა მეშვეობით პრობლემა მეთოდურად და მან ვერ ნომერი 7 სანამ ძალიან ბოლო კარი მას შევხედე, მიუხედავად იმისა, რომ სამართლიანობა, She Got to გადაყარეთ გარკვეული კარები გზაზე, ორობითი ძიება უარეს შემთხვევაში აქვს გაშვებული დროს შესვლა n. ისევ და ისევ, რომ საუბრობს ამ გამყოფი და დაპყრობის. კი მაგრამ საუკეთესო შემთხვევაში? და ალექსი რეალურად გამოცდილი, რომ საუკეთესო შემთხვევაში უფლება როდესაც იგი გამოვიდა სცენაზე. რამდენი ნაბიჯები საერთოდ რომ მიიღოს ორობითი ძებნა? >> [სტუდენტი] 1. 1, მხოლოდ იმიტომ, რომ მან მიიღო იღბლიანი. მაგრამ ეს ჯარიმა, რადგან omega ეხება საუკეთესო შემთხვევაში სცენარი, საუკეთესო შემთხვევაში საშუალებებით, მაშინაც კი, თუ ეს მხოლოდ შემთხვევითი dumb luck. 

ახლა, ამ ძალიან ჩვენ ვაპირებთ მხოლოდ სახის დატოვეთ ცარიელი ახლა. როგორ შესახებ არის ბუშტი დალაგება? ყველაზე ცუდ შემთხვევაში bubble sort, ყველას არის საპირისპირო მიზნით, ამიტომ ჩვენ უნდა გავაკეთოთ ბევრი bubbling. მაგრამ რამდენი ნაბიჯების რომ აპირებს ყველაზე ცუდ შემთხვევაში? >> [სტუდენტი] N კვადრატში. ეს იყო N კვადრატში, რადგან თუ ფიქრობთ ამის შესახებ, თუ სიაში არის სრულიად უკან - 8 დასრულდა აქ, 1 არის აქ - როგორც რამ დაიწყება ბუშტი, ნომერი 8 აპირებს გადაადგილება ამ გზით, ამ გზით, ამ გზით, ამ გზით, მაგრამ სად არის ნომერი 7 ყველაზე ცუდ შემთხვევაში? აქ იგი ისევ იქ. ამიტომ, ჩვენ უნდა გავაკეთოთ ისევ და ისევ. სწორედ აქ მივიღებთ N ნაბიჯები, მაშინ N - 1 ნაბიჯები, მაშინ N - 2 Steps. და თუ თქვენ მიიღოს სიტყვას მისთვის - რომ თუ სახის გავამრავლოთ ის, ის უხეშად n კვადრატში დასასრულს რამდენიმე სხვა თვალსაზრისით, რომ ჩვენ უბრალოდ იგნორირება ახლა - მერე უარეს შემთხვევაში bubble sort არის n კვადრატში, მისცეს ან მიიღოს. მაგრამ რაც შეეხება საუკეთესო შემთხვევაში bubble sort? რა არის საუკეთესო შემთხვევაში სცენარი? ყველა ციფრები დალაგებულია უკვე. და რა იყო heuristic მე გამოიყენება, ხრიკი მე გამოიყენება, გააცნობიეროს, რომ გაკეთდეს არ მუშაობა და შესაბამისად მოგვიანებით შეწყვიტოს დასაწყისში? [სტუდენტი] შეამოწმეთ იგი ერთხელ. >> შეამოწმეთ იგი ერთხელ. მაგრამ რა იყო მე აკეთებს გზაზე? მე შენახვა ტრეკზე რამდენი სვოპების მივიღე. და მივხვდი, თუ მე არ დათვლილი ნებისმიერი სვოპების ჩემს თითებს, მაშინ მე ვაკეთებ არ მუშაობა. მე რა თქმა უნდა არ უნდა ვეცადოთ გავაკეთოთ არ მუშაობის ერთხელ, ასე, რომ შეიძლება უბრალოდ შეწყვიტოს. 

ასე რომ, საუკეთესო შემთხვევაში bubble sort, როდესაც სიაში უკვე დახარისხებული, რას იტყვით omega ნოტაცია არის, საუკეთესო შემთხვევაში ქრონომეტრაჟი? უბრალოდ n. ჩვენ უნდა გავაკეთოთ გარკვეული მუშაობა, მაგრამ ჩვენ მხოლოდ უნდა გავაკეთოთ 1 სეირნობა მისი ღირებულების სამუშაოს. და აქაც მე ვაპირებ დატოვეთ ეს ნაწილი ცარიელი. და ახლა შერჩევის ჯიშია. შერჩევა დალაგების ჰქონდა ჩემთვის plucking პატარა პირი ისევ და ისევ. და რა მივიღეთ ამბობენ გაშვებული დროს რომ იყო? ეს იყო N კვადრატში ყველაზე ცუდ შემთხვევაში. და სამწუხაროდ, საუკეთესო შემთხვევაში ის ასევე n კვადრატში რადგან მე არ მაქვს სახის omniscient ხედი მთელ მსოფლიოში; მე მხოლოდ ვიცი საფუძველზე სრული iteration, რომ მე მართლაც ნაპოვნი პატარა პირი. ამიტომ შერჩევას დალაგების სახის sucks ამ თვალსაზრისით, მაგრამ Upside არის მისი სახის ინტუიციური. ეს საკმაოდ ადვილი კოდი up რადგან ყველა თქვენ უნდა გააკეთოთ წერენ რამდენიმე წყობილი ამისთვის მარყუჟების, ტიპიურად, რომ გადის ეძებს პატარა ელემენტს და შემდეგ აყენებს პატარა ელემენტს, სადაც მას ეკუთვნის დასასრულს სიაში. ასე რომ აქაც არსებობს იქნება ვაჭრობის საგანი. თანხის დრო სჭირდება თქვენ ვიფიქროთ და რეალურად განვითარდეს რაღაც წერილობით კოდი შეიძლება ძალიან კარგად მიიღოს მეტი დრო თუ გინდათ უკეთესი ალგორითმი და სწრაფად შესრულება. 

მაგრამ თუ მართლაც მხოლოდ სახის კოდი რაღაც up სწრაფი და ბინძური და მხოლოდ სახის მიიღოს stupidest შესაძლო იდეა შეგიძლიათ წარმოიდგინოთ, რომ, რომ შესაძლოა თქვენ რამდენიმე წუთში კოდი, მაგრამ დიდი მონაცემები კომპლექტი თქვენი ალგორითმი შესაძლოა საათის გასაშვებად. და კიდევ მე ასპირანტურაში რომ ზოგჯერ ამ ვაჭრობის ღ. კარგი იქნება 3am, მე ვცდილობდი ანალიზი ზოგიერთი ძალიან დიდი მონაცემები კომპლექტი დაკავშირებული უსაფრთხოების კვლევის I აკეთებდა, და ეს იყო ან დახარჯავს 5 წუთი tweaking ჩემი პროგრამის ანალიზი მონაცემები და წასვლა სძინავთ ან დახარჯავს 8 საათი მისაღებად მას მხოლოდ უფლება, ასე რომ ეშვება მყისიერად და წასვლა არ სძინავთ. და ა.შ. იქაც ეს სახის შეგნებული გადაწყვეტილება. ნაკლებია განვითარების დროს, უფრო ძილის. In retrospect, მე ალბათ არ უნდა წაახალისოს, რომ როცა მიზანი აქ არის ოპტიმიზაციის ხარისხის კოდი, მაგრამ რომ ძალიან რეალურ ცხოვრებაში არის ძალიან გონივრული ვაჭრობის საგანი. ნაკლებ დროს, ნაკლებად შესრულების ან პირიქით. ასე რომ აქ ჩვენ საბოლოოდ მიიღოს შანსი საუბრობენ Theta. Theta ნოტაცია რაღაც კომპიუტერის მეცნიერები ვერ ზრდიან საუბარში როდესაც დიდი O და ომეგა მოხდეს იყოს იგივე. თქვენ ამბობთ Theta ნამდვილად გაგზავნას გაგზავნა, რომ ეს არის სახის მჭიდრო შეკრული. არ აქვს მნიშვნელობა თუ არა სცენარი არის კარგი ან ცუდი, ის n კვადრატში. ასე რომ, ეს უბრალოდ არ შეესაბამება ამ ისტორიებს აქ. Insertion დალაგების არის ბოლო ერთი ჩვენ შევხედეთ, სადაც მე უბრალოდ ჩასმა ყველას სწორი ადგილი. საუკეთესო შემთხვევაში რა იყო გაშვებული დრო Insertion დალაგების როგორც ვნახეთ აქ? [სტუდენტი] საუკეთესო შემთხვევაში? >> საუკეთესო შემთხვევაში. 

იგი n რადგან საუკეთესო შემთხვევაში ყველას დახარისხებული, და Sammy და არავინ მართლაც იძულებული იყო ყველა. ისინი უკვე თავიანთ ადგილას. ამიტომ Insertion დალაგების საუკეთესო შემთხვევაში არის, ამ შემთხვევაში, n. მაგრამ უარეს შემთხვევაში ეს სახის n კვადრატში. რატომ? თუ ჩემი სია ადამიანისა არის საპირისპირო მიზნით, მე პირველად იწყება ნომერი 8 და მე ჩადეთ მას სწორი პოზიცია, რომელიც სწორედ აქ. I ტიპის ნაბიჯი მხარეს. ეს ბიჭები არიან არასორტირებული, იგი დახარისხებული. მაგრამ ახლა მე ემართება ვინ შემდეგი? >> [სტუდენტი] 7. 7 ყველაზე ცუდ შემთხვევაში იმიტომ რომ წელს საპირისპირო მიზნით. 

ასე რომ აქ არის 7. სად 7 ეკუთვნის? აუცილებლად ჩემს უკან. მაგრამ ახლა 7 რეალურად ეკუთვნის არა მაშინვე ჩემს უკან, მაგრამ უკან ნომერი 8, ასე უნდა ვთქვა, "ბოდიში, ნომერი 8, შეგიძლიათ გთხოვთ გადაადგილება ამ გზით "იმისათვის, რომ ოთახი 7?" ახლა კი ექმნებათ 6. "ოჰ, მაპატიეთ, ნომერი 8 და ნომერი 7, შეგიძლიათ გადაადგილება, რათა ოთახი 6?" ასე რომ, სხვა სიტყვებით, ერთად Insertion დახარისხების, მიუხედავად იმისა, რომ მე არ აკეთებს გაცილებით მოძრაობა, ხალხი ჩემს უკან ვაკეთებთ უფრო მეტს მუშაობა, და ეს მივიღე ეღირება ვინმე დრო. იგი აპირებს ეღირება კომპიუტერის დრო. ასე რომ იმ შემთხვევაში Insertion დალაგების ჩვენ კვლავ განიცდიან. თუ დაიწყება დასძინა up საერთო რაოდენობის ნაბიჯები, ჩვენ დასრულდება მდე hitting უხეშად N კვადრატში რადგან ეს ბიჭები მოგიწევთ ოთახში ადამიანის უნდა ჩამატებულია ისევ რომ სიაში. და ა.შ. ამ შემთხვევაში Theta მხოლოდ არ გამოიყენება კონკრეტული ამბავი ხელთ. ეს იყო ლამაზი და კარგი. ჩვენ გვყავს ამ 3 სხვადასხვა გზა ვსაუბრობთ ქრონომეტრაჟი. მაგრამ რას უნდა ნიშნავდეს რეალურად რეალური თვალსაზრისით, თუ ჩვენ რეალურად ცდილობენ კოდი up ალგორითმი? 

ნება მომეცით შესთავაზოს, რომ არსებობს კიდევ უკეთესი ალგორითმი არსებობს რომელიც თვითონ აქვს გარკვეული ვაჭრობის ღ. ჩვენ ვაპირებთ ეძახით შერწყმა დალაგების, და ეს ერთგვარი ამ ჯადოსნური ალგორითმი რომ მუშაობს სწრაფად რატომღაც, და ეს ისე ადვილია, რათა გამოხატოს მაინც, pseudocode. განხორციელების ამ ალგორითმის შერწყმა დალაგების იქნება შემდეგნაირად. როდესაც თქვენ მოცემული n ელემენტებს - N ციფრები, N ხალხს, რასაც - პირველი არსებობს საღი აზრის ქვითარი. თუ n ნაკლებია, ვიდრე 2, შერწყმა დალაგება მხოლოდ აჩერებს. ის დააბრუნებს, ასე ვთქვათ. რატომ შეწყვიტოს თუ N ნაკლებია, ვიდრე 2? >> [Inaudible სტუდენტი საპასუხოდ] მარჯვენა. ისევ და ისევ, N არ არის ნომერი სიაში, N არის ზომა სიაში. თუ n ნაკლებია, ვიდრე 2, ეს ნიშნავს, რომ თქვენი სია ან 1, აქ თქვენ აშკარად დალაგებულია თუ 1 ნომერი, ან 0, ამ შემთხვევაში არაფერი დასალაგებლად, ამიტომ ჩვენ გვჭირდება ასეთი ბაზის შემთხვევაში. თუ სიაში არის ასე მოკლე, რომ იქ უბრალოდ არაფერ შუაშია, სიტყვასიტყვით არ არაფერი. დაბრუნება. წინააღმდეგ შემთხვევაში დასალაგებლად მარცხენა ნახევარში ელემენტები, მაშინ დასალაგებლად მარჯვენა ნახევარში ელემენტები, მაშინ შერწყმა 2 დახარისხებული halves. 

ასეთი თითქოს პატარა cheat რომლითაც მე თქვენ გეკითხებით როგორ დასალაგებლად ელემენტები და თქვენ მეუბნებოდა, "Sort მარცხენა ნახევარში, დასალაგებლად მარჯვენა ნახევარში." მე მოსწონს, "ყველა უფლება. როგორ დასალაგებლად მარცხენა ნახევარი?" "Sort მარცხენა ნახევარში მარცხენა ნახევარში, დასალაგებლად მარჯვენა ნახევარში მარცხენა ნახევარში, შემდეგ გაკეთდეს." თქვენ სახის ციკლურად განსაზღვრის რას ნიშნავს დასალაგებლად, მაგრამ აღმოჩნდება, რომ სინამდვილეში ბრწყინვალე ამ შემთხვევაში. ეს არ არის ჭეშმარიტად ამ მანკიერი ციკლი, რომ არასოდეს მთავრდება იმიტომ, რომ ეს არ დასრულდება, როდესაც? >> [სტუდენტი] როდესაც თქვენ მივაღწიოთ 1 რამ. როდესაც თქვენ მივაღწიოთ 1 რამ. ასე რომ მიუხედავად იმისა, რომ თქვენ შეიძლება დაიწყოს 8 ადამიანი და მე ვიტყვი, "Sort მარცხენა ნახევარში ამ ხალხს, ამ 4 ადამიანი ", მაშინ მე ვიტყვი," როგორ დასალაგებლად მარცხენა ნახევარი? ​​" "ისე, დასალაგებლად 2 ადამიანი აქ." და მაშინ თქვენ მოსწონს, "ყველა უფლება, ჯარიმა." "როგორ დასალაგებლად მარცხენა ნახევარში იმ ხალხს?" "სამართლიანი დასალაგებლად ამ 1 ადამიანი აქ." რა არის ბრწყინვალე აღმოჩენა არის? მაქვს დასალაგებლად 1 ადამიანი. შესრულებულია. მე არ მაქვს რაიმე მუშაობა. მაგრამ ახლა უნდა დასალაგებლად ამ ადამიანს, მაგრამ ისინი ერთი ადამიანი, არაფერ შუაშია. 

ამიტომ Magic აშკარად არის ამ მესამე ნაბიჯი: შერწყმა დახარისხებული halves. ასე რომ შერწყმა დალაგების იღებს ამ ბრწყინვალე ინსაითი, რომ თუ თქვენ შესვენება დიდი პრობლემა ქვემოთ შევიდა 2 პატარა, იდენტურად ზომის პრობლემები და მაშინ უბრალოდ სახის წებო პატარა გადაწყვეტილებები ერთად დასასრულს, მე ვთავაზობ, რომ ჩვენ შეგვიძლია გავაკეთოთ ბევრად, ბევრად უკეთესი [მოსმენების sound] ვიდრე ნებისმიერი შერჩევის დალაგების ან Insertion ჯიშია. მე პრაქტიკულად იგნორირება, რომ ნახევარი საათის განმავლობაში, მაგრამ მე ნამდვილად არ ვიცი რა ხდება გარეთ დღეს. [Whirring sound] [სიცილის] მოდით ვნახოთ, თუ ვხედავთ ამ პატარა დახმარება ჩვენი მეგობარი რობ Bowden. არის 2 დიდი ნაბიჯები პროცესში შერწყმა ჯიშია. პირველი, განუწყვეტლივ გაყოფილი სიაში შევიდა თასები halves სანამ ჩვენ გვაქვს bunch of სიები მხოლოდ 1 ჭიქა მათში. არ ინერვიულოთ, თუ სია შეიცავს კენტი ნომერი და ვერ მიიღოს შესანიშნავად სუფთა cut მათ შორის. უბრალოდ თვითნებურად აირჩიოთ რომელიც სიაში შედის ზედმეტი თასი სისტემაში მოდით გაყოფილი ამ სიებში. ახლა ჩვენ გვაქვს 2 სიები. ახლა ჩვენ გვაქვს 4 სიები. ახლა ჩვენ გვაქვს 8 სიები ერთი ჭიქა ყოველ სიაში. ასე რომ ეს ნაბიჯი 1. ამისთვის ნაბიჯი 2 ჩვენ არაერთხელ შერწყმა წყვილი სიები გამოყენებით შერწყმა ალგორითმი გავიგეთ ადრე. შერწყმა 108 და 15 ჩვენ დასრულდება up ერთად სიაში 15, 108. შერწყმა და 50 4 ჩვენ დასრულდება up ერთად 4, 50. შერწყმა 8 და 42 ჩვენ დასრულდება მდე, 8, 42. და შერწყმის 23 და 16 ჩვენ დასრულდება მდე, 16, 23. ახლა ყველა ჩვენი სიები არის ზომა 2. გაითვალისწინეთ, რომ ყოველი 4 სიები დალაგებულია, ამიტომ ჩვენ შეგვიძლია დავიწყოთ შერწყმის წყვილი სიები კიდევ ერთხელ. შერწყმა 15 და 108 და 4 და 50 ჩვენ პირველი მიიღოს 4, შემდეგ 15, მაშინ 50, მაშინ 108. შერწყმა 8, 42 და 16, 23 ჩვენ პირველი მიიღოს 8, შემდეგ 16, მაშინ 23, მაშინ 42. ახლა ჩვენ გვაქვს მხოლოდ 2 სიები ზომა 4, რომელთაგან თითოეული დალაგებულია. ახლა ჩვენ შევაერთებთ ამ 2 სიები. პირველი ჩვენ ვიღებთ 4, მაშინ ჩვენ ვიღებთ 8, მაშინ ჩვენ ვიღებთ 15 და 16 და 23 და 42 და 50 და 108. და ჩვენ გავაკეთეთ. ჩვენ ახლა აქვს დახარისხებული სია. 

რობ იყო სახის მიღების უპირატესობა რაღაც რომ ჩვენ ჯერ არ გაკეთებულა. იგი უარყო, მაგრამ ჩვენ არ რეალურად გავაკეთოთ. იგი აკეთებს რაღაც ფიზიკურად ერთად თასები რომ ვარაუდობს მას ხარჯავს ზოგიერთი რესურსის გარდა დრო. >> [სტუდენტი] ფართი. >> ეს იყო სივრცეში. ფაქტი, რომ მას ამ ტიპის ბი დონის მაგიდასთან, სადაც სივრცეში აქ და სივრცეში ქვემოთ აქ სინამდვილეში გულისხმობს, რომ ის გამოყენებით ორჯერ იმდენი სივრცე როგორც ჩვენს ნებისმიერ ალგორითმები დღემდე - Insertion დახარისხების, bubble sort, ან შერჩევის დალაგება - მაგრამ მას leveraging ამ დამატებითი ფართის სახის ნაბიჯი რამ უკან და მეოთხე ხოლო შენახვა რამ მიზნით. და მიუხედავად იმისა, რომ იგრძნობა მივიღეთ, რათა დახარისხებული სიის, რომ იგრძნო, როგორიცაა დასჭირდა ხოლო. სინამდვილეში, რა რობ აკეთებდა იყო ზუსტად ეს ალგორითმი. მან პირველი აიღო პრობლემა ზომა N, გაყოფილი ის მარცხენა ნახევარში და მარჯვენა ნახევარში. სწორედ მაშინ ის გადავიდა თასები. შემდეგ მან კიდევ ერთხელ გაიმეორა, რომ პროცესი. მან გაყოფილი 4 შევიდა 2 კომპლექტი 2 ზე აქ და აქ. შემდეგ მან კიდევ ერთხელ გაიმეორა, რომ პროცესი და გაყოფილი 2 შევიდა 2 კომპლექტი 1 თითოეული იმ სხვადასხვა თასები. სწორედ აქ ბრწყინვალე შესაძლებლობა ჩნდება. იმ დროისთვის ამბავი, რობ ჰქონდა 8 სიები ზომა 1, ყველა რომლებიც დალაგებულია უკვე. 

ასეა, მაშინ რა უნდოდა მას გაგრძელება უნდა გავაკეთოთ? Pairwise მან აიღო ეს დახარისხებული სია და ამ დახარისხებული სიის და მათ შეუერთდა. შემდეგ მან აიღო ეს ერთი და შეუერთდა მათ, მაშინ ეს ერთი და შეუერთდა მათ, მაშინ ეს ერთი და შეუერთდა მათ. და მერე რა ის გავაკეთოთ შემდეგი? შემდეგ მან ხელახლა გაერთიანდა დიდია სიები და შემდეგ ხელახლა გაერთიანდა დიდია სიები. და თუ ფიქრობთ ამის შესახებ მხოლოდ ინტუიციურად ახლა, რა იყო ის ნამდვილად აკეთებს? იგი გამყოფი პრობლემა ნახევარი, ნახევარ, ნახევარ, ნახევარ რათა მიიღოთ ამ სუპერ მცირე სიები. შემდეგ იგი იყო სახის აერთიანებს ორმაგი, ორმაგი, ორმაგი, ორმაგი. ასე რომ იგი აკეთებს ორჯერ კიდევ ბევრი სამუშაოა, როგორც ჩვენ ვნახეთ დღემდე ერთად რაც ეხება გათიშე და დაიპყროთ, მაგრამ არა დიდი გარიგება. ორჯერ კიდევ ბევრი სამუშაოა არ არის ასეთი დიდი გარიგება. უბრალოდ მუდმივი ფაქტორი. და ჰგავს ჩვენი არითმეტიკის გამოხატვის ადრე, მე უბრალოდ აპირებს გადაკვეთა გარეთ მუდმივი ფაქტორები მოსწონს ჯერ 2. ვინ ზრუნავს? თუ ეს 2 მილიარდობით ჯერ 2, რომ ჯერ კიდევ ბევრი ნაბიჯები. ასე რომ, ეს ნაბიჯი შერწყმის ჩანს გასაღები ინსაითი. მოდით გავლა ამ უბრალოდ რიცხობრივი ადრე - Oh, რომ არ უნდა გაგრძელდეს ამჟამად. მოდით გავლა ამ რიცხობრივი მხოლოდ რეალურად ვხედავ როგორ უკრავს გარეთ. ეს არის ძირითადად მხოლოდ პატარა ღარიბი ადამიანის ანიმაცია. მოდით შესთავაზოს ამ. გაშვებული დრო შერწყმა დალაგება - ჩვენ უბრალოდ უნდა გზა ვსაუბრობთ ამ. ეს არ არის მათემატიკის; ეს მხოლოდ სახის ლაკონური გზით გამოხატვის საკუთარ თავს. ასე T წარმოადგენს დრო და N წარმოადგენს რა? >> [სტუდენტი] ზომა - 

[Malan] ზომა პრობლემა, ადამიანების რიცხვი. ამიტომ მე იმის თაობაზე, რომ გაშვებული დრო დასალაგებლად N ხალხი იქნება 0 დროის თუ n ნაკლებია, ვიდრე 2, რადგან თუ თქვენ გაქვთ 1 ჭიქა ან არა ჭიქები, თქვენ არაფერს დასალაგებლად. მაგრამ ზოგადად, მე ვაპირებ, რომ შესთავაზოს ქრონომეტრაჟი დასალაგებლად N ელემენტები იქნება დრო სჭირდება დასალაგებლად მარცხენა ნახევარში Plus მარჯვენა ნახევარში Plus - რა არის ეს დამატებითი + N? >> [სტუდენტი] Merge ჯიშია. [Malan] სინამდვილეში შერწყმის, რადგან თუ თქვენ გაქვთ N / 2 ელემენტები აქ და თქვენ გაქვთ N / 2 ელემენტები აქ, რამდენი დრო სჭირდება შერწყმა მათ? ისევე, რობ, თქვენ უნდა pluck ამ ერთი მეტი აქ, იქნებ pluck მეტი აქ, pluck მეტი აქ, pluck მეტი აქ, pluck მეტი აქ. თქვენ უნდა შეეხოთ თითოეული თასები ერთხელ. და თუ არსებობს 4 ჭიქა Plus 4 ჭიქა, რომ 8 თასები ან, უფრო ზოგადად, 8 N თასები. ამიტომ შერწყმის ნაბიჯი შეგვიძლია გამოვხატოთ, როგორც N, და რომ სიტყვასიტყვით მოიცავს რამდენჯერმე რობ ფიზიკურად შეეხო ერთი იმ Styrofoam თასები. მოდით ახლა გავაკეთოთ თვითნებური მაგალითად. თუ არსებობს 16 თასები, რა გაშვებული დრო დახარისხება გამოყენებით Rob-ს ალგორითმი, 16 ჭიქა? ეს 2 ჯერ ოდენობით დრო სჭირდება დასალაგებლად 8 თასები იმიტომ რომ ჩვენ გვაქვს 8 თასები აქ, 8 თასები აქ. არ ვიცი, რამდენ ხანს, რომ იღებს, ამიტომ ჩვენ generalizing, როგორც T მომენტისათვის. ვინ იცის რა არის? მაგრამ ახლა მე შემიძლია სახის რეკურსიული ან განმეორებით ვთხოვ იგივე კითხვა. რა დრო სჭირდება დასალაგებლად 8 ჭიქა? 8 ჭიქა მე ვაპირებ ვთქვა იღებს თანხის დრო სჭირდება დასალაგებლად 4 ჭიქა Plus 4 ჭიქა, მაშინ შერწყმის მათი ერთად. სახვითი. ჩვენ მისაღებად შევიდა ციკლი უკვე. როგორ სჭირდება დასალაგებლად 4 ჭიქა? დრო სჭირდება დასალაგებლად 4 ჭიქა არის 2 ჭიქა Plus 2 ჭიქა დახარისხება Plus შერწყმის პროცესი. სახვითი. როგორ სჭირდება დასალაგებლად 2 ჭიქა? 2 ჭიქა არის დროის სჭირდება დასალაგებლად 1 ჭიქა Plus დრო სჭირდება დასალაგებლად მეორე თასი პლუს თანხის დრო სჭირდება შერწყმა, რომელიც მხოლოდ 2. 

სახვითი. ბოლო შეკითხვა. როგორ სჭირდება დასალაგებლად 1 ჭიქა? აქ არის ბაზის შემთხვევაში, რომ ჩვენ იწინასწარმეტყველა ჩვენ ავღნიშნო მოხვდა ადრე. ფაქტი, რომ იგი იღებს არ მუშაობაში ჩაბმის დასალაგებლად პატარა პრობლემები ნიშნავს, რომ ახლა, ერთგვარი Grade სკოლის სტილის, ჩვენ შეგვიძლია უბრალოდ დაიწყოს ჩართვის ამ ნომრებზე უკან შემოსული ახლა ჩვენ ვიცით, რა T 1 არის, ასე, რომ შეიძლება შეაერთედ in 0 ამისთვის T 1. ეს ხელს მაძლევს პასუხი T 2, რომელიც მე მაშინ შეგიძლიათ შეაერთედ უმაღლეს up. ეს ხელს მაძლევს T, 4, რომელიც შემიძლია შეაერთედ უმაღლეს up. ეს ხელს მაძლევს T 8, რომელიც შემიძლია შეაერთედ უმაღლეს up. და თუ მართლაც, რომ მათემატიკის მიერ ჩართვის ეს პასუხები, მე მაშინ კიდევ T of 16 არის 64. და რა 64 წარმოადგენს? თუ T არის 16, ჰო 16 ჯერ 4. ასე, რომ აცხადებენ, რომ ქრონომეტრაჟი ამ რამ მოუწოდა შერწყმა დალაგება - და ეს იქნება fanciest of პირობა ჩვენ ვნახეთ დღემდე - აპირებს ეწოდოს N შესვლა N რადგან რამდენჯერ შეიძლება რობ გაყოფილი მთელი bunch of თასები ნახევარ? შესვლა n. ეს იგივეა, რაც ტელეფონის წიგნი მაგალითად, ეს იგივეა, რაც თვითმმართველობის დათვლა მაგალითად. 

რამდენჯერ შეგიძლიათ გაყოფა რაღაც ნახევარ? თუმცა, არსებობს ამ შერწყმის ნაბიჯი. ალბათ გაყავით ჭიქა შევიდა ნახევარი ისევ და ისევ და ისევ, მაგრამ ყოველ ჯერზე, რომ თქვენ აპირებთ უნდა შერწყმა. ჩვენ ცოტა ხნის წინ განაცხადა, რომ გაერთიანების N თასები იღებს N ნაბიჯები იმიტომ, რომ თქვენ უნდა pluck გარეთ თასი, pluck გარეთ თასი, და თქვენ უნდა შეეხოთ ყველა თასი ერთხელ, ისევე, როგორც რობ გააკეთა. ასე რომ, თუ ვაკეთებთ რაღაც შესვლა N ჯერ და ვაკეთებთ N რამ თითოეულ იმ iterations, თითოეული მათგანი halvings, ჩვენ გვაქვს N ჯერ შესვლა n. ასე რომ, თუ ჩვენ შეაერთედ in 16 ამ მაგალითად, 16 ჯერ შეხვიდეთ of 16 - არ ინერვიულოთ შესახებ, თუ რატომ არის ამ შემთხვევაში, რადგან მე არ შედგა ბაზა - მაგრამ შესვლა არაძვირფასი 2 of 16 არის 4, 16 ჯერ 4 არის 64. მაგრამ ამის საპირისპიროდ, თუ გვქონდა გამოყენებული bubble sort ან შერჩევის დალაგების ან Insertion დალაგების, 16 ნომრები, რა ქრონომეტრაჟი არ ყოფილა, თუ N არის 16? ეს იქნება 16 კვადრატში, რომელიც 256, რომელიც მაშინაც კი თუ თქვენ არ საკმაოდ მოყვება ყველა მათემატიკის, 256 მეტია, ვიდრე 64. რომ მართლაც ჯადოსნური takeaway აქ. და გააცნობიეროს, რომ სამუშაო მეშვეობით ამ მცირე მაგალითები როგორც თქვენ ნება pset ხდის ყველა ბევრად უფრო ინტუიტიური. მაგრამ რა, რომ ნამდვილად ნიშნავს თვალსაზრისით შეგრძნებას ეს ალგორითმი არის ამ: თუ ჩვენ რეალურად შევხედოთ შერწყმა დალაგების აქ - ნება მომეცით დახევის it up ამ ფანჯრის აქ - ეს ოდნავ განსხვავებული მაგალითი, რომლითაც ჩვენ ყველანი 3 ამ ალგორითმები - ბუშტი, შერჩევა, და შერწყმა - უბრალოდ თალიზში. 

მათ ყველა დაიწყო შემთხვევითი ბარები, და ეგ კარგია. არავის არ აქვს ფუნდამენტური უპირატესობა სხვა. მე ვაპირებ წელს მომენტში დააწკაპუნეთ თითოეულ ამ ანიმაციის - დაწყება, დაწყება, დაწყება - სწრაფად შემიძლია ასე რომ, უხეშად, ისინი ყველა დაწყება ამავე დროს, და მოდით მიიჩნევენ, რომ ბუშტი დალაგების ს უარესი შემთხვევაში ქრონომეტრაჟი არის რა? >> [სტუდენტი] N კვადრატში. N კვადრატში. შერჩევა დალაგების ს უარეს შემთხვევაში ქრონომეტრაჟი არის? N კვადრატში. და შერწყმის დალაგების აშკარად - მაშინაც კი თუ თქვენ არ საკმაოდ დაიცვას ყველა მათემატიკის ახლა, ეს გავხდებით ბევრად უფრო ინტუიტიური დროთა განმავლობაში - ეს არის, ჩვენ ვამბობთ,, N ჯერ შესვლა n. და რადგან შესვლა N არის მკაცრად ნაკლები n ერთხელ გვაქვს დიდი ციფრები, N ჯერ შესვლა N მცირეა N ჯერ n ან N კვადრატში. ასე რომ რას გრძნობენ რეალურად იყოს უკეთესი ალგორითმი თვალსაზრისით ქრონომეტრაჟი, N ჯერ შესვლა N ნაცვლად N კვადრატში? Here We Go. დაწკაპუნება, click, click. 

სწორედ რას ნიშნავს გამოიყენოთ რაღაც შერწყმა ჯიშია. ჩვენ გვყავს მომენტში. ვნახოთ რა ხდება აქ. [Chuckles] ვისი ფული არის ბუშტი დალაგება? ეს საკმაოდ დამოკიდებულია შეყვანის ხანდახან. ვნახოთ. Come on. ეს იგრძნობა ის catching up. >> [სტუდენტი] წადი, bubble sort! [სტუდენტი murmuring] [Malan] Yeah, yeah. [სტუდენტი murmuring] წადი, წადით, წავიდეთ! [ყველა cheering] [ტაში] ასე რომ ახლა 1 ბოლო, საბოლოო დემო, თუ ცოტა სახიფათო უნდა გადაიტანოთ თქვენი აზრით გარშემო მათემატიკის ან სახის ვიზუალიზაცია არსებობს, თქვენ შეგიძლიათ რეალურად მოვისმინოთ სიჩქარეზე სხვადასხვა ალგორითმები განსხვავებულად. ეს არის ანიმაცია ვინმე გააკეთა, რომ რეალურად Associates ხმები ერთად პროცესი შევცვალე და სიმაღლე ბარები. როგორც ვნახავთ, აქ, იქ კიდევ რამდენიმე დახარისხება ალგორითმები out არსებობს, რომ ეგ არ მიფიქრია. ეს პირველი იქნება Insertion დალაგების, და ეს იქნება ფრენა მეშვეობით და მოგცემთ Audible გრძნობა როგორ შეიძლება ამ სხვადასხვა ალგორითმები მუშაობა. აქ არის Insertion ჯიშია. [ელექტრონული beeping] [Malan] Bubble ჯიშია. [სწრაფად ელექტრონული beeping] [Malan] შერჩევა ჯიშია. [სწრაფად ელექტრონული beeping] [Malan] Merge ჯიშია. [ელექტრონული beeping] [Beeping ანელებს] [სიცილის] [Malan] Gnome ჯიშია. [ელექტრონული beeping] 

ეს არის CS50. ჩვენ დავინახავთ, თქვენ მომავალ კვირას. [ტაში და cheering] 

[CS50.TV]