1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> დინამიკები: ყველა უფლება, ეს არის CS50. 3 00:00:14,910 --> 00:00:19,020 ეს არის ბოლომდე კვირაში სამი, და თუ თქვენ არ მიუღიათ უპირატესობა უკვე, 4 00:00:19,020 --> 00:00:21,790 ვიცი, რომ იქნება ლანჩი ამ პარასკევს, როგორც ყოველთვის, სადაც 5 00:00:21,790 --> 00:00:25,430 შეგიძლიათ ისიამოვნოთ კარგი საუბარი და საკვები, ცეცხლი და ყინულის 6 00:00:25,430 --> 00:00:27,980 რამდენიმე ერთი CS50 პერსონალის და თანაკლასელები. 7 00:00:27,980 --> 00:00:30,170 უხელმძღვანელებს ამ URL აქ. 8 00:00:30,170 --> 00:00:33,420 >> ახლა თქვენ შეიძლება გავიხსენოთ, ან თქვენ მალე გაეცნო, 9 00:00:33,420 --> 00:00:35,970 ეს ყველაფერი აქ, რაც გაცემული ბოლოს 10 00:00:35,970 --> 00:00:37,850 სემესტრის ბევრი კლასების. 11 00:00:37,850 --> 00:00:40,870 ე.წ. გამოცდა ლურჯი წიგნი, რომელიც თქვენ თქვენი პასუხი გამოცდები. 12 00:00:40,870 --> 00:00:44,240 ახლა მაქვს 26 ასეთი ლურჯი წიგნი, თითოეულ მათგანს 13 00:00:44,240 --> 00:00:47,580 წერია სახელი, მეშვეობით ზ And მართლაც სახელები, რომ უბრალო, 14 00:00:47,580 --> 00:00:50,490 მეშვეობით ზ ხოლო ერთი ის მიზნები, ხელი დღეს 15 00:00:50,490 --> 00:00:53,910 იქნება გავაგრძელოთ ის, რაც ჩვენ დავიწყეთ ორშაბათს, რომელიც არ არის 16 00:00:53,910 --> 00:00:57,830 იმდენად ეძებს კოდი, მაგრამ რეალურად ეძებს იდეები და პრობლემის გადაჭრის. 17 00:00:57,830 --> 00:01:00,170 ერთი მიზანი და დაპირებები ამ კურსის 18 00:01:00,170 --> 00:01:02,985 უნდა ვისწავლოთ ვფიქრობ უფრო ფრთხილად, უფრო მეთოდურად, 19 00:01:02,985 --> 00:01:05,400 და პრობლემების უფრო ეფექტურად. 20 00:01:05,400 --> 00:01:09,526 და მართლაც, ჩვენ შეგვიძლია გავაკეთოთ, რომ ნამდვილად გარეშე კი ეხება ხაზი კოდი. 21 00:01:09,526 --> 00:01:12,150 ასე რომ, მე მაქვს რამდენიმე სპილოები აქ დღეს, ნარინჯისფერი და ლურჯი, 22 00:01:12,150 --> 00:01:15,780 თუ ჩვენ ვერ ერთი მოხალისე, შესაძლოა, კიდევ უფრო უკან, ვიდრე ჩვეულებრივი. 23 00:01:15,780 --> 00:01:18,070 როგორ შესახებ სწორედ იქ, მოდის ქვემოთ. 24 00:01:18,070 --> 00:01:24,180 რომლის მიზანი იქნება, რომ დაეხმაროს პლუს ადმინისტრირება ამ გამოცდის აქ. 25 00:01:24,180 --> 00:01:24,935 რა გქვია? 26 00:01:24,935 --> 00:01:25,768 >> აუდიტორია: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 დინამიკები: Mary Beth, მოდის up. 28 00:01:27,560 --> 00:01:29,560 ნება მომეცით კიდევ მიკროფონი აქ თქვენ. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 კარგია თქვენთან შეხვედრა. 31 00:01:32,880 --> 00:01:34,005 >> აუდიტორია: კარგია თქვენთან შეხვედრა. 32 00:01:34,005 --> 00:01:36,790 დინამიკები: ყველა უფლება, ამიტომ მე არ მაქვს აქ blue წიგნები მეშვეობით Z, 33 00:01:36,790 --> 00:01:41,680 და მე ვაპირებ, ვიტყვი, რომ მე მაქვს ერთი სტუდენტი, 34 00:01:41,680 --> 00:01:45,770 და ისინი მომავალი გარკვეულწილად შემთხვევით ბოლოს სამი საათიანი გამოცდა ბლოკი, 35 00:01:45,770 --> 00:01:49,400 ამიტომ ისინი დამთავრებული ზოგიერთი ნახევრად შემთხვევითი მიზნით მოსწონს ეს. 36 00:01:49,400 --> 00:01:54,510 ახლა თქვენი სამუშაო, რაღაც მომენტში ხდება to be-- ეს არის რეალურად, თუ როგორ იღებენ 37 00:01:54,510 --> 00:01:56,820 დღევანდელი ბოლოს კლასის, სავარაუდოდ. 38 00:01:56,820 --> 00:02:01,120 თქვენი სამუშაო არის, იქნება, საკმაოდ უბრალოდ, ახარისხებენ ლურჯი წიგნები us 39 00:02:01,120 --> 00:02:05,220 საწყისი მეშვეობით ზ 40 00:02:05,220 --> 00:02:08,400 >> აუდიტორია: ოჰ, ეს აპირებს სამუდამოდ. 41 00:02:08,400 --> 00:02:13,747 >> დინამიკები და ჩვენ დავაკვირდებით როგორც თქვენ ამის გაკეთება, არ ზეწოლა. 42 00:02:13,747 --> 00:02:15,330 აუდიტორია: არა, არა, ზეწოლის ან არაფერი. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> დინამიკები და გასართობად, მოდით დააყენა up ტაიმერი. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> აუდიტორია: ასე რომ ბევრი fun, იმდენად fun. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> დინამიკები შემიძლია გამართავს მიკროფონი თქვენთვის. 49 00:02:38,574 --> 00:02:40,240 ყველა უფლება, ჩვენ უბრალოდ გაორმაგდა ჩვენი სიჩქარე. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 ასე რომ, იმავდროულად, ნება მომეცით უქმნის რა არის იქნება კითხვა Mary Beth 52 00:02:49,060 --> 00:02:51,540 არის რა ის აკეთებს, როგორ არის იგი აპირებს გადაჭრას ეს? 53 00:02:51,540 --> 00:02:54,040 და ფაქტობრივად, თქვენ შეიძლება არ აქვს არასოდეს მიფიქრია, რომ რაღაც 54 00:02:54,040 --> 00:02:57,440 ისე მარტივია, როგორც, როდესაც თქვენ აირჩიოთ up 26 წიგნი ასე, 55 00:02:57,440 --> 00:02:59,350 რომელიც არ აქვს ბუნებრივი შეკვეთით მათ. 56 00:02:59,350 --> 00:03:01,335 რა არის პროცესი რომ თქვენ ნამდვილად გამოიყენოს? 57 00:03:01,335 --> 00:03:03,770 ეს არის საკმაოდ შემთხვევითი მხოლოდ კრეფა პირველი ხედავთ 58 00:03:03,770 --> 00:03:05,250 და აყენებს მას თავის ადგილს? 59 00:03:05,250 --> 00:03:09,680 მიგაჩნიათ თუ არა პირველი გადაადგილება თქვენი ხელები გარშემო ეძებს შემდეგ ეძებს B? 60 00:03:09,680 --> 00:03:11,722 მიგაჩნიათ თუ არა მიიღოს შევხედოთ წყვილი მათ გვერდით 61 00:03:11,722 --> 00:03:14,680 და უბრალოდ, ვამბობთ, დაველოდოთ წუთში, ამ არ არის სწორი, შემდეგ სვოპ ბრძანებით? 62 00:03:14,680 --> 00:03:16,960 ჩვენ ვნახეთ, უკვე ორშაბათს რომ არსებობს მთელი რიგი გზები 63 00:03:16,960 --> 00:03:22,140 რომელშიც ჩვენ შეგვიძლია ამის გაკეთება, და მართლაც, როგორც ჩვენ ახლოს დასასრულს აქ, 64 00:03:22,140 --> 00:03:26,360 მინდა მიიღოს შენიშვნა, ალბათ, რა მერი ბეთ აკეთებს. 65 00:03:26,360 --> 00:03:30,040 ჩვენ გვაქვს რამდენიმე piles ჩანს, დიდი ერთი, სამი მცირე ზომის. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> აუდიტორია: მე შეკვეთით მათ როდესაც მე ორი ასო 68 00:03:36,415 --> 00:03:39,540 რომ მე ვიცი, რომ ერთად თანმიმდევრობით, მე დააყენა მათ ერთად ისე, რომ მე არ 69 00:03:39,540 --> 00:03:42,915 უნდა ფიქრი შენახვა სიმღერა მთელი რიგი წიგნები. 70 00:03:42,915 --> 00:03:45,706 უბრალოდ, რა, არის, პირველ რიგში, მაქვს ამ დასტის აქ. 71 00:03:45,706 --> 00:03:47,580 დინამიკები ასე რომ, თითქმის ისევე, თავსატეხი ცალი, რომ 72 00:03:47,580 --> 00:03:49,860 აქვს უფლება ფორმის შეესაბამება ერთმანეთს. 73 00:03:49,860 --> 00:03:51,026 აუდიტორია: საკმაოდ ბევრი, yeah. 74 00:03:51,026 --> 00:03:55,320 დინამიკები: OK, კარგი. 75 00:03:55,320 --> 00:03:59,850 და ახლა ყველა ამ piles სავარაუდოდ დახარისხებული? 76 00:03:59,850 --> 00:04:00,990 >> აუდიტორია: Yeah. 77 00:04:00,990 --> 00:04:09,900 >> დინამიკები: ყველა უფლება, მეშვეობით ზ ყველა მარჯვენა, გილოცავთ, თქვენ გააკეთა. 78 00:04:09,900 --> 00:04:11,461 თქვენ გაქვთ არჩევანი. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 ყველა უფლება, მადლობას გიხდით, რომ. 81 00:04:13,530 --> 00:04:16,679 ასე რომ, მერი ბეთ არ ვთავაზობ რა მისი მიდგომა იყო, 82 00:04:16,679 --> 00:04:19,720 მაგრამ რა არის მეორე მიდგომა, თუ როგორ შეიძლება წავიდეს დახარისხება ეს ყველაფერი? 83 00:04:19,720 --> 00:04:21,130 რას არ კეთდება? 84 00:04:21,130 --> 00:04:24,060 ჩანაწერი ცემა იქნებოდა ერთი წუთი და 50 წამი, 85 00:04:24,060 --> 00:04:26,039 პლუს პირობა დამავიწყდა ითვლიან. 86 00:04:26,039 --> 00:04:27,080 რას არ კეთდება? 87 00:04:27,080 --> 00:04:27,579 ჰო? 88 00:04:27,579 --> 00:04:28,735 აუდიტორია: Take Stack. 89 00:04:28,735 --> 00:04:29,776 დავიწყოთ თავიდან. 90 00:04:29,776 --> 00:04:32,284 შეამოწმეთ თქვენი ბიულეტენი. 91 00:04:32,284 --> 00:04:36,586 და თუ ყველაზე ერთი უფრო მაღალია, მეტი, შესაძლოა, ისინი, 92 00:04:36,586 --> 00:04:38,980 ბოლოში ერთი არის უმაღლესი, შემდეგ გადართოთ მათ. 93 00:04:38,980 --> 00:04:41,300 >> დინამიკები: OK, ასე იწყება ზედა და ქვედა, 94 00:04:41,300 --> 00:04:43,716 და შემდეგ მუშაობა თქვენს გზას შინაგანი, როგორც, რომ შევცვალე მათ? 95 00:04:43,716 --> 00:04:46,580 OK, ასე რომ ცოტა მსგავსი სულისკვეთება, bubble sort, 96 00:04:46,580 --> 00:04:49,160 მაგრამ არჩევის უკიდურესი არა მიმდებარე წყვილი. 97 00:04:49,160 --> 00:04:52,080 მაგრამ მოკლე ის არის, რომ იქ აუცილებლად bunch სხვადასხვა გზა 98 00:04:52,080 --> 00:04:54,210 ჩვენ შეგვიძლია ამის გაკეთება, და სიმართლე გითხრათ, მე ვფიქრობ, თქვენ სახის 99 00:04:54,210 --> 00:04:55,700 მიღებული რამდენიმე მიდგომები, არა? 100 00:04:55,700 --> 00:05:00,567 თქვენ გააკეთა ერთგვარი ოთხი დახარისხებული piles და მაშინ ეფექტურად შეუერთდა მათ ერთად. 101 00:05:00,567 --> 00:05:02,650 და ეს არის ის, daresay, სხვა ტექნიკა საერთოდ. 102 00:05:02,650 --> 00:05:06,950 თქვენ არ შეუძლია მას, როგორც ერთი დიდი pile, თქვენ იყოფა პრობლემა ოთხი კარე, 103 00:05:06,950 --> 00:05:09,820 თუ თქვენ, და მერე რაღაცნაირად მათ შეუერთდა ბოლომდე. 104 00:05:09,820 --> 00:05:13,410 >> ასე რომ, მოდით განიხილავს, საბოლოო ჯამში, როგორ სხვაგან ჩვენ შეიძლება ამის გაკეთება. 105 00:05:13,410 --> 00:05:15,860 ჩვენ გაფორმდება ცნება bubble sort, ბოლო დროს, 106 00:05:15,860 --> 00:05:18,780 და bubble sort გაწვევა ალგორითმი, რომ ჩვენ ვიზუალიზირდება 107 00:05:18,780 --> 00:05:22,640 რვა თქვენი თანაკლასელები აქ, როგორც ჩანს, შემთხვევით დახარისხებული პირველი. 108 00:05:22,640 --> 00:05:26,110 და ჩვენ გადავწყვიტეთ, pairwise, თუ ორი ელემენტები მწყობრიდან, 109 00:05:26,110 --> 00:05:26,950 უბრალოდ სვოპ მათ. 110 00:05:26,950 --> 00:05:28,930 ისე ოთხი და ორი აშკარად მწყობრიდან, 111 00:05:28,930 --> 00:05:31,080 ასე რომ, ეს ორი თანაკლასელები შეცვალა პოზიციები. 112 00:05:31,080 --> 00:05:35,390 და მაშინ ჩვენ განმეორებითი ოთხი და ექვსი, მაშინ ექვსი და რვა, თითოეულ iteration 113 00:05:35,390 --> 00:05:36,980 გადასვლის უფლება. 114 00:05:36,980 --> 00:05:42,590 >> ასე მოცემული რვა ადამიანი, რამდენი pairwise შედარება გავაკეთო ხოლო ფეხით 115 00:05:42,590 --> 00:05:45,220 მარცხნიდან მარჯვნივ ერთი ასეთი iteration? 116 00:05:45,220 --> 00:05:48,410 რამდენი შედარებები? 117 00:05:48,410 --> 00:05:49,197 Seven, არა? 118 00:05:49,197 --> 00:05:51,405 რადგან თუ არსებობს რვა ადამიანი, მაგრამ თქვენ უნდა წყვილი 119 00:05:51,405 --> 00:05:53,880 მათ და თქვენ გაქვთ მოძრაობს ერთ hop უფლება, 120 00:05:53,880 --> 00:05:56,060 თქვენ არ აპირებს რვა შედარება იმიტომ, რომ თქვენ არ შეგიძლიათ შეადაროთ 121 00:05:56,060 --> 00:05:59,226 ელემენტის წინააღმდეგ თავად, ან ეს იქნებოდა უბრალოდ უაზრო, ასე რომ თქვენ შვიდი. 122 00:05:59,226 --> 00:06:01,290 ან საერთოდ, თუ ჩვენ n ხალხი, ჩვენ 123 00:06:01,290 --> 00:06:04,300 გავაკეთოთ N მინუს 1 შედარებები ერთად bubble sort. 124 00:06:04,300 --> 00:06:08,150 >> ასე რომ, მოდით ახლა განვიხილოთ, თუ რამდენად კარგი ან ცუდი bubble sort რეალურად იყო, და ცდილობენ 125 00:06:08,150 --> 00:06:13,570 მისცეს საკუთარ თავს ლექსიკა , რომელიც კრიტიკა ალგორითმები როგორიცაა ამ, 126 00:06:13,570 --> 00:06:14,430 და მალე ჩვენი საკუთარი. 127 00:06:14,430 --> 00:06:16,970 ასე რომ, პირველი გადის bubble sort, პირველად 128 00:06:16,970 --> 00:06:20,909 მე ფეხით მარცხნიდან მარჯვნივ გასწვრივ ეტაპზე, წამიყვანეს N მინუს 1 შედარებები. 129 00:06:20,909 --> 00:06:22,950 და ეს იქნება ჩემი ერთეული ზომის, არა? 130 00:06:22,950 --> 00:06:26,170 მე სახის საუბარი და ფეხით, გარკვეულწილად სწრაფი, გარკვეულწილად ნელი, 131 00:06:26,170 --> 00:06:29,300 ასე დათვლის ჩემი წამში არ არის განსაკუთრებით ვეუბნებოდი, 132 00:06:29,300 --> 00:06:32,260 მაგრამ დათვლის ოპერაცია, რომ მე ორშაბათს, 133 00:06:32,260 --> 00:06:35,900 შედარებით ორი ადამიანი, რომელიც გრძნობს, მსგავსი ლამაზი ერთეული ზომის. 134 00:06:35,900 --> 00:06:40,980 >> ასე N მინუს 1 ნაბიჯებს პირველად, მაგრამ შემდეგ რა მოხდა ამის შემდეგ? 135 00:06:40,980 --> 00:06:46,610 რა არის ერთი პლიუსი ერთ უღელტეხილზე მეშვეობით სხვაგვარად არასორტირებული სიაში? 136 00:06:46,610 --> 00:06:49,840 რა შეგიძლიათ მითხრათ დაახლოებით ელემენტი ვინც იყო ყველა გზა იქ? 137 00:06:49,840 --> 00:06:51,300 ჰო? 138 00:06:51,300 --> 00:06:52,870 რომ იყო ყველაზე დიდი ელემენტს, არა? 139 00:06:52,870 --> 00:06:55,710 რვა, მიუხედავად იმისა, აქედან დაიწყო, ყოველ ჯერზე მე 140 00:06:55,710 --> 00:06:57,860 შედარებით მის წინააღმდეგ მეზობელი, იგი ინახება 141 00:06:57,860 --> 00:07:00,480 bubbling up მარჯვნივ მხარეს სიაში. 142 00:07:00,480 --> 00:07:02,710 და მართლაც, სადაც ალგორითმი იღებს თავისი სახელი. 143 00:07:02,710 --> 00:07:07,630 >> ახლა ამ ლოგიკით, რამდენი შედარებები უნდა მე მეორე დრო 144 00:07:07,630 --> 00:07:09,800 მე, რომ უღელტეხილზე მარცხნიდან მარჯვნივ? 145 00:07:09,800 --> 00:07:10,730 n-2, არა? 146 00:07:10,730 --> 00:07:14,297 ეს იქნებოდა მხოლოდ კარგვაა ჩემი დრო, თუ მე შენარჩუნება შედარებით რვა ვინმეს წინააღმდეგ 147 00:07:14,297 --> 00:07:16,630 სხვა ჩვენ ვიცით, ის იყო სწორი ადგილი. 148 00:07:16,630 --> 00:07:19,760 ასე რომ, ცოტა ოპტიმიზაცია, ასე რომ მომავალი უღელტეხილზე 149 00:07:19,760 --> 00:07:23,899 იქნება plus N მინუს ორი ნაბიჯი, სადაც n რაოდენობის ხალხი. 150 00:07:23,899 --> 00:07:26,940 ახლა თქვენ შეგიძლიათ სახის განზოგადების, მაშინაც კი, თუ თქვენ არ კომპიუტერის მეცნიერი, 151 00:07:26,940 --> 00:07:27,680 როგორ ეს დამთავრდა. 152 00:07:27,680 --> 00:07:31,259 ბოლოს ეს ალგორითმი, სავარაუდოდ, თქვენ მოხვდით მხოლოდ ერთი შედარებით დატოვა. 153 00:07:31,259 --> 00:07:33,800 თქვენ უნდა სახის დაფიქსირება დასაწყისში სიაში შემთხვევაში ორ 154 00:07:33,800 --> 00:07:36,540 და ერთი მწყობრიდან და უნდა იყოს ერთი და ორი, 155 00:07:36,540 --> 00:07:40,330 ასე რომ, ეს bottoms გამოსვლით პლუს 1 საბოლოო შედარება. 156 00:07:40,330 --> 00:07:44,500 >> ახლა dot, dot, dot სახის ტალღების ეს ხელში რაღაც juicier დეტალები, 157 00:07:44,500 --> 00:07:46,452 მაგრამ მოდით უბრალოდ წავიდეთ წინ და გაამარტივებს. 158 00:07:46,452 --> 00:07:48,660 თუ გავიხსენებთ მაღალი სკოლა, სიმართლე გითხრათ, ბევრი თქვენგანი 159 00:07:48,660 --> 00:07:50,340 ჰქონდა მათემატიკის წიგნი რომ ჰქონდა პატარა cheat ფურცელი 160 00:07:50,340 --> 00:07:52,550 ყდაზე ან უკან ყდა, რომ გაჩვენეთ 161 00:07:52,550 --> 00:07:56,400 რა სერია summations, როგორიცაა საბოლოოდ დასძინა მდე. 162 00:07:56,400 --> 00:07:59,600 ზოგად შემთხვევაში, თუ თქვენ გაქვთ ცვლადი მოსწონს N, და მართლაც ამ ერთი, 163 00:07:59,600 --> 00:08:01,634 თუ შევხედე თქვენი ძველი სკოლის მათემატიკის წიგნი, 164 00:08:01,634 --> 00:08:04,050 თქვენ ხედავთ, რომ ეს, ფაქტობრივად, დასძენს მდე ეს თანხა აქ, 165 00:08:04,050 --> 00:08:07,970 N ჯერ N -1 ყველა დაყოფილი 2. 166 00:08:07,970 --> 00:08:11,172 ასე რომ, ახლა ნება მომეცით უბრალოდ ითვალისწინებს, ეს მართლაც ასეა, ასე ნახტომი რწმენის, 167 00:08:11,172 --> 00:08:12,880 ის, რაც ამ თანხები მდე, და ჩვენ შეგვიძლია 168 00:08:12,880 --> 00:08:14,341 დაამტკიცოს, რომ უფრო ზოგად შემთხვევაში. 169 00:08:14,341 --> 00:08:15,590 მაგრამ ახლა მოდით გაფართოებას ამ out. 170 00:08:15,590 --> 00:08:19,920 მოდით გავამრავლოთ ეს, ისე, რომ n კვადრატში მინუს n, ყველა დაყოფილი 2. 171 00:08:19,920 --> 00:08:23,200 რომ მართლაც n კვადრატში, გაყოფილი 2, მინუს N დაახლოებით 2, 172 00:08:23,200 --> 00:08:25,010 ასე რომ ყველა ლამაზი და საინტერესო. 173 00:08:25,010 --> 00:08:27,060 მაგრამ რა მოხდება, თუ ჩვენ ახლა დანამატი მნიშვნელობა? 174 00:08:27,060 --> 00:08:29,724 დავუშვათ, მე არ მაქვს რვა ადამიანი, თუმცა აცხადებენ, რომ მილიონი. 175 00:08:29,724 --> 00:08:31,890 და მილიონი მხოლოდ იმიტომ, ეს საკმაოდ დიდი რაოდენობით, 176 00:08:31,890 --> 00:08:34,039 მოდით plug რომ და ვნახოთ, რა მოხდება. 177 00:08:34,039 --> 00:08:39,039 ასე რომ, თუ მე შეაერთედ მილიონი რომ ფორმულა მე ვაპირებ კიდევ მილიონი კვადრატი, 178 00:08:39,039 --> 00:08:42,868 გაყოფილი 2, მინუს მილიონი, გაყოფილი 2. 179 00:08:42,868 --> 00:08:44,159 ახლა რა, რომ ის იქნება ტოლი? 180 00:08:44,159 --> 00:08:47,354 ასე რომ 500 მილიარდი, მინუს 500,000. 181 00:08:47,354 --> 00:08:49,270 და თუ მართლაც, რომ მათემატიკის, ანუ 182 00:08:49,270 --> 00:08:53,920 რომ დახარისხება მილიონი ხალხი, bubble sort 183 00:08:53,920 --> 00:09:01,800 შესაძლოა, მიიღოს me 499.999.500.000 ნაბიჯები, ან შედარებები, საბოლოო ჯამში, 184 00:09:01,800 --> 00:09:02,900 ჩვენ უბრალოდ extrapolating. 185 00:09:02,900 --> 00:09:06,860 >> რომ გრძნობს საკმაოდ ნელი, მაგრამ გულწრფელად საზომი ერთ კონკრეტულ input 186 00:09:06,860 --> 00:09:09,160 , როგორც ეს, არ არის, რომ ვეუბნებოდი. 187 00:09:09,160 --> 00:09:14,050 მაგრამ ეს ნამდვილად არ ვარაუდობს, რომ როგორც n იღებს უფრო დიდი და უფრო დიდი, ეს ალგორითმი 188 00:09:14,050 --> 00:09:16,280 სახის გრძნობს უარესი და უარესი, თუ თქვენ ნამდვილად 189 00:09:16,280 --> 00:09:20,450 დაიწყოს თავს ტკივილი პოტენცირება, რომელიც n კვადრატში, 190 00:09:20,450 --> 00:09:21,770 რომელიც დასძენს მდე საკმაოდ სწრაფად. 191 00:09:21,770 --> 00:09:25,340 და ეს დეტალი არ არის დაკარგული ადამიანები, ფაქტიურად 192 00:09:25,340 --> 00:09:29,640 რამდენიმე წლის წინ, გარკვეული სენატორი ვინც იყო კამპანიის დაჯდა ინტერვიუში 193 00:09:29,640 --> 00:09:32,180 Google-ის ერიკ Schmidt, აღმასრულებელი დირექტორი, იმ დროს, 194 00:09:32,180 --> 00:09:36,380 და დადგა კითხვა ისევე როგორც ჩვენ განიხილავს დღეს. 195 00:09:36,380 --> 00:09:38,468 მოდით შევხედოთ. 196 00:09:38,468 --> 00:09:45,280 >> [ვიდეო აღწარმოების] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, თქვენ აქ Google, და მე მიყვარს 198 00:09:48,560 --> 00:09:53,382 ვფიქრობ პრეზიდენტობის გასაუბრება. 199 00:09:53,382 --> 00:09:56,434 ახლა, იმისთვის, რომ მიიღოთ სამუშაოს როგორც პრეზიდენტი, 200 00:09:56,434 --> 00:09:58,100 და თქვენ ვაპირებთ მეშვეობით rigors არის. 201 00:09:58,100 --> 00:10:01,860 ასევე, იმისთვის, რომ მიიღოთ სამუშაო Google. 202 00:10:01,860 --> 00:10:05,490 ჩვენ გვაქვს კითხვები, და ჩვენ ვთხოვთ ჩვენი კანდიდატების კითხვები, 203 00:10:05,490 --> 00:10:09,770 და ეს ერთი არის Larry შვიმერი. 204 00:10:09,770 --> 00:10:14,760 What-- ბიჭები ვფიქრობ მე kidding, ეს უფლება აქ. 205 00:10:14,760 --> 00:10:17,930 რა არის ყველაზე ეფექტური გზა დასალაგებლად მილიონი 32-bit რიცხვებით? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -I'm უკაცრავად, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> არა, არა, არა. 210 00:10:27,400 --> 00:10:30,700 მე ვფიქრობ, რომ bubble sort იქნება არასწორი გზა აქვს გასავლელი. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Come On, რომელმაც უთხრა ეს? 213 00:10:38,180 --> 00:10:40,590 მე ვერ ვხედავ, კომპიუტერული მეცნიერების თქვენი ფონზე. 214 00:10:40,590 --> 00:10:42,130 >> -We've მიიღო ჩვენი მზვერავები არსებობს. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, მოდით დავსვათ სხვადასხვა ინტერვიუში კითხვაზე. 217 00:10:48,444 --> 00:10:49,300 >> [END ვიდეო აღწარმოების] 218 00:10:49,300 --> 00:10:52,290 >> დინამიკები ასე ლაპარაკი კონკრეტული ციფრები, თუმცა, 219 00:10:52,290 --> 00:10:53,890 არ იქნება ყველა რომ სასარგებლოა. 220 00:10:53,890 --> 00:10:56,810 ეს არ არის ცხოვრების გაკვეთილი, რომ ბუშტი სახის, იმის გათვალისწინებით, მილიონი საშუალებებით, 221 00:10:56,810 --> 00:10:58,590 შეიძლება მიიღოს როგორც ბევრი როგორც 500 მილიარდი ნაბიჯები. 222 00:10:58,590 --> 00:11:01,120 თქვენ ნამდვილად არ განზოგადება ძალიან ეფექტურად, რომ 223 00:11:01,120 --> 00:11:03,560 და კარგი დიზაინის გადაწყვეტილებები როდესაც წერა პროგრამებს. 224 00:11:03,560 --> 00:11:07,070 ასე რომ, მოდით ფოკუსირება თუმცა, თუ როგორ ჩვენ შეიძლება გამარტივდეს ეს შედეგი. 225 00:11:07,070 --> 00:11:11,780 >> ასე რომ, მე ხაზგასმით ყვითელი აქ შედეგი n კვადრატში გაყოფილი 2, 226 00:11:11,780 --> 00:11:14,330 ასე მილიონი კვადრატი გაყოფილი 2, და შემდეგ 227 00:11:14,330 --> 00:11:16,710 მე ხაზგასმით რა საბოლოო პასუხი იყო 228 00:11:16,710 --> 00:11:20,180 ერთხელ ჩვენ ჩამოჭრილია მთლიანი თანხიდან off n იყოფა 2. 229 00:11:20,180 --> 00:11:24,850 და აცხადებენ, მე ვაპირებ, რომ ახლა ის არის, რომელიც heck ზრუნავს თუ სხვაობა off 230 00:11:24,850 --> 00:11:30,060 ცოტა ძველი n მეტი 2, როდესაც პირველი ნაწილი ეს ფორმულა იმდენად დიდი? 231 00:11:30,060 --> 00:11:33,910 ის დომინირებს სხვა ტერმინი, n კვადრატში გაყოფილი 2 232 00:11:33,910 --> 00:11:37,510 უფრო მეტია, ნათლად, როგორც n იღებს დიდი მილიონი, 233 00:11:37,510 --> 00:11:41,450 რომ არის მართლაც დიდი სხვაობა დღის ბოლოს შორის 500 მილიარდი 234 00:11:41,450 --> 00:11:45,730 და 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 ნამდვილად არ. 236 00:11:46,349 --> 00:11:48,640 და მერე რა, ჩვენ ვაპირებთ გავაკეთოთ როგორც კომპიუტერი მეცნიერები არის 237 00:11:48,640 --> 00:11:53,270 იგნორირება, ქვედა წესრიგის თვალსაზრისით და მსგავსი რამ და რეალურად 238 00:11:53,270 --> 00:11:56,050 უბრალოდ გამარტივება მას ტერმინი, რომელიც აპირებს აქვს. 239 00:11:56,050 --> 00:12:00,315 მით უფრო დიდია იმის მონაცემები კომპლექტი, მით უფრო დიდია, ჩვენს ბაზაში, მით უფრო ვებ გვერდები 240 00:12:00,315 --> 00:12:02,690 ჩვენ უნდა ვეძებოთ, უფრო მეგობრები თქვენ გაქვთ Facebook. 241 00:12:02,690 --> 00:12:07,340 >> როგორც n იღებს უფრო დიდი, ჩვენ მართლაც აპირებს აინტერესებს უდიდესი 242 00:12:07,340 --> 00:12:11,560 ტერმინი ნებისმიერი ასეთი ანალიზი ჩვენი ალგორითმები შესრულება. 243 00:12:11,560 --> 00:12:16,230 და მე ვაპირებ ვთქვა, თქვენ იცით, რა, bubble sort არის ბრძანებით დიდი O, 244 00:12:16,230 --> 00:12:18,060 ბრძანებით n კვადრატში. 245 00:12:18,060 --> 00:12:20,090 ეს არ არის ზუსტად n კვადრატი, როგორც ჩვენ ვნახეთ, 246 00:12:20,090 --> 00:12:22,060 მაგრამ, ვინც ნამდვილად ზრუნავს დაახლოებით იმ მცირე ვადები, 247 00:12:22,060 --> 00:12:24,390 და გულწრფელად, რომელიც ნამდვილად ზრუნავს თუ გავყოფთ 2? 248 00:12:24,390 --> 00:12:25,870 ეს მხოლოდ მუდმივი ფაქტორი. 249 00:12:25,870 --> 00:12:29,480 და 500 მილიარდი წინააღმდეგ 250 მილიარდი მართლაც რომ დიდი გარიგება? 250 00:12:29,480 --> 00:12:32,190 მე ვერ უბრალოდ მოეცადა ერთი წელი, მიადევნე ჩემი ლეპტოპი ფაქტიურად 251 00:12:32,190 --> 00:12:34,810 ორჯერ სწრაფად ტექნიკა, და რომ ერთგვარი სხვაობა 252 00:12:34,810 --> 00:12:36,650 მხოლოდ მიდის ბუნებრივია, დროთა განმავლობაში. 253 00:12:36,650 --> 00:12:39,300 >> რაც ჩვენ აღელვებს არის გამოთქმა, ნაწილი 254 00:12:39,300 --> 00:12:42,489 გამოხატვის, რომ აპირებს განსხვავდება როგორც ჩვენი input იღებს უფრო დიდი და უფრო დიდი. 255 00:12:42,489 --> 00:12:45,280 და მართლაც, რეალურ სამყაროში, რომ ის, რაც ხდება უფრო 256 00:12:45,280 --> 00:12:48,330 არის პორტები ჩვენს პრობლემებს და ალგორითმები იღებენ დიდია. 257 00:12:48,330 --> 00:12:53,470 ასე რომ, დიდი O იქნება notation, asymptotic notation, რომ ჩვენ უბრალოდ 258 00:12:53,470 --> 00:12:57,160 გამოიყენოთ როგორც კომპიუტერის მეცნიერები აღწერს შესრულება, ქრონომეტრაჟი, 259 00:12:57,160 --> 00:12:58,130 ალგორითმი. 260 00:12:58,130 --> 00:13:00,800 ასე რომ, ჩვენ შეგვიძლია შევადაროთ ალგორითმები სხვადასხვა კომპიუტერი წერილობითი 261 00:13:00,800 --> 00:13:04,170 სხვადასხვა ხალხი, გამოყენებით ზოგიერთი პრინციპულად მსგავსი მეტრულ 262 00:13:04,170 --> 00:13:07,557 როგორც იმ შედარებები თქვენ მიღების, ან იქნებ ნომერი გაცვლებს 263 00:13:07,557 --> 00:13:08,140 თქვენ მიღების. 264 00:13:08,140 --> 00:13:11,910 >> ის, რაც ჩვენ არ ვაპირებთ ჯამში არის დროის 265 00:13:11,910 --> 00:13:13,981 რომ გადის საათი კედელზე, როგორც წესი. 266 00:13:13,981 --> 00:13:16,230 ის, რაც ჩვენ არ აპირებს აღელვებს იმის შესახებ, თუ რამდენი მეხსიერება 267 00:13:16,230 --> 00:13:17,820 თქვენ იყენებთ დღეს, მაინც, მიუხედავად იმისა, რომ 268 00:13:17,820 --> 00:13:19,370 კიდევ ერთი რესურსი, შეიძლება ღონისძიება. 269 00:13:19,370 --> 00:13:23,610 ჩვენ ვაპირებთ ცდილობენ ბაზის ჩვენი ანალიზი მხოლოდ ძირითადი ოპერაციების, ვინც, 270 00:13:23,610 --> 00:13:25,930 სიმართლე გითხრათ, რომ თქვენ ხედავთ, ყველაზე ვიზუალურად. 271 00:13:25,930 --> 00:13:30,700 ასე რომ რაღაც დიდი O of n კვადრატი, აცხადებენ, რომ O of n კვადრატში 272 00:13:30,700 --> 00:13:35,820 ზედა შეკრული on ე.წ. ქრონომეტრაჟი bubble sort. 273 00:13:35,820 --> 00:13:38,820 სხვა სიტყვებით, თუ სასურველი აცხადებენ, რომ იქ 274 00:13:38,820 --> 00:13:41,370 ეს ზედა ლიმიტი რამდენი ნაბიჯები ალგორითმი შესაძლოა, 275 00:13:41,370 --> 00:13:46,240 ეს იქნება დიდი O of n კვადრატი, ამ შემთხვევაში, ზედა ზღვარი. 276 00:13:46,240 --> 00:13:49,710 >> რა მოხდება, თუ ნაცვლად შეცვლა სტატია იმის შესახებ, bubble sort, 277 00:13:49,710 --> 00:13:50,910 მაგრამ ამ ზედა შეკრული. 278 00:13:50,910 --> 00:13:54,030 შეიძლება ფიქრობთ, რომ ალგორითმი რომ ჩვენ შევხედე უკვე 279 00:13:54,030 --> 00:13:59,530 რომლის ზედა ზღვარი, მაქსიმალური გავზომოთ დრო და ოპერაციები, 280 00:13:59,530 --> 00:14:04,300 რომ ითქვას, რომ ესაზღვრება by n, წრფივი ფუნქცია, 281 00:14:04,300 --> 00:14:07,260 არა კვადრატული ერთი, რომ curved? 282 00:14:07,260 --> 00:14:10,780 რა არის ალგორითმი, რომელიც ყოველთვის იღებს აღარ 283 00:14:10,780 --> 00:14:12,860 ვიდრე მოსწონს n ნაბიჯები, ან 2n ნაბიჯები, ან 3N ნაბიჯები? 284 00:14:12,860 --> 00:14:13,360 ჰო? 285 00:14:13,360 --> 00:14:15,030 >> აუდიტორია: დამდგენი დიდი რაოდენობის სიაში? 286 00:14:15,030 --> 00:14:16,930 >> დინამიკები: Perfect, მოძიებაში ყველაზე დიდი რაოდენობის სია. 287 00:14:16,930 --> 00:14:18,940 თუ მე მოცემულია სია ადამიანი, მაგალითად, 288 00:14:18,940 --> 00:14:21,440 თითოეული რომელიც მართავს ნომერი, რა არის მაქსიმალური რაოდენობის 289 00:14:21,440 --> 00:14:23,770 ნაბიჯები უნდა მიიღოს me, გონივრულად მოაზროვნე ადამიანს, 290 00:14:23,770 --> 00:14:27,530 რათა იპოვოს უმსხვილესი პირი, ამ სიაში? 291 00:14:27,530 --> 00:14:28,100 n, არა? 292 00:14:28,100 --> 00:14:31,320 რადგან უარეს შემთხვევაში, შესაძლოა, ყველაზე დიდი ღირებულება იქნება? 293 00:14:31,320 --> 00:14:32,700 მარჯვენა, ყველა გზა ბოლომდე. 294 00:14:32,700 --> 00:14:34,575 ასე რომ, უარეს შემთხვევაში ზედა ზღვარი, მე შეიძლება 295 00:14:34,575 --> 00:14:36,450 უნდა წავიდეთ ყველა გზა აქ და იყოს, 296 00:14:36,450 --> 00:14:39,170 OH, აქ რვა, ან რასაც არც. 297 00:14:39,170 --> 00:14:41,330 ახლა ეს მხოლოდ სულელი თუ გავაგრძელე, არა? 298 00:14:41,330 --> 00:14:43,840 ეძებთ უფრო და უფრო მეტი ელემენტები თუ ბოლო ერთი მათგანი არ არის იქ? 299 00:14:43,840 --> 00:14:45,340 ასე რომ, რა თქმა უნდა, n ზედა შეკრული. 300 00:14:45,340 --> 00:14:47,420 მე არ უნდა მიიღოს ნაბიჯები, ვიდრე. 301 00:14:47,420 --> 00:14:51,580 >> მერე რა, რომ ნაცვლად მე შევთავაზე, რომ არსებობს ალგორითმები ამ სამყაროში, 302 00:14:51,580 --> 00:14:57,750 აქვს გაშვებული დრო, რომ ის, ესაზღვრება დიდი O შესვლა N, შეხვიდეთ n? 303 00:14:57,750 --> 00:15:00,390 სადაც არ ჩვენ ვხედავთ ამ ადრე? 304 00:15:00,390 --> 00:15:00,890 ჰო? 305 00:15:00,890 --> 00:15:03,309 >> აუდიტორია: სატელეფონო წიგნი პრობლემა? 306 00:15:03,309 --> 00:15:04,850 დინამიკები Like სატელეფონო წიგნი პრობლემა. 307 00:15:04,850 --> 00:15:07,754 რა იყო ღონისძიება, თუ როგორ ბევრი დრო და რამდენი ცრემლი ის 308 00:15:07,754 --> 00:15:10,170 წამიყვანეს ურთიერთობა, როგორიც არის მაიკ სმიტი სატელეფონო წიგნი? 309 00:15:10,170 --> 00:15:13,212 ჩვენ განაცხადა, რომ ეს ჟურნალი n და მაშინაც კი, თუ იციან, ან ეს ის 310 00:15:13,212 --> 00:15:15,170 ცოტა ბუნდოვანი რა logarithm ან მაჩვენებლებით იყო, 311 00:15:15,170 --> 00:15:17,650 უბრალოდ გვახსოვდეს, რომ log n ზოგადად ეხება პროცესი, 312 00:15:17,650 --> 00:15:20,790 ამ შემთხვევაში, გამყოფი რაღაც ნახევარი ისევ და ისევ, 313 00:15:20,790 --> 00:15:25,790 და ისევ და ისევ, ისეთი, რომ ეს იღებს უფრო და უფრო პატარა, როგორც თქვენ, რომ. 314 00:15:25,790 --> 00:15:28,470 >> ასე რომ შედით ო ეხება, რა თქმა უნდა, რათა სატელეფონო წიგნი მაგალითად, 315 00:15:28,470 --> 00:15:32,662 ორობითი ძებნა თეორიულად, როდესაც ჩვენ ჰქონდა ვირტუალური კარი ფორუმში, 316 00:15:32,662 --> 00:15:34,370 ან როცა შონ ეძებს რაღაც. 317 00:15:34,370 --> 00:15:37,374 თუ მან გამოიყენა ორობითი ძებნა, შესვლა n იქნება ზედა ზღვარი, თუ რამდენად 318 00:15:37,374 --> 00:15:38,040 დრო, რომელიც სჭირდება. 319 00:15:38,040 --> 00:15:44,027 მაგრამ იმ ალგორითმები რომ გაიქცა შესვლა N აიღო, რა ძირითადი დეტალი? 320 00:15:44,027 --> 00:15:45,360 რომ სია დახარისხებული, არა? 321 00:15:45,360 --> 00:15:47,789 თქვენი ალგორითმი ცუდი, თქვენი შეყვანის არის დახარისხებული, 322 00:15:47,789 --> 00:15:49,830 და ჯერ თქვენ გამოყენებით რაღაც ორობითი ძებნა 323 00:15:49,830 --> 00:15:51,704 რადგან თქვენ შეიძლება გადასვლა უფლება მეტი ელემენტი 324 00:15:51,704 --> 00:15:53,600 გარეშე ხვდებიან მას მართლაც არსებობს. 325 00:15:53,600 --> 00:15:55,600 >> ახლა რა შეიძლება იყოს ეს ნიშნავს, დიდი O ერთი? 326 00:15:55,600 --> 00:15:59,117 ეს არ ნიშნავს, რომ თქვენი ალგორითმი იღებს ერთი და მხოლოდ ერთი ნაბიჯია, 327 00:15:59,117 --> 00:16:01,200 ეს მხოლოდ იმას ნიშნავს, რომ იგი იღებს მუდმივი ნაბიჯი. 328 00:16:01,200 --> 00:16:04,060 იქნებ ეს 1, შესაძლოა ეს 10, იქნებ ეს 1000 329 00:16:04,060 --> 00:16:07,750 მაგრამ დამოუკიდებელი ზომის პრობლემა. 330 00:16:07,750 --> 00:16:10,850 არ აქვს მნიშვნელობა, თუ რამდენად დიდი n არის, მუდმივი დროის ალგორითმი 331 00:16:10,850 --> 00:16:12,747 ყოველთვის იღებს იმავე რაოდენობის ნაბიჯები. 332 00:16:12,747 --> 00:16:15,080 ისე რა შეიძლება იყოს ალგორითმი ჩვენ ვისაუბრეთ, ან უბრალოდ 333 00:16:15,080 --> 00:16:20,418 ინტუიციურად, რომ საქმე, რომ ყოველთვის გადის ე.წ. მუდმივი დროს? 334 00:16:20,418 --> 00:16:20,918 ჰო? 335 00:16:20,918 --> 00:16:22,001 >> აუდიტორია: სანიშნეს ორი ნომერი. 336 00:16:22,001 --> 00:16:25,320 დინამიკები სანიშნეს ორი ნომერი, 2 plus 2 შეადგენს 4 გაკეთდეს. 337 00:16:25,320 --> 00:16:27,227 ასე რომ, შესაძლოა, მუშაობა, რა? 338 00:16:27,227 --> 00:16:28,560 როგორ შესახებ უფრო რეალურ ცხოვრებაში, არა? 339 00:16:28,560 --> 00:16:30,686 >> აუდიტორია: დამდგენი პირველი, რაც სიაში. 340 00:16:30,686 --> 00:16:32,810 დინამიკები მოძიება პირველი ელემენტს სიაში, დარწმუნებული ვარ. 341 00:16:32,810 --> 00:16:34,540 ჩვენ რეალურად ვსაუბრობთ შესახებ კოლექტორები უკვე, 342 00:16:34,540 --> 00:16:36,540 როგორ იღებთ ზე პირველი ელემენტია მასივი, 343 00:16:36,540 --> 00:16:40,465 არ აქვს მნიშვნელობა, რამდენ ხანს array არის C კოდი? 344 00:16:40,465 --> 00:16:43,090 თქვენ უბრალოდ გამოყენება, როგორიცაა bracket ნულოვანი notation, bam, თქვენ იქ. 345 00:16:43,090 --> 00:16:46,120 და მართლაც მასივები, როგორც განზე, მხარდაჭერა რაღაც საყოველთაოდ ცნობილია 346 00:16:46,120 --> 00:16:49,240 როგორც შემთხვევითი წვდომის წვდომის მეხსიერება, რადგან თქვენ შეგიძლიათ სიტყვასიტყვით 347 00:16:49,240 --> 00:16:50,284 გადასვლა რომელიმე ადგილი. 348 00:16:50,284 --> 00:16:52,700 ჩვენ შეგვიძლია ამის გაკეთება კიდევ უფრო უბრალოდ ჩვენ შეგვიძლია გადახვევა კვირაში ნულოვანი 349 00:16:52,700 --> 00:16:53,900 როდესაც ჩვენ გავაკეთეთ Scratch. 350 00:16:53,900 --> 00:16:59,707 რამდენი დრო დასჭირდა, რომ ამბობენ ბლოკი Scratch შეასრულოს? 351 00:16:59,707 --> 00:17:00,790 მხოლოდ მუდმივი დროს, არა? 352 00:17:00,790 --> 00:17:03,960 ამბობენ, რომ რაღაც, ვთქვათ, რაღაც, არა აქვს მნიშვნელობა 353 00:17:03,960 --> 00:17:07,359 რამდენად დიდი ნაკაწრები მსოფლიოში, ის ყოველთვის აპირებს იმავე დროის 354 00:17:07,359 --> 00:17:08,490 უბრალოდ ვთქვა რაღაც. 355 00:17:08,490 --> 00:17:11,089 >> ასე რომ, მუდმივი დროს, მაგრამ რა flip მხარეს? 356 00:17:11,089 --> 00:17:13,030 თუ იყო, რომ ზემო ფარგლებში, თუ ჩვენ გვინდა, 357 00:17:13,030 --> 00:17:17,089 აღწერს ქვედა საზღვრები ჩვენი ალგორითმები გაშვებული დრო? 358 00:17:17,089 --> 00:17:19,852 თითქმის საუკეთესო შემთხვევაში პოტენციურად, თუ გნებავთ, 359 00:17:19,852 --> 00:17:23,060 თუმცა, ამ თვალსაზრისით შეიძლება მიმართოს საუკეთესო შემთხვევაში, უარეს შემთხვევაში, საშუალო შემთხვევაში უფრო 360 00:17:23,060 --> 00:17:26,359 ზოგადად, მაგრამ მოდით უბრალოდ ფოკუსირება ქვედა საზღვრები უფრო ზოგადად. 361 00:17:26,359 --> 00:17:31,920 რა არის ალგორითმი, რომელიც აქვს ქვედა ბლოკნოტის N ნაბიჯები, 362 00:17:31,920 --> 00:17:33,350 ან 2n ნაბიჯები, ან 3N ნაბიჯები? 363 00:17:33,350 --> 00:17:36,241 ზოგიერთი ფაქტორი N ნაბიჯები, რომ არის მისი ქვედა შეკრული. 364 00:17:36,241 --> 00:17:36,740 ჰო? 365 00:17:36,740 --> 00:17:37,910 >> აუდიტორია: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> დინამიკები: Bubble დალაგების იღებს თქვენ მინიმალურად N ნაბიჯები, რატომ? 367 00:17:41,610 --> 00:17:42,279 რატომ არის, რომ? 368 00:17:42,279 --> 00:17:45,320 რატომ უნდა დაწყება მოვედი თქვენთან ინტუიციურად, მაშინაც კი, თუ ეს არ არის მხოლოდ 369 00:17:45,320 --> 00:17:46,530 ჯერ არ გაქვთ? 370 00:17:46,530 --> 00:17:47,030 ჰო? 371 00:17:47,030 --> 00:17:47,990 >> აუდიტორია: [INAUDIBLE]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 დინამიკები: ზუსტად. 374 00:17:52,360 --> 00:17:55,810 საუკეთესო შესაძლო სცენარი bubble sort, და ბევრი ალგორითმები, 375 00:17:55,810 --> 00:17:58,769 თუ მე მხრივ, რვა ადამიანი რომლებიც უკვე დახარისხებული, 376 00:17:58,769 --> 00:18:00,560 ეს იქნებოდა უგუნური თქვენ, ალგორითმი, 377 00:18:00,560 --> 00:18:02,202 წავიდეთ უკან და მეოთხე კიდევ ერთხელ, არა? 378 00:18:02,202 --> 00:18:04,285 იმის გამო, რომ, როგორც კი თქვენ გავლა სია ერთხელ, 379 00:18:04,285 --> 00:18:08,090 თქვენ უნდა გაიგოთ, რა, მე არ სვოპები, ამ სიაში დალაგებულია, გასასვლელი. 380 00:18:08,090 --> 00:18:09,700 მაგრამ, რომ აპირებს თქვენ N ნაბიჯები. 381 00:18:09,700 --> 00:18:12,033 >> და პირიქით, თუ რა არის სხვა აზროვნების შესახებ? 382 00:18:12,033 --> 00:18:15,240 Bubble დალაგების არის ომეგა, ასე ვთქვათ, n, 383 00:18:15,240 --> 00:18:19,050 რადგან თუ გადავხედავთ ნაკლები n ელემენტებს, რა 384 00:18:19,050 --> 00:18:23,009 არის ფუნდამენტური საკითხი, არსებობს? 385 00:18:23,009 --> 00:18:24,550 თქვენ არ იცით, თუ ეს დახარისხებული, მარჯვნივ. 386 00:18:24,550 --> 00:18:26,800 ჩვენ ადამიანებს ერთი შეხედვით რვა ადამიანი და იყოს, oh, ეს დახარისხებული, 387 00:18:26,800 --> 00:18:28,430 რომ არ ჰქონია ჩემთვის n ნაბიჯები, მაგრამ ეს მოხდა. 388 00:18:28,430 --> 00:18:30,810 შენი თვალები, მიუხედავად იმისა, რომ ასეთი აქვს დიდი თვალსაწიერი, 389 00:18:30,810 --> 00:18:33,184 შევხედე რვა ელემენტები, შევხედე რვა ადამიანი, 390 00:18:33,184 --> 00:18:34,610 რომ რვა ნაბიჯები ეფექტური. 391 00:18:34,610 --> 00:18:38,612 და მხოლოდ მაშინ, მე გავლა მთელი სიაში მე გააცნობიეროს, დიახ, დახარისხებული. 392 00:18:38,612 --> 00:18:41,320 თუ მე შეჩერება შუა ნაწილამდე იყვნენ ფიქრობდა, ყველა უფლება, ის საკმაოდ დალაგებულია ჯერჯერობით, 393 00:18:41,320 --> 00:18:42,520 რა შანსები, რომ ეს არ დახარისხებული? 394 00:18:42,520 --> 00:18:44,186 რომ ალგორითმები არ იქნება სწორი. 395 00:18:44,186 --> 00:18:46,250 შეიძლება იყოს უფრო სწრაფად, მაგრამ არასწორია. 396 00:18:46,250 --> 00:18:48,500 >> ახლა ჩვენ გვაქვს გზა აღწერს ქვედა საზღვრები, 397 00:18:48,500 --> 00:18:49,710 რაც შეეხება მუდმივ დრო? 398 00:18:49,710 --> 00:18:54,565 რა არის ალგორითმი, რომელიც აქვს ქვედა შეკრული მისი ქრონომეტრაჟი ერთი? 399 00:18:54,565 --> 00:18:58,350 1 ნაბიჯი 2 ნაბიჯი, 10 ნაბიჯები, მაგრამ მუდმივი, დამოუკიდებელი n, 400 00:18:58,350 --> 00:18:59,310 ზომა შეყვანის? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 ჰო, წელს უკან. 403 00:19:04,600 --> 00:19:05,309 >> აუდიტორია: Printf? 404 00:19:05,309 --> 00:19:06,183 დინამიკები: რა არის ეს? 405 00:19:06,183 --> 00:19:07,184 აუდიტორია: Printf? 406 00:19:07,184 --> 00:19:07,850 დინამიკები printf. 407 00:19:07,850 --> 00:19:08,400 OK, დარწმუნებული ვარ. 408 00:19:08,400 --> 00:19:10,720 ასე რომ იღებს ფიქსირებული რაოდენობის ნაბიჯები. 409 00:19:10,720 --> 00:19:13,170 და მე უნდა ახლა არის, რომ ჩვენ ვსაუბრობთ C კოდი 410 00:19:13,170 --> 00:19:16,040 და არა ნულიდან, რაღაც როგორიცაა მაგალითად, printf, 411 00:19:16,040 --> 00:19:17,710 ჩვენ უნდა დაიწყოს, ფრთხილად. 412 00:19:17,710 --> 00:19:21,090 იმის გამო, რომ printf არ მიიღოს შეყვანა, სიმებიანი, 413 00:19:21,090 --> 00:19:23,220 და ვიდრე არ ტექნიკურად აქვს სიგრძეზე. 414 00:19:23,220 --> 00:19:25,530 ასე რომ, თუ ჩვენ ახლა უნდა აირჩიოთ თქვენ, თუ არ იბადება, 415 00:19:25,530 --> 00:19:29,430 ტექნიკურად ჩვენ ვერ ამტკიცებენ, რომ printf არ მიიღოს ცვლადი სიგრძის input, 416 00:19:29,430 --> 00:19:32,270 და რა თქმა უნდა ის შესაძლოა უფრო დრო ბეჭდვა სიმებიანი ეს ხანგრძლივი, 417 00:19:32,270 --> 00:19:33,560 ვიდრე ამ ხნის მანძილზე. 418 00:19:33,560 --> 00:19:36,570 >> მერე რა, თუ გავითვალისწინებთ, მხოლოდ დახარისხება და ძიების მაგალითები? 419 00:19:36,570 --> 00:19:40,450 რაც შეეხება მაიკ სმიტი ტელეფონი წიგნი, ან ორობითი ძებნა, უფრო მეტი? 420 00:19:40,450 --> 00:19:42,220 საუკეთესო შემთხვევაში, რა შეიძლება მოხდეს? 421 00:19:42,220 --> 00:19:45,577 მე გახსნა სატელეფონო წიგნი და bam, არსებობს მაიკ სმიტი ნომერი. 422 00:19:45,577 --> 00:19:46,660 მე მოვუწოდებ მას დაუყოვნებლივ. 423 00:19:46,660 --> 00:19:49,390 >> აიღო ერთი ნაბიჯი, შესაძლოა, ორი ნაბიჯი, მაგრამ მუდმივი რიგი ნაბიჯები 424 00:19:49,390 --> 00:19:50,230 თუ მე მივიღე გაუმართლა. 425 00:19:50,230 --> 00:19:52,570 და გულწრფელად, ვნახეთ ორშაბათი თქვენი თანაკლასელი 426 00:19:52,570 --> 00:19:54,710 საკმაოდ გაუმართლა ორჯერ ზედიზედ. 427 00:19:54,710 --> 00:19:57,050 და რომ მართლაც მუდმივი დროს ქვედა საზღვრები 428 00:19:57,050 --> 00:20:01,280 ალგორითმი კითხვა მოძიების ნომერი 50 უკან იმ დახურულ 429 00:20:01,280 --> 00:20:01,830 კარები. 430 00:20:01,830 --> 00:20:06,400 >> ახლა, როგორც განზე, თუ თქვენ აღმოაჩინეთ, რომ როგორც დიდი O, ზედა შეკრული, 431 00:20:06,400 --> 00:20:09,310 და ომეგა, ქვედა შეკრული, არის ერთი და იგივე, რომ 432 00:20:09,310 --> 00:20:11,830 არის იგივე ფორმულა ფრჩხილებში, ასევე შეგიძლიათ 433 00:20:11,830 --> 00:20:15,170 ვთქვათ, მხოლოდ უნდა იყოს ლამაზი, რომ რაღაც არის თეტა 434 00:20:15,170 --> 00:20:18,270 ო ან თეტა რაიმე სხვა ღირებულება. 435 00:20:18,270 --> 00:20:20,661 ეს უბრალოდ ნიშნავს, როდესაც დიდი O და ომეგა იგივეა. 436 00:20:20,661 --> 00:20:21,910 ახლა რაც შეეხება შერჩევის დალაგება? 437 00:20:21,910 --> 00:20:23,400 მოდით გამოვიყენოთ ეს ახალი ლექსიკა. 438 00:20:23,400 --> 00:20:27,407 შერჩევის დალაგების, რა იყო ჩვენ ამით ისევ და ისევ და ისევ? 439 00:20:27,407 --> 00:20:29,990 მივდიოდი და მეოთხე მეშვეობით სია, ეძებს ვის? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 ყველაზე პატარა ნომერი. 442 00:20:34,730 --> 00:20:37,560 >> ისე რამდენი ნაბიჯები, თუ როგორ ბევრი შედარებები არ მინდა 443 00:20:37,560 --> 00:20:43,250 უნდა მიიღოს, რათა გაერკვნენ, რომელიც პატარა ელემენტს სიაში? 444 00:20:43,250 --> 00:20:44,437 N მინუს 1, არა? 445 00:20:44,437 --> 00:20:47,770 რადგან თუ მე დავიწყო ერთი მე ვარ მოცემული და დავიწყებ შედარებით მას, 446 00:20:47,770 --> 00:20:49,519 მაშინ მას, მას ან მისი, მას, მე 447 00:20:49,519 --> 00:20:52,010 შეიძლება მხოლოდ წყვილი ელემენტები ერთად N მინუს 1 ჯერ. 448 00:20:52,010 --> 00:20:55,630 ამიტომ შერჩევას დალაგების ერთნაირად იღებს N მინუს 1 ნაბიჯებს პირველად. 449 00:20:55,630 --> 00:20:59,540 >> რამდენი ნაბიჯები სჭირდება ჩემთვის იპოვოს მეორე ყველაზე პატარა ელემენტი? 450 00:20:59,540 --> 00:21:02,920 n-2, რადგან მე ვარ, რომ მუნჯები თუ მე შენარჩუნება ეძებს იგივე ადამიანი 451 00:21:02,920 --> 00:21:06,280 კიდევ ერთხელ, თუ მე უკვე აარჩია ან მისი და ამით მათ ადგილას. 452 00:21:06,280 --> 00:21:09,270 და მესამე ნაბიჯი, n მინუს 3, მაშინ n მინუს 4. 453 00:21:09,270 --> 00:21:11,020 ჩვენ ვნახეთ, რომ ეს ნიმუში ადრე, და მართლაც 454 00:21:11,020 --> 00:21:13,460 შერჩევის დალაგების ასეთივე აქვს ზედა ზღვარი 455 00:21:13,460 --> 00:21:16,210 n კვადრატში, თუ ჩვენ გავაკეთებთ, რომ summation. 456 00:21:16,210 --> 00:21:19,790 რა არის მისი ქვედა შეკრული, შერჩევის დალაგება? 457 00:21:19,790 --> 00:21:25,350 მინიმალურად, რამდენი დრო უნდა შერჩევა სახის მიიღოს, რადგან ჩვენ განვსაზღვრეთ ეს ორშაბათს? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 შესთავაზოს ორი ვარიანტი. 460 00:21:30,490 --> 00:21:32,360 იქნებ ეს n, როგორც ადრე. 461 00:21:32,360 --> 00:21:35,040 იქნებ ეს n კვადრატში, რადგან ის ახლა, როგორც ზედა შეკრული. 462 00:21:35,040 --> 00:21:35,874 >> აუდიტორია: N კვადრატში. 463 00:21:35,874 --> 00:21:36,664 დინამიკები: N კვადრატში. 464 00:21:36,664 --> 00:21:37,368 რატომ? 465 00:21:37,368 --> 00:21:40,060 >> აუდიტორია: იმიტომ, რომ თქვენ რათა განისაზღვროს [INAUDIBLE]. 466 00:21:40,060 --> 00:21:41,510 >> დინამიკები: ზუსტად. 467 00:21:41,510 --> 00:21:45,077 როგორც მინიმუმ, როგორც მე განვმარტე შერჩევის დალაგების ეს იყო საკმაოდ გულუბრყვილო, შენარჩუნებას აპირებს, 468 00:21:45,077 --> 00:21:46,160 მოვძებნოთ პატარა ელემენტს. 469 00:21:46,160 --> 00:21:47,770 წავიდეთ კიდევ ერთხელ, იპოვოს პატარა ელემენტს. 470 00:21:47,770 --> 00:21:49,490 წავიდეთ კიდევ ერთხელ, იპოვოს პატარა ელემენტს. 471 00:21:49,490 --> 00:21:51,700 არ არსებობს ერთგვარი ოპტიმიზაცია არსებობს, რომ 472 00:21:51,700 --> 00:21:54,350 შეიძლება მიადევნე თვალი შეწყვეტა მას შემდეგ, რაც უბრალოდ n ან იმდენად ნაბიჯები. 473 00:21:54,350 --> 00:21:57,080 ასე რომ, რა თქმა უნდა, შერჩევა სახის, omega n კვადრატში. 474 00:21:57,080 --> 00:22:00,667 >> რაც შეეხება Insertion დალაგების, სადაც მე ვინც მე გადაეცა, ხოლო შემდეგ მე plopped მას 475 00:22:00,667 --> 00:22:01,750 ან მისი სწორი ადგილი? 476 00:22:01,750 --> 00:22:04,958 მერე, მეორე პირი, plopped მისთვის საჭირო ადგილას. 477 00:22:04,958 --> 00:22:07,910 მაშინ შემდეგი პირი, plopped მისთვის საჭირო ადგილას. 478 00:22:07,910 --> 00:22:10,537 გაითვალისწინეთ, რომ ეს არის ძალიან წრფივი, ასე ვთქვათ. 479 00:22:10,537 --> 00:22:12,620 მე სწორი ხაზი, მე არ აპირებს უკან და მეოთხე, 480 00:22:12,620 --> 00:22:16,080 მე არასდროს არ ეძებს უკან ნამდვილად, მაგრამ რა ხდება, როდესაც მე ჩადეთ მას 481 00:22:16,080 --> 00:22:20,302 ან მისი შევიდა დასაწყისში სიაში, როგორც ჩვენ ორშაბათს? 482 00:22:20,302 --> 00:22:21,010 რა ხდება? 483 00:22:21,010 --> 00:22:21,510 ჰო? 484 00:22:21,510 --> 00:22:23,122 აუდიტორია: [INAUDIBLE]. 485 00:22:23,122 --> 00:22:24,830 დინამიკები: ჰო, იყო დაჭერა, არა? 486 00:22:24,830 --> 00:22:26,746 თქვენ შეიძლება გავიხსენოთ თქვენი თანაკლასელები, თუ ისინი 487 00:22:26,746 --> 00:22:29,670 იყო, რომ ნებისმიერი მოძრაობა მათი ფეხები, რომ იყო ოპერაცია. 488 00:22:29,670 --> 00:22:33,610 ასე რომ, თუ სამი ადამიანი აქ და ახალ ადამიანს ეკუთვნოდა გზა იქ, 489 00:22:33,610 --> 00:22:37,360 ხანგრძლივი ეტაპი, როგორც ეს, რა თქმა უნდა, ის ან შეეძლო უბრალოდ ბოლომდე. 490 00:22:37,360 --> 00:22:40,074 მაგრამ თუ ჩვენ ფიქრი კომპიუტერი და მასივი მეხსიერება, 491 00:22:40,074 --> 00:22:41,990 ეს ხალხი აპირებს უნდა shuffle მეტი 492 00:22:41,990 --> 00:22:43,260 ოთახში, რომ პირი. 493 00:22:43,260 --> 00:22:46,930 და ისე, რომ n -1 shufflings, n-2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 მინუს 3 shufflings მხოლოდ სახის ხდება ჩემს უკან, არ ჩემ თვალწინ 495 00:22:50,660 --> 00:22:52,710 როგორც ადრე, გარკვეული თვალსაზრისით. 499 00:22:52,557 --> 00:22:54,640 ახლა, როგორც განზე, და როგორც თქვენ შეიძლება არ მინახავს შემოსული 500 00:22:54,640 --> 00:22:57,699 თუ თქვენ დაიწყოს გააღიზიანოს გარშემო სახის, არსებობს ამდენი სხვადასხვა პირობა 501 00:22:57,699 --> 00:22:59,490 არსებობს, ზოგიერთი მათგანი უკეთესი, ვიდრე სხვები. 502 00:22:59,490 --> 00:23:02,200 მართლაც, bogosort არის ერთ ერთი რომ სახის fun ეძებოთ. 503 00:23:02,200 --> 00:23:06,650 Bogosort იღებს კომპლექტი ციფრები ამბობენ ან deck ბარათების, 504 00:23:06,650 --> 00:23:09,870 შემთხვევით shuffles მათ, და ამოწმებს, თუ ისინი დახარისხებული. 505 00:23:09,870 --> 00:23:12,130 და თუ არა, იმას კიდევ ერთხელ აკეთებს. 506 00:23:12,130 --> 00:23:14,140 და თუ არა, იმას კიდევ ერთხელ აკეთებს. 507 00:23:14,140 --> 00:23:15,440 თუ არა, იმას კიდევ ერთხელ აკეთებს. 508 00:23:15,440 --> 00:23:17,060 წარმოუდგენლად სულელური. 509 00:23:17,060 --> 00:23:19,520 >> და მართლაც, თუ წაიკითხავთ როგორიცაა Wikipedia article, 510 00:23:19,520 --> 00:23:21,200 მისი მეტსახელი არის სულელური სახის. 511 00:23:21,200 --> 00:23:25,180 იგი საბოლოოდ მუშაობა, იმედია, საკმარისი დრო, 512 00:23:25,180 --> 00:23:28,240 მაგრამ იმ დროის შეიძლება საკმაოდ გარკვეული დრო. 513 00:23:28,240 --> 00:23:31,650 ასე რომ, თუ შეიძლება, მოდით სიჩქარე რამ მდე Mary Beth მაგალითს ადრე, 514 00:23:31,650 --> 00:23:35,150 მიერ, რომელსაც რამდენიმე ელემენტები, მაგრამ კიდევ ორი ​​პროცესორი. 515 00:23:35,150 --> 00:23:37,100 ორი ადამიანი, თუ არ იბადება შეუერთდება ჩემთვის. 516 00:23:37,100 --> 00:23:40,972 როგორ შესახებ 1 აქ და მოდით წასვლა არავის იქ? 517 00:23:40,972 --> 00:23:41,722 არავინ იქ? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 თქვენ black პერანგი, დიახ, მოდის ქვემოთ. 520 00:23:44,190 --> 00:23:45,000 ყველა უფლება, რა გქვია? 521 00:23:45,000 --> 00:23:45,720 >> აუდიტორია: პეტრე. 522 00:23:45,720 --> 00:23:46,100 >> დინამიკები: რა არის ეს? 523 00:23:46,100 --> 00:23:46,766 >> აუდიტორია: პეტრე. 524 00:23:46,766 --> 00:23:49,450 დინამიკები: პეტრე, დავითი, კარგია თქვენთან შეხვედრა. 525 00:23:49,450 --> 00:23:53,670 ყველა უფლება, ჩვენ გვაქვს პეტრე, თუ მინდა, რომ მოვიდეს გადატანა მაგიდასთან მეტი აქ. 526 00:23:53,670 --> 00:23:54,550 და რა გქვია? 527 00:23:54,550 --> 00:23:55,216 >> აუდიტორია: ელენა. 528 00:23:55,216 --> 00:23:55,970 დინამიკები: ელენა. 529 00:23:55,970 --> 00:23:57,030 OK, კარგია თქვენთან შეხვედრა. 530 00:23:57,030 --> 00:23:58,060 Elena შეხვდება პეტრე. 531 00:23:58,060 --> 00:23:59,170 პეტრე, ელენა. 532 00:23:59,170 --> 00:24:02,290 და ჩვენ უნდა Andrew აქ, ასევე, გთხოვთ. 533 00:24:02,290 --> 00:24:06,107 და თქვენი გამოწვევა აპირებს უნდა იყოს დასალაგებლად deck ბარათების. 534 00:24:06,107 --> 00:24:08,190 და თუ უცნობ, deck ბარათები უნდა, საბოლოო ჯამში, 535 00:24:08,190 --> 00:24:11,064 იყოს დახარისხებული პატარა რაღაც ეს სადაც ჩვენ ყველაფერს გავაკეთებთ, კლუბები, მაშინ 536 00:24:11,064 --> 00:24:13,660 ყვავი, მაშინ გული და ბრილიანტები, საწყისი ace როგორც ერთი, 537 00:24:13,660 --> 00:24:15,570 ყველა გზა მდე მეფე. 538 00:24:15,570 --> 00:24:20,890 >> ბარათები მე ვაპირებ მოგცემთ ვაპირებთ, რომ იყოს 52 რაოდენობა. 539 00:24:20,890 --> 00:24:23,160 ჩვენ ვაპირებთ ასეთივე დროს, რაღაც მომენტში. 540 00:24:23,160 --> 00:24:26,410 ჩვენ ვაპირებთ, რომ იმისათვის, Andrew up ეკრანზე აქ, 541 00:24:26,410 --> 00:24:28,170 ისე უყურებს, როგორც თქვენ ამის გაკეთება. 542 00:24:28,170 --> 00:24:31,070 და ისე, რომ ყველა ამ მით უფრო, ჩანს, 543 00:24:31,070 --> 00:24:33,490 ეს არის გაცნობები მე მივიღე Amazon. 544 00:24:33,490 --> 00:24:42,861 ასე რომ, ისინი უკვე შემთხვევით დახარისხებული და ჩვენ ვაპირებთ, რომ ახლა თქვენ. 545 00:24:42,861 --> 00:24:44,610 და ჩვენ ვაპირებთ შევინარჩუნოთ ის რეალური ამ დროს, 546 00:24:44,610 --> 00:24:47,820 ასე რომ, ჩვენ ვაპირებთ ცდილობენ ზეწოლის თქვენ რადგან, წინააღმდეგ შემთხვევაში, ეს მიიღებს tedious 547 00:24:47,820 --> 00:24:48,460 სწრაფად. 548 00:24:48,460 --> 00:24:53,860 თუ შეიძლება გააგრძელოს დასალაგებლად 52 ელემენტები ერთად მეშვეობით ზოგიერთი საშუალება, ახლა. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> და ისევ, როგორც ჩვენ ვუყურებთ ამ ბიჭები რა, საბოლოო ჯამში, 551 00:25:07,180 --> 00:25:10,200 აპირებს აწარმოოს აშკარა შედეგი, ვფიქრობ იმაზე, მართლა 552 00:25:10,200 --> 00:25:12,962 როგორ ისინი თითოეულ აკეთებს, როგორ შეიძლება აღწერს მას. 553 00:25:12,962 --> 00:25:15,045 იმის გამო, რომ ერთხელ, ეს არის ყველა პროცესების, ალგორითმები 554 00:25:15,045 --> 00:25:17,090 რომ ჩვენ, თავისთავად, როგორც ადამიანის. 555 00:25:17,090 --> 00:25:22,349 მაგრამ თქვენ ალბათ დიდი ხანია ინტუიცია, ხნით ადრე თქვენ კი 556 00:25:22,349 --> 00:25:24,390 ეგონა აღების კომპიუტერულ მეცნიერებათა კლასი 557 00:25:24,390 --> 00:25:27,223 ალბათ ჰქონდა ინტუიცია ერთად რომელიც უნდა გადაწყვიტოს პრობლემა მოსწონს ეს. 558 00:25:27,223 --> 00:25:29,560 მაგრამ ერთხელ თქვენ აღიარებს მოდელი და დაიწყოს 559 00:25:29,560 --> 00:25:32,407 ფორმალური ნაბიჯები, რომელიც თქვენ გადაჭრის ამ პრობლემებს, 560 00:25:32,407 --> 00:25:35,490 თქვენ ნახავთ, რომ თქვენ შეგიძლიათ მოგვარება ბევრად უფრო საინტერესო და ბევრად უფრო რთული 561 00:25:35,490 --> 00:25:39,190 პრობლემების სწრაფად. 562 00:25:39,190 --> 00:25:42,351 ასე რომ ვინმეს აუდიტორიას, რა არის ერთი ელემენტი ალგორითმი 563 00:25:42,351 --> 00:25:43,350 რომ ისინი აქ გამოყენებით? 564 00:25:43,350 --> 00:25:44,275 >> აუდიტორია: [INAUDIBLE] 565 00:25:44,275 --> 00:25:45,150 დინამიკები: რა არის ეს? 566 00:25:45,150 --> 00:25:47,062 აუდიტორია: სარჩელი. 567 00:25:47,062 --> 00:25:47,770 დინამიკები სარჩელი. 568 00:25:47,770 --> 00:25:50,630 ასე რომ, ისინი თავდაპირველად კლასტერიზაციის ყველა ბრილიანტები ერთად 569 00:25:50,630 --> 00:25:52,560 როგორც ჩანს, ყველა გული ერთად, როგორც ჩანს, 570 00:25:52,560 --> 00:25:56,520 და ა.შ., პატივისცემის გარეშე ციფრები, ბარათები. 571 00:25:56,520 --> 00:26:00,900 და ახლა ისინი, როგორც ჩანს, მაგალითად, უნდა დააჯგუფეს ნომერი. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 ძალიან კარგი. 574 00:26:08,910 --> 00:26:12,370 >> ყველა უფლება, ასე აპირებს საბოლოო ნაბიჯი აქ? 575 00:26:12,370 --> 00:26:16,950 მას შემდეგ, რაც ჩვენ გვაქვს ოთხი დახარისხებული ლუქსი, რა ჩვენ უნდა გავაკეთოთ, რომ ოთხი piles 576 00:26:16,950 --> 00:26:20,059 იმისათვის, რომ მივაღწიოთ ერთი დალაგებულია deck, უბრალოდ? 577 00:26:20,059 --> 00:26:21,350 ასე რომ, ჩვენ უნდა შერწყმა მათ. 578 00:26:21,350 --> 00:26:25,160 >> ასე რომ, არსებობს საინტერესო იდეა, რომ ერთხელ, daresay, ძალიან ინტუიციური კი 579 00:26:25,160 --> 00:26:28,140 თუ თქვენ, შესაძლოა, არასდროს ხელი გაარტყა რომ სახის label იგი. 580 00:26:28,140 --> 00:26:31,900 ამ ფუნდამენტური ცნება გამყოფი პრობლემა არ ნახევარ ამ დროს, 581 00:26:31,900 --> 00:26:33,410 მაგრამ მაინც ოთხი ცალი. 582 00:26:33,410 --> 00:26:36,810 საქმე საკმაოდ ბევრი ფუნდამენტურად იდენტური პრობლემები 583 00:26:36,810 --> 00:26:40,480 იზოლაცია ერთმანეთს, და შემდეგ შერწყმის შედეგები. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 და, კარგი, გაკეთდეს. 586 00:26:50,140 --> 00:26:52,140 ყველა უფლება, დიდი მრგვალი ტაში, თუ შეგვეძლო. 587 00:26:52,140 --> 00:26:56,480 >> [ტაში] 588 00:26:56,480 --> 00:26:59,740 >> დინამიკები: მე არ ვიცი, რა თქვენ გააკეთოს ეს, მაგრამ აქ წასვლა. 589 00:26:59,740 --> 00:27:01,690 დიდი მადლობა, რომ. 590 00:27:01,690 --> 00:27:04,660 ასე რომ, ვნახოთ, ორი წუთი და რვა წამში, 591 00:27:04,660 --> 00:27:07,490 თუ გსურთ გამოწვევა თქვენს მეგობრებს. 592 00:27:07,490 --> 00:27:12,160 მერე რა იქნება შეიძლება წართმევას ამ 593 00:27:12,160 --> 00:27:13,830 რომ ჩვენ შეგვიძლია ბერკეტები უფრო ზოგადად? 594 00:27:13,830 --> 00:27:16,080 ისე, ვფიქრობ, უკან ამ მასივი ნომრები, 595 00:27:16,080 --> 00:27:19,060 და ვფიქრობ, რომ ახლა ზოგიერთი pseudocode ჩვენ წერილობითი წარსულში, 596 00:27:19,060 --> 00:27:22,080 და ეს იყო pseudocode for გადაჭრის სატელეფონო წიგნი პრობლემა. 597 00:27:22,080 --> 00:27:25,150 რომლის დროსაც, pseudocode I ჩამოთვლილ უფრო მეთოდური გზა 598 00:27:25,150 --> 00:27:28,400 აღწერს, როგორ მე ძალიან ინტუიტიური ადამიანის ალგორითმი გამყოფი ტელეფონი 599 00:27:28,400 --> 00:27:31,650 წიგნი ნახევარი, ვიმეორებ, ვიმეორებ, ვიმეორებ, სანამ მე ვინმეს მსგავსად, მაიკ სმიტი, 600 00:27:31,650 --> 00:27:33,790 თუ იგი მართლაც სატელეფონო წიგნი. 601 00:27:33,790 --> 00:27:37,610 >> მაგრამ სახის გამოიყენება რა მე მოვუწოდებ ძალიან განმეორებითი მიდგომა აქ, 602 00:27:37,610 --> 00:27:42,160 კერძოდ გაფრთხილების line 8 და ხაზი 11. 603 00:27:42,160 --> 00:27:46,750 იმ მტკიცებულება განმეორებითი მიდგომა, looping მიდგომა, 604 00:27:46,750 --> 00:27:49,040 რადგან სწორედ ქცევის ისინი გამოიწვიოს. 605 00:27:49,040 --> 00:27:52,910 იმ ხაზების ორივე ამბობენ წასვლა ხაზი სამი, და შეგიძლიათ სახის 606 00:27:52,910 --> 00:27:55,140 ვფიქრობ, რომ თქვენს გონების თვალით, როგორც loop. 607 00:27:55,140 --> 00:27:59,080 ის გეუბნებოდით დაბრუნდეს დაიხევს სამი და ვიმეორებ, ისევ და ისევ, 608 00:27:59,080 --> 00:28:00,010 და ისევ. 609 00:28:00,010 --> 00:28:04,410 >> მაგრამ რა, თუ ბერკეტი გასაღები იდეა აქ რომ ჩვენ არ ბოლო დროს, 610 00:28:04,410 --> 00:28:10,280 და გაამარტივებს line 8 და ხაზის 11 და მათი მეზობლები 611 00:28:10,280 --> 00:28:12,840 როგორც მხოლოდ ამ, ყვითელი. 612 00:28:12,840 --> 00:28:16,480 ეს არ ფუნდამენტურად შეკვეცას pseudocode ძალიან, 613 00:28:16,480 --> 00:28:20,530 მაგრამ ეს ძირეულად შეცვლის ბუნების ალგორითმი. 614 00:28:20,530 --> 00:28:24,220 რა მე ახლა ამბობს ნაბიჯი 7 ნაბიჯი 10, 615 00:28:24,220 --> 00:28:29,140 მოძიება Mike ზუსტად იგივე გზა, 616 00:28:29,140 --> 00:28:31,580 მაგრამ მხოლოდ მარცხენა ნახევარი ან მარჯვენა ნახევარში. 617 00:28:31,580 --> 00:28:33,420 >> ასე რომ, სხვა სიტყვებით, თუ I იწყება ერთი ნაბიჯი, 618 00:28:33,420 --> 00:28:36,150 შეარჩიო სატელეფონო წიგნი, ღია, საშუალო სატელეფონო წიგნი, შევხედოთ სახელები, 619 00:28:36,150 --> 00:28:39,010 თუ Smith შორის არის სახელის, დარეკეთ Mike, სხვა 620 00:28:39,010 --> 00:28:44,340 თუ სმიტი ადრე წიგნი, ნაბიჯი შვიდი ძიება მაიკ მარცხენა ნახევარში წიგნი. 621 00:28:44,340 --> 00:28:47,130 მაგრამ, რომ სახის იგრძნობა ის ტოვებს ჩემთვის ჩამოკიდებული, არა? 622 00:28:47,130 --> 00:28:49,240 ყვითელი, არის სწავლების, მაგრამ როგორ უნდა 623 00:28:49,240 --> 00:28:51,870 ძიება Mike მარცხენა ნახევარი სატელეფონო წიგნი? 624 00:28:51,870 --> 00:28:54,210 სად აქვს ალგორითმი, რომელიც მე 625 00:28:54,210 --> 00:28:57,100 შეგიძლიათ მოძებნოთ ვინმე მოსწონს მაიკ სმიტი? 626 00:28:57,100 --> 00:28:58,980 ისე, ეს ვნებათაღელვა us სახე. 627 00:28:58,980 --> 00:29:03,090 შემიძლია სიტყვასიტყვით გამოყენება ზუსტი იგივე პროგრამა ეფექტურად მიმდინარეობს ზევით 628 00:29:03,090 --> 00:29:06,490 კიდევ ერთხელ და ხელახლა გაშვებას იგივე ხაზების კოდი. 629 00:29:06,490 --> 00:29:10,610 >> ასე რომ, მიუხედავად იმისა, რომ ეს უნდა გრძნობდეს როგორიც ცოტა ციკლურ განმარტება 630 00:29:10,610 --> 00:29:13,480 სადაც თქვენ პასუხობდა ვინმეს კითხვა მხოლოდ ერთგვარი ითხოვს 631 00:29:13,480 --> 00:29:15,990 იგივე კითხვა ისევ, როგორიცაა, რატომ, რატომ, რატომ? 632 00:29:15,990 --> 00:29:21,580 რეალობა ის არის, იმიტომ, რომ ჩვენ რთული კოდირებული რამდენიმე სპეციალური ხაზები, ნაბიჯი 4, 633 00:29:21,580 --> 00:29:25,320 რომელიც თუ, და ნაბიჯი, რომელიც 12 ეფექტურად მორიგი ფილიალი, 634 00:29:25,320 --> 00:29:30,120 იმიტომ, რომ ჩვენ გვაქვს ის stopgap ღონისძიებები, ეს ალგორითმი შეწყვიტოს თუ ჩვენ 635 00:29:30,120 --> 00:29:32,050 მოძიების მაიკ, თუ არა. 636 00:29:32,050 --> 00:29:36,810 მაგრამ ნაბიჯი 7 და 10 ახლა, ჩვენ გვაქვს რა ჩვენ მოვუწოდებთ რეკურსიული ალგორითმი. 637 00:29:36,810 --> 00:29:40,420 და უკან არის მართლაც ძლიერი იდეა, რომ ცოტა გონება bending, პირველ რიგში, 638 00:29:40,420 --> 00:29:42,500 რომ ჩვენ შეგვიძლია ახლა ვრცელდება ასეთია. 639 00:29:42,500 --> 00:29:46,600 >> შერწყმა დალაგების იქნება ბოლო დალაგების დავაკვირდებით, მინიმუმ კლასში ფორმალურად. 640 00:29:46,600 --> 00:29:50,040 და ეს ძირეულად განსხვავებული იმ ბოლო სამი, და რა თქმა უნდა, 641 00:29:50,040 --> 00:29:52,140 ბოლო ოთხი თუ ჩვენ მოიცავს bogosort. 642 00:29:52,140 --> 00:29:54,810 აი pseudocode შერწყმა დალაგების. 643 00:29:54,810 --> 00:30:00,170 როდესაც შეყვანის N ელემენტები, ასე მოცემული მასივი ზომა n, თუ n ნაკლებია, ვიდრე 2, 644 00:30:00,170 --> 00:30:01,040 დაბრუნდება. 645 00:30:01,040 --> 00:30:03,610 ასე რომ, რატომ მაქვს, საღი აზრის შეამოწმოს პირველი? 646 00:30:03,610 --> 00:30:09,477 რა გავლენა თუ მე მხრივ, თქვენ მასივი, რომლის სიგრძე n ნაკლებია, ვიდრე 2? 647 00:30:09,477 --> 00:30:11,060 ეს უკვე დახარისხებული, ცხადია, არა? 648 00:30:11,060 --> 00:30:13,640 რადგან სიაში ან აქვს ერთი ელემენტი, რომელიც trivially 649 00:30:13,640 --> 00:30:15,180 დახარისხებული რადგან ის ერთადერთი, რაც არ არსებობს. 650 00:30:15,180 --> 00:30:18,138 ან, ეს ზომა ნულოვანი რაც იმას ნიშნავს, არაფერი დასალაგებლად, ამიტომ ბუნებით 651 00:30:18,138 --> 00:30:18,720 ეს დახარისხებული. 652 00:30:18,720 --> 00:30:20,410 არსებობს უბრალოდ არაფერი არასწორი არსებობს. 653 00:30:20,410 --> 00:30:22,310 ასე რომ ჩვენი ე.წ. ბაზის შემთხვევაში. 654 00:30:22,310 --> 00:30:24,440 >> რომ მსგავსი სულისკვეთებით რა გავაკეთეთ ერთად მაიკ. 655 00:30:24,440 --> 00:30:26,023 თუ მაიკ სატელეფონო წიგნი, მას. 656 00:30:26,023 --> 00:30:27,740 თუ ის არ არის, უარი თქვას. 657 00:30:27,740 --> 00:30:31,240 ეს ე.წ. ბაზის შემთხვევაში, რათა დავრწმუნდეთ, ეს ალგორითმი ბოლოს დღეს 658 00:30:31,240 --> 00:30:33,540 შეწყდება გარკვეულ შემთხვევებში. 659 00:30:33,540 --> 00:30:37,890 >> მაგრამ აქ ნახტომი რწმენის ახლა სხვაგან, დასალაგებლად მარცხენა ნახევარში ელემენტები, 660 00:30:37,890 --> 00:30:39,740 მაშინ დასალაგებლად მარჯვენა ნახევარში ელემენტები, 661 00:30:39,740 --> 00:30:41,189 შემდეგ შერწყმა დახარისხებული halves. 662 00:30:41,189 --> 00:30:43,230 და აქ, სადაც იგი გრძნობს როგორც ჩვენ copping out. 663 00:30:43,230 --> 00:30:46,900 მე გთხოვეთ დასალაგებლად n ელემენტებს, და მე 664 00:30:46,900 --> 00:30:50,712 განაცხადა, ბატონო, ამის დახარისხება მარცხენა და დახარისხება უფლება. 665 00:30:50,712 --> 00:30:52,420 მაგრამ მე რომ ერთი სხვა რამ, და ეს 666 00:30:52,420 --> 00:30:55,530 არის გასაღები თემა, როგორც ჩანს, in ინტუიცია ჯერჯერობით, 667 00:30:55,530 --> 00:30:57,380 არსებობს ამ მესამე საფეხურის შერწყმით. 668 00:30:57,380 --> 00:31:00,430 რომელიც მიუხედავად იმისა, რომ როგორც ჩანს, იმდენად dumb სული, 669 00:31:00,430 --> 00:31:02,320 მინდა უბრალოდ შერწყმა რამ ერთად, როგორც ჩანს, 670 00:31:02,320 --> 00:31:05,380 იყოს გასაღები ნაბიჯი reassembly ორი პრობლემა, რომელიც 671 00:31:05,380 --> 00:31:07,330 დაიყო საბოლოოდ ნახევარი. 672 00:31:07,330 --> 00:31:12,090 >> ასე რომ შერწყმა დალაგების, მოდით, თუ თქვენ იუმორი ჩემთვის, კიდევ ერთი საპროტესტო აქცია, 673 00:31:12,090 --> 00:31:14,730 ასე რომ, ჩვენ გვაქვს ნომრები მუშაობა. 674 00:31:14,730 --> 00:31:19,470 შემიძლია გაცვლა რვა სტრესი ბურთები რვა ადამიანი? 675 00:31:19,470 --> 00:31:29,320 ყველა უფლება, როგორ შესახებ, სამი, ოთხი ამ სექციაში, ხუთი, ექვსი, და მოდით 676 00:31:29,320 --> 00:31:30,720 არ 7, 8, მოდის up. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, yeah OK. 679 00:31:36,520 --> 00:31:38,640 მინუს 8, იქ წასვლა, პლუს 1. 680 00:31:38,640 --> 00:31:39,150 შესანიშნავი. 681 00:31:39,150 --> 00:31:42,000 ყველა უფლება მოდის up, მოდით სწრაფად გაძლევთ ნომრები. 682 00:31:42,000 --> 00:31:50,800 მეორე, მესამე, მეოთხე, ნომერი ხუთი, ექვსი, შვიდი, რვა. 683 00:31:50,800 --> 00:31:52,140 მე რვა სწორად ამ დროს. 684 00:31:52,140 --> 00:31:56,390 >> OK, ასე რომ წავიდეთ წინ, თუ შეიძლება, და მოდით დალაგებული ორიგინალური მიზნით 685 00:31:56,390 --> 00:31:59,810 რომ ჩვენ გვქონდა გუშინ რაც ჩანდა როგორიცაა, თუ თქვენ არ ხართ. 686 00:31:59,810 --> 00:32:03,620 და მოდით ამას წინ მაგიდასთან. 687 00:32:03,620 --> 00:32:06,510 ყველა უფლება, ასე რომ შერწყმა დალაგების. 688 00:32:06,510 --> 00:32:08,820 ეს არის, სადაც ეს მიიღოს სახის საინტერესო, 689 00:32:08,820 --> 00:32:12,800 იმიტომ, რომ მე, როგორც ჩანს, რაც თავს ასე გაცილებით ნაკლები ინფორმაცია დღეს. 690 00:32:12,800 --> 00:32:15,149 >> ასე რომ შერწყმა დალაგების, პირველ რიგში, შეყვანის N ელემენტები, 691 00:32:15,149 --> 00:32:18,440 და აშკარად არანაკლებ ორი, ეს რვა, ამიტომ კიდევ რამდენიმე გასაკეთებელი. 692 00:32:18,440 --> 00:32:21,140 ასე რომ, ახლა გონებრივად ჩვენ როგორც კლასი ახლა სხვაგან ფილიალი, 693 00:32:21,140 --> 00:32:22,540 რაც იმას ნიშნავს, სამი ნაბიჯი. 694 00:32:22,540 --> 00:32:25,017 პირველ რიგში, მე უნდა დასალაგებლად მარცხენა ნახევარში ელემენტები. 695 00:32:25,017 --> 00:32:26,350 ასე რომ, როგორ წავიდეთ შესახებ ამით? 696 00:32:26,350 --> 00:32:28,950 ისე, მე ვაპირებ სახის სულიერად დაყოფის სია აქ, 697 00:32:28,950 --> 00:32:30,700 თქვენ არ უნდა ფიზიკური გადაადგილება, და მე 698 00:32:30,700 --> 00:32:33,180 ვაპირებ ფოკუსირება მხოლოდ მარცხენა ნახევარში ელემენტები აქ. 699 00:32:33,180 --> 00:32:36,770 ასე როგორ უნდა წავიდეს შესახებ დახარისხება სიაში არის ზომა ოთხი? 700 00:32:36,770 --> 00:32:38,730 რა არის ჩემი ალგორითმი? 701 00:32:38,730 --> 00:32:42,580 პირველი მე შეამოწმოს არის თუ n ნაკლებია, ვიდრე ორი, არა, ასე გაგრძელება სხვაგან ბლოკი კვლავ. 702 00:32:42,580 --> 00:32:43,900 Sort მარცხენა ნახევარში ელემენტები. 703 00:32:43,900 --> 00:32:45,608 >> ასე რომ, ახლა ისევ, გონებრივად და ეს არის, სადაც 704 00:32:45,608 --> 00:32:49,550 თქვენ უნდა დაერიცხება ბევრი ფსიქიკური ისტორია, თუ გნებავთ. 705 00:32:49,550 --> 00:32:51,940 ახლა მე დახარისხება მარცხენა ნახევარში მარცხენა ნახევარში. 706 00:32:51,940 --> 00:32:57,000 ყველა უფლება, ასე რომ, ახლა მე ჩემს იგივე შერწყმა დახარისხება ალგორითმი, არის N ნაკლებია, ვიდრე ორი? 707 00:32:57,000 --> 00:33:00,590 არა, ეს ორი, ამიტომ უნდა დასალაგებლად მარცხენა ნახევარში და მარჯვენა ნახევარში. 708 00:33:00,590 --> 00:33:02,042 ასე რომ, აქ ჩვენ გადასვლა, დასალაგებლად მარცხენა ნახევარი. 709 00:33:02,042 --> 00:33:03,750 რატომ არ მხოლოდ ერთი ნაბიჯით წინ. 710 00:33:03,750 --> 00:33:04,415 რა გქვია? 711 00:33:04,415 --> 00:33:04,860 >> აუდიტორია: Darren. 712 00:33:04,860 --> 00:33:05,260 >> დინამიკები დან. 713 00:33:05,260 --> 00:33:06,040 Dan გადადგა ნაბიჯი. 714 00:33:06,040 --> 00:33:06,748 >> აუდიტორია: Darren. 715 00:33:06,748 --> 00:33:09,000 დინამიკები: Darren, გაკეთდეს. 716 00:33:09,000 --> 00:33:10,090 ხომ არ ამბობენ, Darren ან დენ? 717 00:33:10,090 --> 00:33:10,550 >> აუდიტორია: Darren. 718 00:33:10,550 --> 00:33:11,216 >> დინამიკები: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren დაიხია წინ და ახლა დახარისხებული. 720 00:33:14,422 --> 00:33:16,130 და ეს თითქმის inane პრეტენზია, არა? 721 00:33:16,130 --> 00:33:18,862 მე ნამდვილად არ ჩანს, უნდა მისაღწევად არაფერი, მაგრამ მოდით გაგრძელება. 722 00:33:18,862 --> 00:33:20,820 ახლა ნება მომეცით დასალაგებლად მარჯვენა ნახევარში ელემენტები. 723 00:33:20,820 --> 00:33:21,200 რა გქვია? 724 00:33:21,200 --> 00:33:21,690 >> აუდიტორია: ლუკა. 725 00:33:21,690 --> 00:33:22,273 >> დინამიკები: ლუკა. 726 00:33:22,273 --> 00:33:23,400 მოდის, წინ გადადგმული ნაბიჯია. 727 00:33:23,400 --> 00:33:25,640 კეთდება, მე დახარისხებული ლუკა. 728 00:33:25,640 --> 00:33:28,570 მარცხენა ნახევარში არის გადანაწილებული და მარჯვენა ნახევარში არის დახარისხებული, 729 00:33:28,570 --> 00:33:30,770 თუმცა ისევ და ისევ, იქ გადამწყვეტი აქ. 730 00:33:30,770 --> 00:33:32,940 რა შემიძლია შემდეგი უნდა გავაკეთოთ? 731 00:33:32,940 --> 00:33:33,941 შერწყმა დახარისხებული halves. 732 00:33:33,941 --> 00:33:36,648 ახლა ჩვენ ვაპირებთ, რომ უბრალოდ უნდა ყველას უკან და მეოთხე, ამ გზით, 733 00:33:36,648 --> 00:33:38,620 რადგან მე სახის უნდა გარკვეული ნულიდან სივრცეში. 734 00:33:38,620 --> 00:33:40,411 ის თითქმის მოსწონს ეს ბიჭები არიან მაგიდა, 735 00:33:40,411 --> 00:33:42,460 და მე უნდა ზოგიერთი ოთახი გადაადგილება მათ გარშემო. 736 00:33:42,460 --> 00:33:44,170 ამიტომ, მე ვაპირებ, რომ შერწყმა თქვენ ბიჭები ეძებს 737 00:33:44,170 --> 00:33:45,960 მარცხენა ნახევარში და მარჯვენა ნახევარში. 738 00:33:45,960 --> 00:33:48,740 და ვინც აშკარად მოდის პირველი, მარცხენა ნახევარში და მარჯვენა ნახევარში? 739 00:33:48,740 --> 00:33:52,710 ასე რომ, მარჯვენა ნახევარში, მოდით გადაადგილება Luke მეტი აქ Darren ის პოზიციას. 740 00:33:52,710 --> 00:33:57,640 და ახლა შერწყმა მათი მარცხენა ნახევარში, Darren აპირებს გადავიდეს უფლება არსებობს. 741 00:33:57,640 --> 00:33:59,750 >> ასე რომ იგრძნობა თითქმის bubble sort ეფექტი, 742 00:33:59,750 --> 00:34:02,482 მაგრამ ჩემი ძირითადი ალგორითმი, ძალიან განსხვავებული ამ დროს. 743 00:34:02,482 --> 00:34:04,815 მაგრამ ახლა არის სადაც რამ კიდევ ცოტა შემაშფოთებელი იმიტომ, რომ თქვენ 744 00:34:04,815 --> 00:34:06,810 უნდა გადახვევა გონებრივად სად დატოვება მოჰყვა. 745 00:34:06,810 --> 00:34:09,893 მე უბრალოდ შეუერთდა დახარისხებული halves, რაც იმას ნიშნავს, რომ მე ვარ, სადაც ჩემი ალგორითმი? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 მე უნდა დასალაგებლად მარჯვენა ნახევარში, არა? 748 00:34:13,770 --> 00:34:15,910 >> თუ თქვენ გადახვევა, ფაქტიურად ვიდეო, თქვენ 749 00:34:15,910 --> 00:34:18,339 , რომ ჩვენ მივიღეთ ეს წერტილი და ლუკა Darren 750 00:34:18,339 --> 00:34:21,370 მიერ დახარისხება მარცხენა ნახევარში მარცხენა ნახევარში. 751 00:34:21,370 --> 00:34:23,430 შემდეგ ჩვენ გაერთიანდა იმ დახარისხებული halves, რომელიც 752 00:34:23,430 --> 00:34:27,941 ნიშნავს, რომ შემდეგი ნაბიჯი არის ერთგვარი მარჯვენა ნახევარში მარცხენა ნახევარში. 753 00:34:27,941 --> 00:34:29,649 ყველა უფლება, მოდით ამისათვის უფრო სწრაფად. 754 00:34:29,649 --> 00:34:33,282 ყველა უფლება, ექვსი, მე ვაპირებ იმის მტკიცებას, თქვენ ახლა დახარისხებული, მოდის ნაბიჯია. 755 00:34:33,282 --> 00:34:33,990 რა გქვია? 756 00:34:33,990 --> 00:34:34,589 >> აუდიტორია: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> დინამიკები: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano არის გადანაწილებული. 759 00:34:36,010 --> 00:34:36,450 და რა გქვია? 760 00:34:36,450 --> 00:34:37,080 >> აუდიტორია: Alex. 761 00:34:37,080 --> 00:34:38,379 >> დინამიკები: Alex არის გადანაწილებული. 762 00:34:38,379 --> 00:34:40,750 მარცხენა ნახევარში, მარჯვენა ნახევარში, რა არის საბოლოო ნაბიჯი? 763 00:34:40,750 --> 00:34:41,250 შერწყმა. 764 00:34:41,250 --> 00:34:44,310 საკმაოდ ტრივიალური, ასე რომ მე ვაპირებთ შერწყმა ექვს, 765 00:34:44,310 --> 00:34:46,930 ერთი ნაბიჯი უკან, რვა, ერთი ნაბიჯი უკან. 766 00:34:46,930 --> 00:34:49,530 და ახლა შეამჩნია ეს არის სასარგებლო takeaway, რა 767 00:34:49,530 --> 00:34:53,930 არის ჭეშმარიტია მარცხენა ნახევარში სიაში, მიუხედავად იმისა, თუ როგორ დაიწყო? 768 00:34:53,930 --> 00:34:55,090 ეს დახარისხებული. 769 00:34:55,090 --> 00:34:57,750 >> ახლა ეს არ არის დახარისხებული დიდი სქემა რამ, 770 00:34:57,750 --> 00:35:00,250 მაგრამ ეს დახარისხებული დამოუკიდებლად მეორე ნახევარში. 771 00:35:00,250 --> 00:35:04,100 ახლა რა ნაბიჯი ავირჩიე თუ შეინახოს გადახვევა ამბავი დაიწყო? 772 00:35:04,100 --> 00:35:05,680 ახლა უნდა დასალაგებლად მარჯვენა ნახევარში. 773 00:35:05,680 --> 00:35:07,630 ახლა ჩვენ გზა უკან დასაწყისში ამბავი, 774 00:35:07,630 --> 00:35:08,921 და მოდით ეს უფრო სწრაფად. 775 00:35:08,921 --> 00:35:11,320 ამიტომ, მე ვაპირებ დასალაგებლად მარჯვენა ნახევარში მთელი სია. 776 00:35:11,320 --> 00:35:13,060 რა არის შემდეგი ნაბიჯი? 777 00:35:13,060 --> 00:35:15,840 დასალაგებლად მარცხენა ნახევარი მარჯვენა ნახევარში. 778 00:35:15,840 --> 00:35:18,715 დასალაგებლად მარცხენა ნახევარში მარცხენა ნახევარში მარჯვენა ნახევარში. 779 00:35:18,715 --> 00:35:19,590 და რა გქვია? 780 00:35:19,590 --> 00:35:20,230 >> აუდიტორია: ომარ. 781 00:35:20,230 --> 00:35:21,970 >> დინამიკები: Omar, წინ გადადგმული ნაბიჯია, გაკეთდეს. 782 00:35:21,970 --> 00:35:22,860 მარცხენა ნახევარში დალაგებულია. 783 00:35:22,860 --> 00:35:23,330 და რა გქვია? 784 00:35:23,330 --> 00:35:23,820 >> აუდიტორია: Chris. 785 00:35:23,820 --> 00:35:25,620 >> დინამიკები: Chris, მიიღოს ნაბიჯი წინ, ახლა დახარისხებული. 786 00:35:25,620 --> 00:35:27,010 რა არის გადამწყვეტი ახლა? 787 00:35:27,010 --> 00:35:27,510 შერწყმა. 788 00:35:27,510 --> 00:35:30,509 ასე რომ, ერთი ვაპირებთ უერთდება ადგილი აქ, თუ შეიძლება მიიღოს უკან გადადგმული ნაბიჯია, 789 00:35:30,509 --> 00:35:32,930 და სამი აპირებს ერთი ნაბიჯი უკან, შერწყმა. 790 00:35:32,930 --> 00:35:38,080 ასე რომ მარცხენა ნახევარში მარჯვენა ნახევარში, არის გადანაწილებული. 791 00:35:38,080 --> 00:35:41,747 გულწრფელად ვამბობ, ეს ალგორითმი იგრძნობა გაყვანაა გზა მეტი დრო, ვიდრე ადრე, 792 00:35:41,747 --> 00:35:44,830 მაგრამ, თუ ეს გავაკეთეთ რეალურ დროში, ჩვენ გამოგიგზავნით ვნახოთ, რა takeaways იქნება. 793 00:35:44,830 --> 00:35:47,970 ახლა აქ ვარ, უფლება ნახევარი მარჯვენა ნახევარში, 794 00:35:47,970 --> 00:35:50,170 ნება მომეცით წავიდეთ წინ და დასალაგებლად მარცხენა ნახევარში. 795 00:35:50,170 --> 00:35:51,482 წინ გადადგმული ნაბიჯია, რაც თქვენი სახელი? 796 00:35:51,482 --> 00:35:52,190 აუდიტორია: Ramsey. 797 00:35:52,190 --> 00:35:53,210 დინამიკები: Ramsey არის გადანაწილებული. 798 00:35:53,210 --> 00:35:53,570 რა გქვია? 799 00:35:53,570 --> 00:35:54,200 >> აუდიტორია: მარინა. 800 00:35:54,200 --> 00:35:57,033 >> დინამიკები: მარინა ახლა დალაგებულია როგორც ასევე, თუ თქვენ მიიღოს ერთი წინ გადადგმული ნაბიჯია. 801 00:35:57,033 --> 00:36:00,690 გადამწყვეტი აქ არის შერწყმა, მე აპირებს pluck ჩემი ორი სიები, 802 00:36:00,690 --> 00:36:01,720 მარცხენა და მარჯვენა. 803 00:36:01,720 --> 00:36:05,150 ხუთი აპირებს მოდის პირველი, და შვიდი აპირებს მოვა შემდეგი. 804 00:36:05,150 --> 00:36:06,410 და ისევ, ეს არის მიზანმიმართული. 805 00:36:06,410 --> 00:36:08,535 ის ფაქტი, რომ ისინი იღებენ მივიწევთ წინ და უკან 806 00:36:08,535 --> 00:36:12,997 იგულისხმება წარმოადგენს, რომ ჩვენ არ შეგვიძლია ამისათვის ალგორითმი ადგილზე, როგორც ადვილად 807 00:36:12,997 --> 00:36:15,830 როგორც ბუშტი დალაგების, და შერჩევის დალაგების, და Insertion დალაგების სადაც ჩვენ უბრალოდ 808 00:36:15,830 --> 00:36:16,960 დაცული შევცვალე ხალხი. 809 00:36:16,960 --> 00:36:19,940 მე სიტყვასიტყვით უნდა ერთგვარი ნულიდან ქაღალდი, რომელიც 810 00:36:19,940 --> 00:36:21,827 იმისათვის, რომ ეს ხალხი, ხოლო მე შერწყმა, 811 00:36:21,827 --> 00:36:23,410 და მერე შეგიძლიათ განათავსოთ მათ უკან ადგილი. 812 00:36:23,410 --> 00:36:27,260 და ეს გასაღები იმიტომ, რომ მე გამოყენებით ახალი რესურსი, სივრცეში, არა მხოლოდ დროს. 813 00:36:27,260 --> 00:36:28,270 >> OK, ეს არის საოცარი. 814 00:36:28,270 --> 00:36:32,050 მარცხენა ნახევარში დალაგებულია, მარჯვენა ნახევარში არის დახარისხებული, ახლა, რომ გასაღები შერწყმის ნაბიჯი. 815 00:36:32,050 --> 00:36:33,450 როგორ ვარ მე აპირებს შერწყმა ეს? 816 00:36:33,450 --> 00:36:35,470 ასე რომ, თუ თქვენ დაიცვას ჩემი მარცხენა და მარჯვენა ხელი, 817 00:36:35,470 --> 00:36:38,930 მე ვაპირებ აღვნიშნო ჩემი მარცხენა ხელი მარცხენა ნახევარში, ჩემი მარჯვენა ხელი 818 00:36:38,930 --> 00:36:42,680 მარჯვენა ნახევარში, და ახლა მე უნდა გადაწყვეტს, ეტაპობრივად, რომელთანაც შერწყმა. 819 00:36:42,680 --> 00:36:44,650 რომელიც აშკარად მოდის პირველი? 820 00:36:44,650 --> 00:36:45,150 ნომერ პირველი. 821 00:36:45,150 --> 00:36:47,327 ასე რომ, მოდის, აქ, აქ არის ჩვენი ნულიდან pad. 822 00:36:47,327 --> 00:36:49,910 ასე რომ, ახლა ნომერ, და შეამჩნია, რა მე გავაკეთებ ჩემს მარჯვენა ხელს, 823 00:36:49,910 --> 00:36:54,152 მე ვაპირებ გადაადგილება ჩემი უფლება ხელის ერთი ნაბიჯი მეტი აღვნიშნო ნომერი სამი, 824 00:36:54,152 --> 00:36:55,860 და ახლა მე უნდა მიიღოს იგივე გადაწყვეტილება. 825 00:36:55,860 --> 00:36:58,387 და რეალურად დგანან უფლება წინა ლუკა აქ თუ შეიძლება, 826 00:36:58,387 --> 00:36:59,720 იმიტომ, რომ ეს არის ჩვენი ნულიდან pad. 827 00:36:59,720 --> 00:37:00,610 ასე რომ, ვინც მოდის შემდეგი? 828 00:37:00,610 --> 00:37:05,000 ჩვენ გვაქვს ლუკა ნომერი ორი ან Chris ერთად ნომერი სამი. 829 00:37:05,000 --> 00:37:07,460 ცხადია ლუკა, ნომერი ორ, ასე რომ აქ მოვიდა. 830 00:37:07,460 --> 00:37:11,270 >> მაგრამ ჩემი მარცხენა ხელის ახლა აპირებს შეიძლება incremented აღვნიშნო Darren, 831 00:37:11,270 --> 00:37:15,160 და აქ არის გასაღები წართმევას გაერთიანების, მე ვაპირებ შენარჩუნება ამით, 832 00:37:15,160 --> 00:37:17,340 ცხადია, თუ სახის საქართველოს ლოგიკის. 833 00:37:17,340 --> 00:37:19,670 მაგრამ ხელები არ აპირებს წავიდეს უკან, 834 00:37:19,670 --> 00:37:23,861 რაც იმას ნიშნავს, რომ მე მხოლოდ ოდესმე გადადის მარცხენა ჩემი შერწყმის პროცესი, 835 00:37:23,861 --> 00:37:26,360 და ეს იქნება გასაღები ჩვენი ანალიზი რაღაც მომენტში. 836 00:37:26,360 --> 00:37:27,859 >> ახლა მოდით დავამთავროთ ეს up სწრაფად. 837 00:37:27,859 --> 00:37:31,650 ამიტომ სამი მოდის მომდევნო, მაშინ ოთხი მოდის მომდევნო, 838 00:37:31,650 --> 00:37:38,750 და ახლა ხუთი მოდის შემდეგ, მაშინ ექვსი, და შვიდი, და მაშინ საბოლოოდ რვა. 839 00:37:38,750 --> 00:37:42,960 იგრძნობა ნელი ალგორითმი არ არის, მაგრამ თუ ჩვენ რეალურად 840 00:37:42,960 --> 00:37:45,510 აწარმოებს მას იგივე სახის საათის სიჩქარე, ასე 841 00:37:45,510 --> 00:37:48,106 ვთქვათ, იგივე ticking საათი, როგორც ადრე. 842 00:37:48,106 --> 00:37:48,605 რატომ? 843 00:37:48,605 --> 00:37:51,100 კარგად, მოდით შეხედეთ ბოლოს შედეგი. 844 00:37:51,100 --> 00:37:56,990 >> მოდით დავუბრუნდეთ მეტი აქ, ნება მომეცით დახევის up აქცია ვიზუალურად 845 00:37:56,990 --> 00:37:59,030 ის, რაც ჩვენ გავაკეთეთ. 846 00:37:59,030 --> 00:38:06,110 მასშტაბირება აქ, ამ აქ, ვეუბნებოდი Firefox 847 00:38:06,110 --> 00:38:08,200 ჩვენ გვინდა, რომ რიგი up ამ ყუთში, მოდით 848 00:38:08,200 --> 00:38:11,260 ამბობენ, bubble sort, რომელთანაც ჩვენ უკვე კარგად ნაცნობი, 849 00:38:11,260 --> 00:38:14,130 შერჩევის დალაგების, რომელიც სხვა საკმაოდ მარტივია ერთი, 850 00:38:14,130 --> 00:38:18,250 და ახლა დღევანდელი შერწყმა ჯიშია, იქნება ჩვენი კლიმატური დასასრული. 851 00:38:18,250 --> 00:38:21,530 მიზეზი დასჭირდა იმდენად აღარ აქ ადამიანებს და მომაყენა არის, 852 00:38:21,530 --> 00:38:23,480 ცხადია, მე ვუხსნიდი, ყოველი ნაბიჯი. 853 00:38:23,480 --> 00:38:26,920 მაგრამ თუ უბრალოდ შეასრულოს ამ, ბევრად როგორც ჩვენ bubble sort და შერჩევა 854 00:38:26,920 --> 00:38:30,890 სახის არა მხოლოდ ვიზუალურად, watch რამდენად უფრო ეფექტურად 855 00:38:30,890 --> 00:38:33,330 ამ leveraging of სამმართველოს და დაპყრობის 856 00:38:33,330 --> 00:38:39,150 შეიძლება მიმართა მონაცემები კომპლექტი, არის კი არა ზომის რვა, მაგრამ კიდევ ბევრი რამ, 857 00:38:39,150 --> 00:38:39,970 გაცილებით დიდია. 858 00:38:39,970 --> 00:38:44,585 მე გაძლევთ შერწყმა დალაგების, გვერდით მხარე ამ სხვა ალგორითმები. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 ეს აპირებს მიიღოს მტკივნეული სწრაფად და დასასრულით 861 00:38:58,530 --> 00:39:00,890 არ არის განსაკუთრებით climactic, ისინი უბრალოდ დასრულდება up დახარისხებული. 862 00:39:00,890 --> 00:39:05,280 მაგრამ მთავარი წართმევას ის არის, რომ შეხედეთ, როგორ ბევრად უფრო სწრაფად შერწყმა დალაგების 863 00:39:05,280 --> 00:39:08,110 იყო, თუ ფიქრობთ, რომ მე ვარ უბრალოდ სახის ძვირფასი თქვენთვის. 864 00:39:08,110 --> 00:39:13,100 თუ ამას ერთი საბოლოო დრო, მოდით განაახლეთ ეს, მოდით დავუბრუნდეთ 865 00:39:13,100 --> 00:39:14,960 და bubble sort, და მხოლოდ ჩათვლით, 866 00:39:14,960 --> 00:39:17,330 მოდით ავირჩიოთ ჩასმა სახის, უბრალოდ კარგი ღონისძიება. 867 00:39:17,330 --> 00:39:20,020 და ამ დროს ისევ, მოდით აირჩიეთ შერწყმა დალაგების და მოდით 868 00:39:20,020 --> 00:39:21,595 რეალურად აწარმოებს ამ გვერდით. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> და ეს არ არის, ფაქტობრივად, fluke. 871 00:39:26,930 --> 00:39:31,140 რა მე ეფექტურად ვაკეთებ არის მე გაყოფილი ჩემი input ნახევარი, კიდევ ერთხელ, 872 00:39:31,140 --> 00:39:32,240 და ისევ და ისევ. 873 00:39:32,240 --> 00:39:35,590 და არსებობს მხოლოდ იმდენად ბევრი ჯერ თქვენ შეგიძლიათ გაყოფა თქვენი წვლილი halves, მარცხენა 874 00:39:35,590 --> 00:39:36,240 და მარჯვენა. 875 00:39:36,240 --> 00:39:39,425 რა არის ფორმულა, რომ ჩვენ ვხედავთ რომელიც ასახავს სამმართველოს ნახევარი 876 00:39:39,425 --> 00:39:41,050 ისევ და ისევ, და ისევ და ისევ? 877 00:39:41,050 --> 00:39:41,890 >> აუდიტორია: შესვლა n. 878 00:39:41,890 --> 00:39:42,760 >> დინამიკები შესვლა n. 879 00:39:42,760 --> 00:39:46,300 მაგრამ არსებობს ერთი სხვა საკვანძო ნაბიჯი, ეს ალგორითმი არ შეხვიდეთ N ნაბიჯები. 880 00:39:46,300 --> 00:39:48,992 თუ ეს იყო მხოლოდ შეხვიდეთ N ნაბიჯები, ჩვენ გვინდა, რომ იგივე პრობლემა 881 00:39:48,992 --> 00:39:51,200 როგორც ადრე, სადაც ჩვენ არ შეიძლება იყოს დარწმუნებული ვარ, ყველაფერი დალაგებულია. 882 00:39:51,200 --> 00:39:54,480 თქვენ უნდა მინიმალურად შევხედოთ n ელემენტებს დარწმუნებული უნდა იყოს n ელემენტები დალაგებულია, 883 00:39:54,480 --> 00:39:55,950 წინააღმდეგ შემთხვევაში, ეს ნახტომი რწმენის. 884 00:39:55,950 --> 00:39:59,810 >> ასე რომ, ეს მინიმალურად log n ნაბიჯები, მაგრამ რაც შეეხება ამ გასაღები შერწყმის ნაბიჯი 885 00:39:59,810 --> 00:40:04,370 სადაც გაერთიანდა ჩემი მარცხენა ნახევარში და მარჯვენა ნახევარი და გაიარა ეტაპი? 886 00:40:04,370 --> 00:40:06,980 რამდენი ნაბიჯების რომ შერწყმა? 887 00:40:06,980 --> 00:40:10,150 ის n, მაგრამ მე არა მხოლოდ შერწყმა საბოლოო დრო. 888 00:40:10,150 --> 00:40:15,089 თითოეულ ამ წყობილი ზარები, თითოეულ იმ წყობილი უერთდება, მე მაინც ინახება. 889 00:40:15,089 --> 00:40:18,380 გაერთიანდა ეს ორი ბიჭები, მაშინ ამ ორი ბიჭები, მაშინ ამ ორი ბიჭები და სხვ. 890 00:40:18,380 --> 00:40:19,955 >> ასე რომ, მე გაერთიანების ისევ და ისევ. 891 00:40:19,955 --> 00:40:20,580 რამდენჯერ? 892 00:40:20,580 --> 00:40:23,510 ასე რომ ყოველ ჯერზე მე გაყოფილი სია ნახევარ, მე შერწყმა. 893 00:40:23,510 --> 00:40:25,460 დაყოფის სია ნახევარ, ამის შერწყმა. 894 00:40:25,460 --> 00:40:28,570 ასე რომ, თუ გამყოფი სია შეიძლება გაკეთდეს შესვლა N ჯერ, 895 00:40:28,570 --> 00:40:33,880 და გაერთიანების საბოლოოდ იღებს n ნაბიჯები, რაც შეიძლება ახლა ზედა 896 00:40:33,880 --> 00:40:37,000 შეკრული გაშვებული დრო ჩვენი ალგორითმი? 897 00:40:37,000 --> 00:40:37,980 N შესვლა n. 898 00:40:37,980 --> 00:40:40,560 >> და მართლაც, ის, რაც მივაღწიეთ აქ. 899 00:40:40,560 --> 00:40:44,650 ასე გრძნობს, რომ ხედავთ ვიზუალურად როდესაც ეს სამი რამ აწარმოებს გვერდით 900 00:40:44,650 --> 00:40:47,930 n კვადრატში წინააღმდეგ n კვადრატი წინააღმდეგ N შესვლა n. 901 00:40:47,930 --> 00:40:51,010 ფუნდამენტურად ვნახავთ, არა მარტო დღეს, არამედ მომავალში, 902 00:40:51,010 --> 00:40:52,760 ბევრად, ბევრად უფრო სწრაფად. 903 00:40:52,760 --> 00:40:56,010 რაუნდი ტაში ამ ბიჭებს, მე დააჯილდოებს მათ სტრესი ბურთები. 904 00:40:56,010 --> 00:41:00,260 მოდით adjourn დღეს აქ, და ვნახავთ თქვენ ორშაბათს. 905 00:41:00,260 --> 00:41:02,255