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

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

აუდიტორია: Mary Beth. დინამიკები: Mary Beth, მოდის up. ნება მომეცით კიდევ მიკროფონი აქ თქვენ. კარგია თქვენთან შეხვედრა. 

აუდიტორია: კარგია თქვენთან შეხვედრა. დინამიკები: ყველა უფლება, ამიტომ მე არ მაქვს აქ blue წიგნები მეშვეობით Z, და მე ვაპირებ, ვიტყვი, რომ მე მაქვს ერთი სტუდენტი, და ისინი მომავალი გარკვეულწილად შემთხვევით ბოლოს სამი საათიანი გამოცდა ბლოკი, ამიტომ ისინი დამთავრებული ზოგიერთი ნახევრად შემთხვევითი მიზნით მოსწონს ეს. ახლა თქვენი სამუშაო, რაღაც მომენტში ხდება to be-- ეს არის რეალურად, თუ როგორ იღებენ დღევანდელი ბოლოს კლასის, სავარაუდოდ. თქვენი სამუშაო არის, იქნება, საკმაოდ უბრალოდ, ახარისხებენ ლურჯი წიგნები us საწყისი მეშვეობით ზ 

აუდიტორია: ოჰ, ეს აპირებს სამუდამოდ. 

დინამიკები და ჩვენ დავაკვირდებით როგორც თქვენ ამის გაკეთება, არ ზეწოლა. აუდიტორია: არა, არა, ზეწოლის ან არაფერი. 

დინამიკები და გასართობად, მოდით დააყენა up ტაიმერი. 

აუდიტორია: ასე რომ ბევრი fun, იმდენად fun. 

დინამიკები შემიძლია გამართავს მიკროფონი თქვენთვის. ყველა უფლება, ჩვენ უბრალოდ გაორმაგდა ჩვენი სიჩქარე. ასე რომ, იმავდროულად, ნება მომეცით უქმნის რა არის იქნება კითხვა Mary Beth არის რა ის აკეთებს, როგორ არის იგი აპირებს გადაჭრას ეს? და ფაქტობრივად, თქვენ შეიძლება არ აქვს არასოდეს მიფიქრია, რომ რაღაც ისე მარტივია, როგორც, როდესაც თქვენ აირჩიოთ up 26 წიგნი ასე, რომელიც არ აქვს ბუნებრივი შეკვეთით მათ. რა არის პროცესი რომ თქვენ ნამდვილად გამოიყენოს? ეს არის საკმაოდ შემთხვევითი მხოლოდ კრეფა პირველი ხედავთ და აყენებს მას თავის ადგილს? მიგაჩნიათ თუ არა პირველი გადაადგილება თქვენი ხელები გარშემო ეძებს შემდეგ ეძებს B? მიგაჩნიათ თუ არა მიიღოს შევხედოთ წყვილი მათ გვერდით და უბრალოდ, ვამბობთ, დაველოდოთ წუთში, ამ არ არის სწორი, შემდეგ სვოპ ბრძანებით? ჩვენ ვნახეთ, უკვე ორშაბათს რომ არსებობს მთელი რიგი გზები რომელშიც ჩვენ შეგვიძლია ამის გაკეთება, და მართლაც, როგორც ჩვენ ახლოს დასასრულს აქ, მინდა მიიღოს შენიშვნა, ალბათ, რა მერი ბეთ აკეთებს. ჩვენ გვაქვს რამდენიმე piles ჩანს, დიდი ერთი, სამი მცირე ზომის. 

აუდიტორია: მე შეკვეთით მათ როდესაც მე ორი ასო რომ მე ვიცი, რომ ერთად თანმიმდევრობით, მე დააყენა მათ ერთად ისე, რომ მე არ უნდა ფიქრი შენახვა სიმღერა მთელი რიგი წიგნები. უბრალოდ, რა, არის, პირველ რიგში, მაქვს ამ დასტის აქ. დინამიკები ასე რომ, თითქმის ისევე, თავსატეხი ცალი, რომ აქვს უფლება ფორმის შეესაბამება ერთმანეთს. აუდიტორია: საკმაოდ ბევრი, yeah. დინამიკები: OK, კარგი. და ახლა ყველა ამ piles სავარაუდოდ დახარისხებული? 

აუდიტორია: Yeah. 

დინამიკები: ყველა უფლება, მეშვეობით ზ ყველა მარჯვენა, გილოცავთ, თქვენ გააკეთა. თქვენ გაქვთ არჩევანი. Blue? ყველა უფლება, მადლობას გიხდით, რომ. ასე რომ, მერი ბეთ არ ვთავაზობ რა მისი მიდგომა იყო, მაგრამ რა არის მეორე მიდგომა, თუ როგორ შეიძლება წავიდეს დახარისხება ეს ყველაფერი? რას არ კეთდება? ჩანაწერი ცემა იქნებოდა ერთი წუთი და 50 წამი, პლუს პირობა დამავიწყდა ითვლიან. რას არ კეთდება? ჰო? აუდიტორია: Take Stack. დავიწყოთ თავიდან. შეამოწმეთ თქვენი ბიულეტენი. და თუ ყველაზე ერთი უფრო მაღალია, მეტი, შესაძლოა, ისინი, ბოლოში ერთი არის უმაღლესი, შემდეგ გადართოთ მათ. 

დინამიკები: OK, ასე იწყება ზედა და ქვედა, და შემდეგ მუშაობა თქვენს გზას შინაგანი, როგორც, რომ შევცვალე მათ? OK, ასე რომ ცოტა მსგავსი სულისკვეთება, bubble sort, მაგრამ არჩევის უკიდურესი არა მიმდებარე წყვილი. მაგრამ მოკლე ის არის, რომ იქ აუცილებლად bunch სხვადასხვა გზა ჩვენ შეგვიძლია ამის გაკეთება, და სიმართლე გითხრათ, მე ვფიქრობ, თქვენ სახის მიღებული რამდენიმე მიდგომები, არა? თქვენ გააკეთა ერთგვარი ოთხი დახარისხებული piles და მაშინ ეფექტურად შეუერთდა მათ ერთად. და ეს არის ის, daresay, სხვა ტექნიკა საერთოდ. თქვენ არ შეუძლია მას, როგორც ერთი დიდი pile, თქვენ იყოფა პრობლემა ოთხი კარე, თუ თქვენ, და მერე რაღაცნაირად მათ შეუერთდა ბოლომდე. 

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

ასე მოცემული რვა ადამიანი, რამდენი pairwise შედარება გავაკეთო ხოლო ფეხით მარცხნიდან მარჯვნივ ერთი ასეთი iteration? რამდენი შედარებები? Seven, არა? რადგან თუ არსებობს რვა ადამიანი, მაგრამ თქვენ უნდა წყვილი მათ და თქვენ გაქვთ მოძრაობს ერთ hop უფლება, თქვენ არ აპირებს რვა შედარება იმიტომ, რომ თქვენ არ შეგიძლიათ შეადაროთ ელემენტის წინააღმდეგ თავად, ან ეს იქნებოდა უბრალოდ უაზრო, ასე რომ თქვენ შვიდი. ან საერთოდ, თუ ჩვენ n ხალხი, ჩვენ გავაკეთოთ N მინუს 1 შედარებები ერთად bubble sort. 

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

ასე N მინუს 1 ნაბიჯებს პირველად, მაგრამ შემდეგ რა მოხდა ამის შემდეგ? რა არის ერთი პლიუსი ერთ უღელტეხილზე მეშვეობით სხვაგვარად არასორტირებული სიაში? რა შეგიძლიათ მითხრათ დაახლოებით ელემენტი ვინც იყო ყველა გზა იქ? ჰო? რომ იყო ყველაზე დიდი ელემენტს, არა? რვა, მიუხედავად იმისა, აქედან დაიწყო, ყოველ ჯერზე მე შედარებით მის წინააღმდეგ მეზობელი, იგი ინახება bubbling up მარჯვნივ მხარეს სიაში. და მართლაც, სადაც ალგორითმი იღებს თავისი სახელი. 

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

ახლა dot, dot, dot სახის ტალღების ეს ხელში რაღაც juicier დეტალები, მაგრამ მოდით უბრალოდ წავიდეთ წინ და გაამარტივებს. თუ გავიხსენებთ მაღალი სკოლა, სიმართლე გითხრათ, ბევრი თქვენგანი ჰქონდა მათემატიკის წიგნი რომ ჰქონდა პატარა cheat ფურცელი ყდაზე ან უკან ყდა, რომ გაჩვენეთ რა სერია summations, როგორიცაა საბოლოოდ დასძინა მდე. ზოგად შემთხვევაში, თუ თქვენ გაქვთ ცვლადი მოსწონს N, და მართლაც ამ ერთი, თუ შევხედე თქვენი ძველი სკოლის მათემატიკის წიგნი, თქვენ ხედავთ, რომ ეს, ფაქტობრივად, დასძენს მდე ეს თანხა აქ, N ჯერ N -1 ყველა დაყოფილი 2. ასე რომ, ახლა ნება მომეცით უბრალოდ ითვალისწინებს, ეს მართლაც ასეა, ასე ნახტომი რწმენის, ის, რაც ამ თანხები მდე, და ჩვენ შეგვიძლია დაამტკიცოს, რომ უფრო ზოგად შემთხვევაში. მაგრამ ახლა მოდით გაფართოებას ამ out. მოდით გავამრავლოთ ეს, ისე, რომ n კვადრატში მინუს n, ყველა დაყოფილი 2. რომ მართლაც n კვადრატში, გაყოფილი 2, მინუს N დაახლოებით 2, ასე რომ ყველა ლამაზი და საინტერესო. მაგრამ რა მოხდება, თუ ჩვენ ახლა დანამატი მნიშვნელობა? დავუშვათ, მე არ მაქვს რვა ადამიანი, თუმცა აცხადებენ, რომ მილიონი. და მილიონი მხოლოდ იმიტომ, ეს საკმაოდ დიდი რაოდენობით, მოდით plug რომ და ვნახოთ, რა მოხდება. ასე რომ, თუ მე შეაერთედ მილიონი რომ ფორმულა მე ვაპირებ კიდევ მილიონი კვადრატი, გაყოფილი 2, მინუს მილიონი, გაყოფილი 2. ახლა რა, რომ ის იქნება ტოლი? ასე რომ 500 მილიარდი, მინუს 500,000. და თუ მართლაც, რომ მათემატიკის, ანუ რომ დახარისხება მილიონი ხალხი, bubble sort შესაძლოა, მიიღოს me 499.999.500.000 ნაბიჯები, ან შედარებები, საბოლოო ჯამში, ჩვენ უბრალოდ extrapolating. 

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

[ვიდეო აღწარმოების] 

-Senator, თქვენ აქ Google, და მე მიყვარს ვფიქრობ პრეზიდენტობის გასაუბრება. ახლა, იმისთვის, რომ მიიღოთ სამუშაოს როგორც პრეზიდენტი, და თქვენ ვაპირებთ მეშვეობით rigors არის. ასევე, იმისთვის, რომ მიიღოთ სამუშაო Google. ჩვენ გვაქვს კითხვები, და ჩვენ ვთხოვთ ჩვენი კანდიდატების კითხვები, და ეს ერთი არის Larry შვიმერი. What-- ბიჭები ვფიქრობ მე kidding, ეს უფლება აქ. რა არის ყველაზე ეფექტური გზა დასალაგებლად მილიონი 32-bit რიცხვებით? 

-Well-- 

-I'm უკაცრავად, maybe-- 

არა, არა, არა. მე ვფიქრობ, რომ bubble sort იქნება არასწორი გზა აქვს გასავლელი. 

-Come On, რომელმაც უთხრა ეს? მე ვერ ვხედავ, კომპიუტერული მეცნიერების თქვენი ფონზე. 

-We've მიიღო ჩვენი მზვერავები არსებობს. 

-OK, მოდით დავსვათ სხვადასხვა ინტერვიუში კითხვაზე. 

[END ვიდეო აღწარმოების] 

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

ასე რომ, მე ხაზგასმით ყვითელი აქ შედეგი n კვადრატში გაყოფილი 2, ასე მილიონი კვადრატი გაყოფილი 2, და შემდეგ მე ხაზგასმით რა საბოლოო პასუხი იყო ერთხელ ჩვენ ჩამოჭრილია მთლიანი თანხიდან off n იყოფა 2. და აცხადებენ, მე ვაპირებ, რომ ახლა ის არის, რომელიც heck ზრუნავს თუ სხვაობა off ცოტა ძველი n მეტი 2, როდესაც პირველი ნაწილი ეს ფორმულა იმდენად დიდი? ის დომინირებს სხვა ტერმინი, n კვადრატში გაყოფილი 2 უფრო მეტია, ნათლად, როგორც n იღებს დიდი მილიონი, რომ არის მართლაც დიდი სხვაობა დღის ბოლოს შორის 500 მილიარდი და 499.999.500.000? ნამდვილად არ. და მერე რა, ჩვენ ვაპირებთ გავაკეთოთ როგორც კომპიუტერი მეცნიერები არის იგნორირება, ქვედა წესრიგის თვალსაზრისით და მსგავსი რამ და რეალურად უბრალოდ გამარტივება მას ტერმინი, რომელიც აპირებს აქვს. მით უფრო დიდია იმის მონაცემები კომპლექტი, მით უფრო დიდია, ჩვენს ბაზაში, მით უფრო ვებ გვერდები ჩვენ უნდა ვეძებოთ, უფრო მეგობრები თქვენ გაქვთ Facebook. 

როგორც n იღებს უფრო დიდი, ჩვენ მართლაც აპირებს აინტერესებს უდიდესი ტერმინი ნებისმიერი ასეთი ანალიზი ჩვენი ალგორითმები შესრულება. და მე ვაპირებ ვთქვა, თქვენ იცით, რა, bubble sort არის ბრძანებით დიდი O, ბრძანებით n კვადრატში. ეს არ არის ზუსტად n კვადრატი, როგორც ჩვენ ვნახეთ, მაგრამ, ვინც ნამდვილად ზრუნავს დაახლოებით იმ მცირე ვადები, და გულწრფელად, რომელიც ნამდვილად ზრუნავს თუ გავყოფთ 2? ეს მხოლოდ მუდმივი ფაქტორი. და 500 მილიარდი წინააღმდეგ 250 მილიარდი მართლაც რომ დიდი გარიგება? მე ვერ უბრალოდ მოეცადა ერთი წელი, მიადევნე ჩემი ლეპტოპი ფაქტიურად ორჯერ სწრაფად ტექნიკა, და რომ ერთგვარი სხვაობა მხოლოდ მიდის ბუნებრივია, დროთა განმავლობაში. 

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

ის, რაც ჩვენ არ ვაპირებთ ჯამში არის დროის რომ გადის საათი კედელზე, როგორც წესი. ის, რაც ჩვენ არ აპირებს აღელვებს იმის შესახებ, თუ რამდენი მეხსიერება თქვენ იყენებთ დღეს, მაინც, მიუხედავად იმისა, რომ კიდევ ერთი რესურსი, შეიძლება ღონისძიება. ჩვენ ვაპირებთ ცდილობენ ბაზის ჩვენი ანალიზი მხოლოდ ძირითადი ოპერაციების, ვინც, სიმართლე გითხრათ, რომ თქვენ ხედავთ, ყველაზე ვიზუალურად. ასე რომ რაღაც დიდი O of n კვადრატი, აცხადებენ, რომ O of n კვადრატში ზედა შეკრული on ე.წ. ქრონომეტრაჟი bubble sort. სხვა სიტყვებით, თუ სასურველი აცხადებენ, რომ იქ ეს ზედა ლიმიტი რამდენი ნაბიჯები ალგორითმი შესაძლოა, ეს იქნება დიდი O of n კვადრატი, ამ შემთხვევაში, ზედა ზღვარი. 

რა მოხდება, თუ ნაცვლად შეცვლა სტატია იმის შესახებ, bubble sort, მაგრამ ამ ზედა შეკრული. შეიძლება ფიქრობთ, რომ ალგორითმი რომ ჩვენ შევხედე უკვე რომლის ზედა ზღვარი, მაქსიმალური გავზომოთ დრო და ოპერაციები, რომ ითქვას, რომ ესაზღვრება by n, წრფივი ფუნქცია, არა კვადრატული ერთი, რომ curved? რა არის ალგორითმი, რომელიც ყოველთვის იღებს აღარ ვიდრე მოსწონს n ნაბიჯები, ან 2n ნაბიჯები, ან 3N ნაბიჯები? ჰო? 

აუდიტორია: დამდგენი დიდი რაოდენობის სიაში? 

დინამიკები: Perfect, მოძიებაში ყველაზე დიდი რაოდენობის სია. თუ მე მოცემულია სია ადამიანი, მაგალითად, თითოეული რომელიც მართავს ნომერი, რა არის მაქსიმალური რაოდენობის ნაბიჯები უნდა მიიღოს me, გონივრულად მოაზროვნე ადამიანს, რათა იპოვოს უმსხვილესი პირი, ამ სიაში? n, არა? რადგან უარეს შემთხვევაში, შესაძლოა, ყველაზე დიდი ღირებულება იქნება? მარჯვენა, ყველა გზა ბოლომდე. ასე რომ, უარეს შემთხვევაში ზედა ზღვარი, მე შეიძლება უნდა წავიდეთ ყველა გზა აქ და იყოს, OH, აქ რვა, ან რასაც არც. ახლა ეს მხოლოდ სულელი თუ გავაგრძელე, არა? ეძებთ უფრო და უფრო მეტი ელემენტები თუ ბოლო ერთი მათგანი არ არის იქ? ასე რომ, რა თქმა უნდა, n ზედა შეკრული. მე არ უნდა მიიღოს ნაბიჯები, ვიდრე. 

მერე რა, რომ ნაცვლად მე შევთავაზე, რომ არსებობს ალგორითმები ამ სამყაროში, აქვს გაშვებული დრო, რომ ის, ესაზღვრება დიდი O შესვლა N, შეხვიდეთ n? სადაც არ ჩვენ ვხედავთ ამ ადრე? ჰო? 

აუდიტორია: სატელეფონო წიგნი პრობლემა? დინამიკები Like სატელეფონო წიგნი პრობლემა. რა იყო ღონისძიება, თუ როგორ ბევრი დრო და რამდენი ცრემლი ის წამიყვანეს ურთიერთობა, როგორიც არის მაიკ სმიტი სატელეფონო წიგნი? ჩვენ განაცხადა, რომ ეს ჟურნალი n და მაშინაც კი, თუ იციან, ან ეს ის ცოტა ბუნდოვანი რა logarithm ან მაჩვენებლებით იყო, უბრალოდ გვახსოვდეს, რომ log n ზოგადად ეხება პროცესი, ამ შემთხვევაში, გამყოფი რაღაც ნახევარი ისევ და ისევ, და ისევ და ისევ, ისეთი, რომ ეს იღებს უფრო და უფრო პატარა, როგორც თქვენ, რომ. 

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

ახლა რა შეიძლება იყოს ეს ნიშნავს, დიდი O ერთი? ეს არ ნიშნავს, რომ თქვენი ალგორითმი იღებს ერთი და მხოლოდ ერთი ნაბიჯია, ეს მხოლოდ იმას ნიშნავს, რომ იგი იღებს მუდმივი ნაბიჯი. იქნებ ეს 1, შესაძლოა ეს 10, იქნებ ეს 1000 მაგრამ დამოუკიდებელი ზომის პრობლემა. არ აქვს მნიშვნელობა, თუ რამდენად დიდი n არის, მუდმივი დროის ალგორითმი ყოველთვის იღებს იმავე რაოდენობის ნაბიჯები. ისე რა შეიძლება იყოს ალგორითმი ჩვენ ვისაუბრეთ, ან უბრალოდ ინტუიციურად, რომ საქმე, რომ ყოველთვის გადის ე.წ. მუდმივი დროს? ჰო? 

აუდიტორია: სანიშნეს ორი ნომერი. დინამიკები სანიშნეს ორი ნომერი, 2 plus 2 შეადგენს 4 გაკეთდეს. ასე რომ, შესაძლოა, მუშაობა, რა? როგორ შესახებ უფრო რეალურ ცხოვრებაში, არა? 

აუდიტორია: დამდგენი პირველი, რაც სიაში. დინამიკები მოძიება პირველი ელემენტს სიაში, დარწმუნებული ვარ. ჩვენ რეალურად ვსაუბრობთ შესახებ კოლექტორები უკვე, როგორ იღებთ ზე პირველი ელემენტია მასივი, არ აქვს მნიშვნელობა, რამდენ ხანს array არის C კოდი? თქვენ უბრალოდ გამოყენება, როგორიცაა bracket ნულოვანი notation, bam, თქვენ იქ. და მართლაც მასივები, როგორც განზე, მხარდაჭერა რაღაც საყოველთაოდ ცნობილია როგორც შემთხვევითი წვდომის წვდომის მეხსიერება, რადგან თქვენ შეგიძლიათ სიტყვასიტყვით გადასვლა რომელიმე ადგილი. ჩვენ შეგვიძლია ამის გაკეთება კიდევ უფრო უბრალოდ ჩვენ შეგვიძლია გადახვევა კვირაში ნულოვანი როდესაც ჩვენ გავაკეთეთ Scratch. რამდენი დრო დასჭირდა, რომ ამბობენ ბლოკი Scratch შეასრულოს? მხოლოდ მუდმივი დროს, არა? ამბობენ, რომ რაღაც, ვთქვათ, რაღაც, არა აქვს მნიშვნელობა რამდენად დიდი ნაკაწრები მსოფლიოში, ის ყოველთვის აპირებს იმავე დროის უბრალოდ ვთქვა რაღაც. 

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

აუდიტორია: Bubble sort? 

დინამიკები: Bubble დალაგების იღებს თქვენ მინიმალურად N ნაბიჯები, რატომ? რატომ არის, რომ? რატომ უნდა დაწყება მოვედი თქვენთან ინტუიციურად, მაშინაც კი, თუ ეს არ არის მხოლოდ ჯერ არ გაქვთ? ჰო? 

აუდიტორია: [INAUDIBLE]. დინამიკები: ზუსტად. საუკეთესო შესაძლო სცენარი bubble sort, და ბევრი ალგორითმები, თუ მე მხრივ, რვა ადამიანი რომლებიც უკვე დახარისხებული, ეს იქნებოდა უგუნური თქვენ, ალგორითმი, წავიდეთ უკან და მეოთხე კიდევ ერთხელ, არა? იმის გამო, რომ, როგორც კი თქვენ გავლა სია ერთხელ, თქვენ უნდა გაიგოთ, რა, მე არ სვოპები, ამ სიაში დალაგებულია, გასასვლელი. მაგრამ, რომ აპირებს თქვენ N ნაბიჯები. 

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

ახლა ჩვენ გვაქვს გზა აღწერს ქვედა საზღვრები, რაც შეეხება მუდმივ დრო? რა არის ალგორითმი, რომელიც აქვს ქვედა შეკრული მისი ქრონომეტრაჟი ერთი? 1 ნაბიჯი 2 ნაბიჯი, 10 ნაბიჯები, მაგრამ მუდმივი, დამოუკიდებელი n, ზომა შეყვანის? ჰო, წელს უკან. 

აუდიტორია: Printf? დინამიკები: რა არის ეს? აუდიტორია: Printf? დინამიკები printf. OK, დარწმუნებული ვარ. ასე რომ იღებს ფიქსირებული რაოდენობის ნაბიჯები. და მე უნდა ახლა არის, რომ ჩვენ ვსაუბრობთ C კოდი და არა ნულიდან, რაღაც როგორიცაა მაგალითად, printf, ჩვენ უნდა დაიწყოს, ფრთხილად. იმის გამო, რომ printf არ მიიღოს შეყვანა, სიმებიანი, და ვიდრე არ ტექნიკურად აქვს სიგრძეზე. ასე რომ, თუ ჩვენ ახლა უნდა აირჩიოთ თქვენ, თუ არ იბადება, ტექნიკურად ჩვენ ვერ ამტკიცებენ, რომ printf არ მიიღოს ცვლადი სიგრძის input, და რა თქმა უნდა ის შესაძლოა უფრო დრო ბეჭდვა სიმებიანი ეს ხანგრძლივი, ვიდრე ამ ხნის მანძილზე. 

მერე რა, თუ გავითვალისწინებთ, მხოლოდ დახარისხება და ძიების მაგალითები? რაც შეეხება მაიკ სმიტი ტელეფონი წიგნი, ან ორობითი ძებნა, უფრო მეტი? საუკეთესო შემთხვევაში, რა შეიძლება მოხდეს? მე გახსნა სატელეფონო წიგნი და bam, არსებობს მაიკ სმიტი ნომერი. მე მოვუწოდებ მას დაუყოვნებლივ. 

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

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

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

რამდენი ნაბიჯები სჭირდება ჩემთვის იპოვოს მეორე ყველაზე პატარა ელემენტი? n-2, რადგან მე ვარ, რომ მუნჯები თუ მე შენარჩუნება ეძებს იგივე ადამიანი კიდევ ერთხელ, თუ მე უკვე აარჩია ან მისი და ამით მათ ადგილას. და მესამე ნაბიჯი, n მინუს 3, მაშინ n მინუს 4. ჩვენ ვნახეთ, რომ ეს ნიმუში ადრე, და მართლაც შერჩევის დალაგების ასეთივე აქვს ზედა ზღვარი n კვადრატში, თუ ჩვენ გავაკეთებთ, რომ summation. რა არის მისი ქვედა შეკრული, შერჩევის დალაგება? მინიმალურად, რამდენი დრო უნდა შერჩევა სახის მიიღოს, რადგან ჩვენ განვსაზღვრეთ ეს ორშაბათს? შესთავაზოს ორი ვარიანტი. იქნებ ეს n, როგორც ადრე. იქნებ ეს n კვადრატში, რადგან ის ახლა, როგორც ზედა შეკრული. 

აუდიტორია: N კვადრატში. დინამიკები: N კვადრატში. რატომ? 

აუდიტორია: იმიტომ, რომ თქვენ რათა განისაზღვროს [INAUDIBLE]. 

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

რაც შეეხება Insertion დალაგების, სადაც მე ვინც მე გადაეცა, ხოლო შემდეგ მე plopped მას ან მისი სწორი ადგილი? მერე, მეორე პირი, plopped მისთვის საჭირო ადგილას. მაშინ შემდეგი პირი, plopped მისთვის საჭირო ადგილას. გაითვალისწინეთ, რომ ეს არის ძალიან წრფივი, ასე ვთქვათ. მე სწორი ხაზი, მე არ აპირებს უკან და მეოთხე, მე არასდროს არ ეძებს უკან ნამდვილად, მაგრამ რა ხდება, როდესაც მე ჩადეთ მას ან მისი შევიდა დასაწყისში სიაში, როგორც ჩვენ ორშაბათს? რა ხდება? ჰო? აუდიტორია: [INAUDIBLE]. დინამიკები: ჰო, იყო დაჭერა, არა? თქვენ შეიძლება გავიხსენოთ თქვენი თანაკლასელები, თუ ისინი იყო, რომ ნებისმიერი მოძრაობა მათი ფეხები, რომ იყო ოპერაცია. ასე რომ, თუ სამი ადამიანი აქ და ახალ ადამიანს ეკუთვნოდა გზა იქ, ხანგრძლივი ეტაპი, როგორც ეს, რა თქმა უნდა, ის ან შეეძლო უბრალოდ ბოლომდე. მაგრამ თუ ჩვენ ფიქრი კომპიუტერი და მასივი მეხსიერება, ეს ხალხი აპირებს უნდა shuffle მეტი ოთახში, რომ პირი. და ისე, რომ n -1 shufflings, n-2 shufflings, n მინუს 3 shufflings მხოლოდ სახის ხდება ჩემს უკან, არ ჩემ თვალწინ როგორც ადრე, გარკვეული თვალსაზრისით. ახლა, როგორც განზე, და როგორც თქვენ შეიძლება არ მინახავს შემოსული თუ თქვენ დაიწყოს გააღიზიანოს გარშემო სახის, არსებობს ამდენი სხვადასხვა პირობა არსებობს, ზოგიერთი მათგანი უკეთესი, ვიდრე სხვები. მართლაც, bogosort არის ერთ ერთი რომ სახის fun ეძებოთ. Bogosort იღებს კომპლექტი ციფრები ამბობენ ან deck ბარათების, შემთხვევით shuffles მათ, და ამოწმებს, თუ ისინი დახარისხებული. და თუ არა, იმას კიდევ ერთხელ აკეთებს. და თუ არა, იმას კიდევ ერთხელ აკეთებს. თუ არა, იმას კიდევ ერთხელ აკეთებს. წარმოუდგენლად სულელური. 

და მართლაც, თუ წაიკითხავთ როგორიცაა Wikipedia article, მისი მეტსახელი არის სულელური სახის. იგი საბოლოოდ მუშაობა, იმედია, საკმარისი დრო, მაგრამ იმ დროის შეიძლება საკმაოდ გარკვეული დრო. ასე რომ, თუ შეიძლება, მოდით სიჩქარე რამ მდე Mary Beth მაგალითს ადრე, მიერ, რომელსაც რამდენიმე ელემენტები, მაგრამ კიდევ ორი ​​პროცესორი. ორი ადამიანი, თუ არ იბადება შეუერთდება ჩემთვის. როგორ შესახებ 1 აქ და მოდით წასვლა არავის იქ? არავინ იქ? OK. თქვენ black პერანგი, დიახ, მოდის ქვემოთ. ყველა უფლება, რა გქვია? 

აუდიტორია: პეტრე. 

დინამიკები: რა არის ეს? 

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

აუდიტორია: ელენა. დინამიკები: ელენა. OK, კარგია თქვენთან შეხვედრა. Elena შეხვდება პეტრე. პეტრე, ელენა. და ჩვენ უნდა Andrew აქ, ასევე, გთხოვთ. და თქვენი გამოწვევა აპირებს უნდა იყოს დასალაგებლად deck ბარათების. და თუ უცნობ, deck ბარათები უნდა, საბოლოო ჯამში, იყოს დახარისხებული პატარა რაღაც ეს სადაც ჩვენ ყველაფერს გავაკეთებთ, კლუბები, მაშინ ყვავი, მაშინ გული და ბრილიანტები, საწყისი ace როგორც ერთი, ყველა გზა მდე მეფე. 

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

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

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

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

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

[ტაში] 

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

მაგრამ სახის გამოიყენება რა მე მოვუწოდებ ძალიან განმეორებითი მიდგომა აქ, კერძოდ გაფრთხილების line 8 და ხაზი 11. იმ მტკიცებულება განმეორებითი მიდგომა, looping მიდგომა, რადგან სწორედ ქცევის ისინი გამოიწვიოს. იმ ხაზების ორივე ამბობენ წასვლა ხაზი სამი, და შეგიძლიათ სახის ვფიქრობ, რომ თქვენს გონების თვალით, როგორც loop. ის გეუბნებოდით დაბრუნდეს დაიხევს სამი და ვიმეორებ, ისევ და ისევ, და ისევ. 

მაგრამ რა, თუ ბერკეტი გასაღები იდეა აქ რომ ჩვენ არ ბოლო დროს, და გაამარტივებს line 8 და ხაზის 11 და მათი მეზობლები როგორც მხოლოდ ამ, ყვითელი. ეს არ ფუნდამენტურად შეკვეცას pseudocode ძალიან, მაგრამ ეს ძირეულად შეცვლის ბუნების ალგორითმი. რა მე ახლა ამბობს ნაბიჯი 7 ნაბიჯი 10, მოძიება Mike ზუსტად იგივე გზა, მაგრამ მხოლოდ მარცხენა ნახევარი ან მარჯვენა ნახევარში. 

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

ასე რომ, მიუხედავად იმისა, რომ ეს უნდა გრძნობდეს როგორიც ცოტა ციკლურ განმარტება სადაც თქვენ პასუხობდა ვინმეს კითხვა მხოლოდ ერთგვარი ითხოვს იგივე კითხვა ისევ, როგორიცაა, რატომ, რატომ, რატომ? რეალობა ის არის, იმიტომ, რომ ჩვენ რთული კოდირებული რამდენიმე სპეციალური ხაზები, ნაბიჯი 4, რომელიც თუ, და ნაბიჯი, რომელიც 12 ეფექტურად მორიგი ფილიალი, იმიტომ, რომ ჩვენ გვაქვს ის stopgap ღონისძიებები, ეს ალგორითმი შეწყვიტოს თუ ჩვენ მოძიების მაიკ, თუ არა. მაგრამ ნაბიჯი 7 და 10 ახლა, ჩვენ გვაქვს რა ჩვენ მოვუწოდებთ რეკურსიული ალგორითმი. და უკან არის მართლაც ძლიერი იდეა, რომ ცოტა გონება bending, პირველ რიგში, რომ ჩვენ შეგვიძლია ახლა ვრცელდება ასეთია. 

შერწყმა დალაგების იქნება ბოლო დალაგების დავაკვირდებით, მინიმუმ კლასში ფორმალურად. და ეს ძირეულად განსხვავებული იმ ბოლო სამი, და რა თქმა უნდა, ბოლო ოთხი თუ ჩვენ მოიცავს bogosort. აი pseudocode შერწყმა დალაგების. როდესაც შეყვანის N ელემენტები, ასე მოცემული მასივი ზომა n, თუ n ნაკლებია, ვიდრე 2, დაბრუნდება. ასე რომ, რატომ მაქვს, საღი აზრის შეამოწმოს პირველი? რა გავლენა თუ მე მხრივ, თქვენ მასივი, რომლის სიგრძე n ნაკლებია, ვიდრე 2? ეს უკვე დახარისხებული, ცხადია, არა? რადგან სიაში ან აქვს ერთი ელემენტი, რომელიც trivially დახარისხებული რადგან ის ერთადერთი, რაც არ არსებობს. ან, ეს ზომა ნულოვანი რაც იმას ნიშნავს, არაფერი დასალაგებლად, ამიტომ ბუნებით ეს დახარისხებული. არსებობს უბრალოდ არაფერი არასწორი არსებობს. ასე რომ ჩვენი ე.წ. ბაზის შემთხვევაში. 

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

მაგრამ აქ ნახტომი რწმენის ახლა სხვაგან, დასალაგებლად მარცხენა ნახევარში ელემენტები, მაშინ დასალაგებლად მარჯვენა ნახევარში ელემენტები, შემდეგ შერწყმა დახარისხებული halves. და აქ, სადაც იგი გრძნობს როგორც ჩვენ copping out. მე გთხოვეთ დასალაგებლად n ელემენტებს, და მე განაცხადა, ბატონო, ამის დახარისხება მარცხენა და დახარისხება უფლება. მაგრამ მე რომ ერთი სხვა რამ, და ეს არის გასაღები თემა, როგორც ჩანს, in ინტუიცია ჯერჯერობით, არსებობს ამ მესამე საფეხურის შერწყმით. რომელიც მიუხედავად იმისა, რომ როგორც ჩანს, იმდენად dumb სული, მინდა უბრალოდ შერწყმა რამ ერთად, როგორც ჩანს, იყოს გასაღები ნაბიჯი reassembly ორი პრობლემა, რომელიც დაიყო საბოლოოდ ნახევარი. 

ასე რომ შერწყმა დალაგების, მოდით, თუ თქვენ იუმორი ჩემთვის, კიდევ ერთი საპროტესტო აქცია, ასე რომ, ჩვენ გვაქვს ნომრები მუშაობა. შემიძლია გაცვლა რვა სტრესი ბურთები რვა ადამიანი? ყველა უფლება, როგორ შესახებ, სამი, ოთხი ამ სექციაში, ხუთი, ექვსი, და მოდით არ 7, 8, მოდის up. OK, yeah OK. მინუს 8, იქ წასვლა, პლუს 1. შესანიშნავი. ყველა უფლება მოდის up, მოდით სწრაფად გაძლევთ ნომრები. მეორე, მესამე, მეოთხე, ნომერი ხუთი, ექვსი, შვიდი, რვა. მე რვა სწორად ამ დროს. 

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

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

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

აუდიტორია: Darren. 

დინამიკები დან. Dan გადადგა ნაბიჯი. 

აუდიტორია: Darren. დინამიკები: Darren, გაკეთდეს. ხომ არ ამბობენ, Darren ან დენ? 

აუდიტორია: Darren. 

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

აუდიტორია: ლუკა. 

დინამიკები: ლუკა. მოდის, წინ გადადგმული ნაბიჯია. კეთდება, მე დახარისხებული ლუკა. მარცხენა ნახევარში არის გადანაწილებული და მარჯვენა ნახევარში არის დახარისხებული, თუმცა ისევ და ისევ, იქ გადამწყვეტი აქ. რა შემიძლია შემდეგი უნდა გავაკეთოთ? შერწყმა დახარისხებული halves. ახლა ჩვენ ვაპირებთ, რომ უბრალოდ უნდა ყველას უკან და მეოთხე, ამ გზით, რადგან მე სახის უნდა გარკვეული ნულიდან სივრცეში. ის თითქმის მოსწონს ეს ბიჭები არიან მაგიდა, და მე უნდა ზოგიერთი ოთახი გადაადგილება მათ გარშემო. ამიტომ, მე ვაპირებ, რომ შერწყმა თქვენ ბიჭები ეძებს მარცხენა ნახევარში და მარჯვენა ნახევარში. და ვინც აშკარად მოდის პირველი, მარცხენა ნახევარში და მარჯვენა ნახევარში? ასე რომ, მარჯვენა ნახევარში, მოდით გადაადგილება Luke მეტი აქ Darren ის პოზიციას. და ახლა შერწყმა მათი მარცხენა ნახევარში, Darren აპირებს გადავიდეს უფლება არსებობს. 

ასე რომ იგრძნობა თითქმის bubble sort ეფექტი, მაგრამ ჩემი ძირითადი ალგორითმი, ძალიან განსხვავებული ამ დროს. მაგრამ ახლა არის სადაც რამ კიდევ ცოტა შემაშფოთებელი იმიტომ, რომ თქვენ უნდა გადახვევა გონებრივად სად დატოვება მოჰყვა. მე უბრალოდ შეუერთდა დახარისხებული halves, რაც იმას ნიშნავს, რომ მე ვარ, სადაც ჩემი ალგორითმი? მე უნდა დასალაგებლად მარჯვენა ნახევარში, არა? 

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

აუდიტორია: Adriano. 

დინამიკები: Adriano. Adriano არის გადანაწილებული. და რა გქვია? 

აუდიტორია: Alex. 

დინამიკები: Alex არის გადანაწილებული. მარცხენა ნახევარში, მარჯვენა ნახევარში, რა არის საბოლოო ნაბიჯი? შერწყმა. საკმაოდ ტრივიალური, ასე რომ მე ვაპირებთ შერწყმა ექვს, ერთი ნაბიჯი უკან, რვა, ერთი ნაბიჯი უკან. და ახლა შეამჩნია ეს არის სასარგებლო takeaway, რა არის ჭეშმარიტია მარცხენა ნახევარში სიაში, მიუხედავად იმისა, თუ როგორ დაიწყო? ეს დახარისხებული. 

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

აუდიტორია: ომარ. 

დინამიკები: Omar, წინ გადადგმული ნაბიჯია, გაკეთდეს. მარცხენა ნახევარში დალაგებულია. და რა გქვია? 

აუდიტორია: Chris. 

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

აუდიტორია: მარინა. 

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

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

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

ახლა მოდით დავამთავროთ ეს up სწრაფად. ამიტომ სამი მოდის მომდევნო, მაშინ ოთხი მოდის მომდევნო, და ახლა ხუთი მოდის შემდეგ, მაშინ ექვსი, და შვიდი, და მაშინ საბოლოოდ რვა. იგრძნობა ნელი ალგორითმი არ არის, მაგრამ თუ ჩვენ რეალურად აწარმოებს მას იგივე სახის საათის სიჩქარე, ასე ვთქვათ, იგივე ticking საათი, როგორც ადრე. რატომ? კარგად, მოდით შეხედეთ ბოლოს შედეგი. 

მოდით დავუბრუნდეთ მეტი აქ, ნება მომეცით დახევის up აქცია ვიზუალურად ის, რაც ჩვენ გავაკეთეთ. მასშტაბირება აქ, ამ აქ, ვეუბნებოდი Firefox ჩვენ გვინდა, რომ რიგი up ამ ყუთში, მოდით ამბობენ, bubble sort, რომელთანაც ჩვენ უკვე კარგად ნაცნობი, შერჩევის დალაგების, რომელიც სხვა საკმაოდ მარტივია ერთი, და ახლა დღევანდელი შერწყმა ჯიშია, იქნება ჩვენი კლიმატური დასასრული. მიზეზი დასჭირდა იმდენად აღარ აქ ადამიანებს და მომაყენა არის, ცხადია, მე ვუხსნიდი, ყოველი ნაბიჯი. მაგრამ თუ უბრალოდ შეასრულოს ამ, ბევრად როგორც ჩვენ bubble sort და შერჩევა სახის არა მხოლოდ ვიზუალურად, watch რამდენად უფრო ეფექტურად ამ leveraging of სამმართველოს და დაპყრობის შეიძლება მიმართა მონაცემები კომპლექტი, არის კი არა ზომის რვა, მაგრამ კიდევ ბევრი რამ, გაცილებით დიდია. მე გაძლევთ შერწყმა დალაგების, გვერდით მხარე ამ სხვა ალგორითმები. ეს აპირებს მიიღოს მტკივნეული სწრაფად და დასასრულით არ არის განსაკუთრებით climactic, ისინი უბრალოდ დასრულდება up დახარისხებული. მაგრამ მთავარი წართმევას ის არის, რომ შეხედეთ, როგორ ბევრად უფრო სწრაფად შერწყმა დალაგების იყო, თუ ფიქრობთ, რომ მე ვარ უბრალოდ სახის ძვირფასი თქვენთვის. თუ ამას ერთი საბოლოო დრო, მოდით განაახლეთ ეს, მოდით დავუბრუნდეთ და bubble sort, და მხოლოდ ჩათვლით, მოდით ავირჩიოთ ჩასმა სახის, უბრალოდ კარგი ღონისძიება. და ამ დროს ისევ, მოდით აირჩიეთ შერწყმა დალაგების და მოდით რეალურად აწარმოებს ამ გვერდით. 

და ეს არ არის, ფაქტობრივად, fluke. რა მე ეფექტურად ვაკეთებ არის მე გაყოფილი ჩემი input ნახევარი, კიდევ ერთხელ, და ისევ და ისევ. და არსებობს მხოლოდ იმდენად ბევრი ჯერ თქვენ შეგიძლიათ გაყოფა თქვენი წვლილი halves, მარცხენა და მარჯვენა. რა არის ფორმულა, რომ ჩვენ ვხედავთ რომელიც ასახავს სამმართველოს ნახევარი ისევ და ისევ, და ისევ და ისევ? 

აუდიტორია: შესვლა n. 

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

ასე რომ, ეს მინიმალურად log n ნაბიჯები, მაგრამ რაც შეეხება ამ გასაღები შერწყმის ნაბიჯი სადაც გაერთიანდა ჩემი მარცხენა ნახევარში და მარჯვენა ნახევარი და გაიარა ეტაპი? რამდენი ნაბიჯების რომ შერწყმა? ის n, მაგრამ მე არა მხოლოდ შერწყმა საბოლოო დრო. თითოეულ ამ წყობილი ზარები, თითოეულ იმ წყობილი უერთდება, მე მაინც ინახება. გაერთიანდა ეს ორი ბიჭები, მაშინ ამ ორი ბიჭები, მაშინ ამ ორი ბიჭები და სხვ. 

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

და მართლაც, ის, რაც მივაღწიეთ აქ. ასე გრძნობს, რომ ხედავთ ვიზუალურად როდესაც ეს სამი რამ აწარმოებს გვერდით n კვადრატში წინააღმდეგ n კვადრატი წინააღმდეგ N შესვლა n. ფუნდამენტურად ვნახავთ, არა მარტო დღეს, არამედ მომავალში, ბევრად, ბევრად უფრო სწრაფად. რაუნდი ტაში ამ ბიჭებს, მე დააჯილდოებს მათ სტრესი ბურთები. მოდით adjourn დღეს აქ, და ვნახავთ თქვენ ორშაბათს.