1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [კვირა 3 გაგრძელდა]

2
00:00:02,280 --> 00:00:04,110
>> [დევიდ ჯ Malan - ჰარვარდის უნივერსიტეტი]

3
00:00:04,110 --> 00:00:07,130
>> [ეს არის CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> ყველა უფლება. კეთილი იყოს. ეს არის CS50 და ეს ბოლომდე კვირაში 3.

5
00:00:11,010 --> 00:00:14,680
>> ასე რომ იმ უცნობ, გასულ წელს ჰარვარდის დაიწყო რასაც ინოვაცია ლაბორატორია,

6
00:00:14,680 --> 00:00:18,530
ან I-ლაბორატორია, რომელიც მშვენიერი შენობის გასწვრივ მდინარე HBS-ს კამპუსში

7
00:00:18,530 --> 00:00:22,640
რომ ღიაა კოლეჯის სტუდენტები, GSAS სტუდენტები, სტუდენტები მასშტაბით კამპუსში,

8
00:00:22,640 --> 00:00:27,000
მათ შორის ფაკულტეტი, და ეს ადგილი უნდა გავერთიანდეთ, რომ მუშაობა ინოვაციური რამ,

9
00:00:27,000 --> 00:00:29,180
განსაკუთრებით სამეწარმეო რამ

10
00:00:29,180 --> 00:00:33,410
თუ თქვენ და 0 ან მეტი მეგობრები ფიქრობენ კეთების რაღაც სამეწარმეო

11
00:00:33,410 --> 00:00:37,080
ან ამ კლასის, შემდეგ ამ კლასში, ან მის ფარგლებს გარეთ.

12
00:00:37,080 --> 00:00:41,540
>> ასე რომ ერთი რამ ისინი მეტი J ვადა არის ამ მოგზაურობის დროს,

13
00:00:41,540 --> 00:00:44,510
რომელთაგან ერთი ნიუ იორკში, რომელთაგან ერთი უნდა სილიკონის ველის.

14
00:00:44,510 --> 00:00:47,530
ფართი არის ძალიან შეზღუდულია, მაგრამ ეს შესაძლებლობა RUB უნდა ერთად MBAs

15
00:00:47,530 --> 00:00:52,200
და ასპირანტების მასშტაბით კამპუსში და რეალურად დროის იმ შესაბამის სფეროებში

16
00:00:52,200 --> 00:00:55,500
chatting up startups, chatting up მეწარმეებს და ასე შემდეგ.

17
00:00:55,500 --> 00:00:57,870
ასე რომ, თუ დაინტერესებული, შეამოწმეთ ეს მისამართი აქ.

18
00:00:57,870 --> 00:01:01,220
ეს არის ასევე ხელმისაწვდომია სლაიდები ხაზზე.

19
00:01:01,220 --> 00:01:04,610
>> შეგვეძლო ტონი ქვემოთ სახლის აუდიო უბრალოდ ცოტა?

20
00:01:04,610 --> 00:01:08,640
თუ გსურთ შემოგვიერთდით ლანჩზე ამ პარასკევი, 1:15 საათზე ცეცხლი და ყინული, გთხოვთ უხელმძღვანელებს არსებობს.

21
00:01:08,640 --> 00:01:11,390
ბოდიშის თუ ფორმა უკვე შევსებული მიერ ახლა თქვენ იქ.

22
00:01:11,390 --> 00:01:13,750
მაგრამ ჩვენ გავაგრძელებთ ამ ტრადიციას Onward.

23
00:01:13,750 --> 00:01:17,350
>> დღეს ჩვენ გავაგრძელებთ მაღალ დონეზე განხილვას სხვადასხვა პრობლემები, რომელიც ჩვენ შეგვიძლია გადავჭრათ,

24
00:01:17,350 --> 00:01:21,330
ფოკუსის გაცილებით ნაკლებია, დღეს მინიმუმ, on კოდი და ბევრად უფრო იდეები.

25
00:01:21,330 --> 00:01:24,720
ასე მგონია თავში კვირაში 0, როდესაც ჩვენ დაწყვეტილია ტელეფონი წიგნი ნახევარი,

26
00:01:24,720 --> 00:01:28,260
ობიექტური იყო, რომ რამე, admittedly, ცოტა დრამატული

27
00:01:28,260 --> 00:01:32,360
მაგრამ გამოაგზავნოს წერტილი, რომ ძებნას არ უნდა იყოს, აუცილებლად,

28
00:01:32,360 --> 00:01:35,100
როგორც აშკარაა ერთი შეხედვით, როგორც თქვენ შესაძლოა იფიქროს.

29
00:01:35,100 --> 00:01:40,200
და პრობლემის გადაჭრის ზოგადად შეიძლება არ ემთხვეოდეს ყოველთვის იქნება საუკეთესო -

30
00:01:40,200 --> 00:01:44,130
ყველაზე ნათელი გამოსავალი შესაძლოა არ ემთხვეოდეს იყოს საუკეთესო.

31
00:01:44,130 --> 00:01:47,300
ამიტომ ჩვენ გვქონდა ამ სატელეფონო წიგნაკი და, სიმართლე გითხრათ, ყველა ჩვენგანისთვის ამ ოთახში ჰქონდა ინსტინქტებს,

32
00:01:47,300 --> 00:01:51,470
სავარაუდოდ, უნდა დაიწყოს შუა როდესაც ეძებს მაიკ სმიტი და მერე მარცხნივ და მარჯვნივ

33
00:01:51,470 --> 00:01:54,280
ეფუძნება რასაც წერილი ანბანი ჩვენ მოხდა მოხვდნენ შესახებ.

34
00:01:54,280 --> 00:01:57,560
>> მაგრამ ეს მარტივი იდეა, რომ ჩვენ ადამიანები აქვთ აღებული თავისთავად ამდენი ხანი

35
00:01:57,560 --> 00:02:00,670
ნამდვილად უნდა დავიწყოთ მისვლა forefront თქვენი გონება

36
00:02:00,670 --> 00:02:03,900
რადგან პრობლემები კიდევ უფრო მეტი კომპლექსი, ვიდრე სატელეფონო წიგნი,

37
00:02:03,900 --> 00:02:07,420
იმ იგივე მარტივი, ბრწყინვალე insights არიან რა ვაპირებთ საშუალებას მოგვცემს

38
00:02:07,420 --> 00:02:10,259
მოგვარებას ბევრად უფრო რთული და უფრო საინტერესო პრობლემებს,

39
00:02:10,259 --> 00:02:12,930
მათ შორის ზოგიერთი რამ თავისთავად უკვე ამ დღეებში.

40
00:02:12,930 --> 00:02:15,720
მილიარდობით ვებ გვერდები არსებობს, მაგრამ Google და Bing და მოსწონს

41
00:02:15,720 --> 00:02:17,660
შეუძლია იპოვოს რამ ჩვენთვის იგრძნობა.

42
00:02:17,660 --> 00:02:22,300
რომ არ ხდება გამოყენებით ხაზოვანი ძებნა, ჩხრეკის მეშვეობით ყველა შესაძლო ვებ გვერდები.

43
00:02:22,300 --> 00:02:25,290
Facebook შეუძლია გითხრათ, რომლებიც ყველა თქვენს მეგობრებს ან მეგობრებს მეგობრებს,

44
00:02:25,290 --> 00:02:28,250
და რომ ძალიან შეიძლება გაკეთდეს როგორც ჩანს წელს მყისიერი ამ დღეებში

45
00:02:28,250 --> 00:02:30,820
მიუხედავად იმისა, რომ მათ აქვთ მილიონობით მომხმარებლებს.

46
00:02:30,820 --> 00:02:34,250
>> და ასე თუ როგორ რეალურად პრობლემების შესახებ, რომ მასშტაბის საბოლოოდ შეამცირებს

47
00:02:34,250 --> 00:02:37,830
to იდეები ჩვენ შევხედეთ წელს კვირაში 0 და უფრო მეტი დღეს.

48
00:02:37,830 --> 00:02:42,320
ჩვენ არ ხელახლა შესრულდეს ეს ალგორითმი, მაგრამ გავიხსენოთ, რომ ჩვენ ასევე გააკეთა კვირაში 0 ამ exercise

49
00:02:42,320 --> 00:02:44,780
აქ ჩვენ ყველას აღუდგეს, იღებს ხმების 1,

50
00:02:44,780 --> 00:02:48,720
და მაშინ ჩვენ გვქონდა ყველას თვითმმართველობის რაოდენობა მიერ pairing off და დასძინა, თქვენი ნომრები ერთად,

51
00:02:48,720 --> 00:02:51,930
მაშინ ნახევარი ბანდა დაჯდა ყოველ iteration.

52
00:02:51,930 --> 00:02:56,750
ამიტომ წავედით 500 სტუდენტებს 250 დან 125 და სხვ.

53
00:02:56,750 --> 00:03:00,080
თუმცა, როგორც ჩვენ განაცხადა ორშაბათს, ძლიერი იდეა არსებობს

54
00:03:00,080 --> 00:03:02,460
ის იყო, რომ თუ ჩვენ გაორმაგდა ზომის რომ პრობლემა

55
00:03:02,460 --> 00:03:06,480
და ყველა ბავშვები იუსტიციის ან ევროკომისიის 10 დაბრუნდა ოთახში და შემოგვიერთდნენ,

56
00:03:06,480 --> 00:03:09,510
ასევე, შეიძლება ალბათ ითვლიან, რომ მთელი აგრეგატი ჯგუფი

57
00:03:09,510 --> 00:03:13,380
მხოლოდ 1 დიდი iteration of loop რადგან ისინი მხოლოდ იქნებ გაორმაგება ზომა

58
00:03:13,380 --> 00:03:15,630
ან ევროკომისიის 10 საქმე ცოტა ორჯერ მეტი ზომა.

59
00:03:15,630 --> 00:03:18,440
და ამიტომ ჩვენ უნდა დახარჯოს ცოტა მეტი დრო,

60
00:03:18,440 --> 00:03:22,000
მაგრამ ჩვენ არ უნდა დახარჯოს 400 ან 700 მეტი ნაბიჯები.

61
00:03:22,000 --> 00:03:26,550
>> უბრალოდ ხატვა ამ სურათს ისე, რომ ცოტა ნაკლები აბსტრაქტული, მოდით არ ყველას აღუდგეს.

62
00:03:26,550 --> 00:03:31,100
მაგრამ, თუ აღნიშნული, ვინც არჩია იჯდეს ორკესტრი დღეს არ იბადება იდგა up,

63
00:03:31,100 --> 00:03:34,580
მოდით ვნახოთ, თუ შევძლებთ გაერკვნენ შორის, ვინც ყველაზე მაღალ პირი

64
00:03:34,580 --> 00:03:36,730
ამით იმავე სახის შედარებითი ალგორითმი.

65
00:03:36,730 --> 00:03:41,830
ასე რომ, თუ თქვენ იჯდა ორკესტრი, ჩემი ბოდიში, მაგრამ ნაბიჯი 1, აღუდგეს;

66
00:03:41,830 --> 00:03:44,650
ნაბიჯი 2, წყვილი off არავისთან მიმდებარე თქვენ,

67
00:03:44,650 --> 00:03:49,360
გაერკვნენ, რომელიც გრძელია, და დასხდნენ თუ თქვენ მოკლე.

68
00:03:49,360 --> 00:03:51,360
მაშინ ვიმეორებ.

69
00:03:51,360 --> 00:03:56,280
[სტუდენტი murmuring]

70
00:04:13,450 --> 00:04:15,320
>> Okay.

71
00:04:15,320 --> 00:04:19,010
Okay. ერთი დარჩა იდგა. რა არის შენი სახელი? >> ენდრიუ.

72
00:04:19,010 --> 00:04:21,959
>> ანდრია, თქვენ ყველაზე მაღალი პირი ორკესტრი მონაკვეთზე დღეს.

73
00:04:21,959 --> 00:04:28,100
>> გილოცავთ. [ტაში და cheering] Okay. Have ადგილს. ამიტომ, ჩვენ ი ენდრიუ.

74
00:04:28,100 --> 00:04:30,870
მაგრამ რამდენ ხანს უნდა ჰქონოდა ჩემთვის, მაგალითად, იპოვოს ენდრიუ

75
00:04:30,870 --> 00:04:33,740
ამ ორკესტრმა მონაკვეთზე 50 + ან ხალხმა?

76
00:04:33,740 --> 00:04:36,900
მე შეეძლო აღებული საკმაოდ მარტივი მიდგომა და დაიწყება აქ.

77
00:04:36,900 --> 00:04:39,270
და მე 2 ადამიანი აღუდგეს და მე უბრალოდ შედარება,

78
00:04:39,270 --> 00:04:42,120
და მაშინ მე ვიტყვი, რომ ვინც ოდნავ მოკლე, "Okay, თქვენ დასხდნენ,"

79
00:04:42,120 --> 00:04:44,380
და მე ვაპირებ მახსოვს ვინ გრძელია პირი იყო.

80
00:04:44,380 --> 00:04:49,030
მაშინ ვიმეორებ, ვიმეორებ, ვიმეორებ, და მე გათიშეთ შესახებ, რომ ყველაზე მაღალი პირი

81
00:04:49,030 --> 00:04:51,920
სანამ მიწერ ოდნავ გრძელია, ვიდრე მათ, სადაც წერტილი

82
00:04:51,920 --> 00:04:54,950
ოდნავ მოკლეა ადამიანს აქვს შემდეგ დასხდნენ.

83
00:04:54,950 --> 00:04:57,690
მაგრამ რომ ალგორითმი ამ ორკესტრის მონაკვეთზე, თუ არსებობს N თქვენგანს,

84
00:04:57,690 --> 00:05:00,480
რამდენი ნაბიჯების რომ ალგორითმი აპირებს? >> [სტუდენტი] ნ

85
00:05:00,480 --> 00:05:03,580
>> ის აპირებს N, უფლება, რადგან უარეს შემთხვევაში, ასე ვთქვათ,

86
00:05:03,580 --> 00:05:09,090
ყველაზე მაღალი ადამიანი არის ძალიან ბოლო პირი, რომ მივიღო, რათა მხოლოდ შემთხვევითი ცუდი იღბალი.

87
00:05:09,090 --> 00:05:14,260
ასე რომ, უარეს შემთხვევაში, გაშვებული დრო, რომ ალგორითმი არის წრფივი, ეს N,

88
00:05:14,260 --> 00:05:18,070
სადაც n საერთო რაოდენობის ხალხი სივრცეში, ზომა პრობლემა.

89
00:05:18,070 --> 00:05:19,600
რაც შეეხება ამ ალგორითმი?

90
00:05:19,600 --> 00:05:22,080
ის, რომ თქვენ ყველა წამოდგა და ისევ ნახევარი თქვენ დაჯდა,

91
00:05:22,080 --> 00:05:23,950
ნახევარი თქვენ დაჯდა, ნახევარი თქვენ დაჯდა.

92
00:05:23,950 --> 00:05:26,070
რამდენი ნაბიჯები უნდა რომ აქვთ აღებული, თუ არსებობს N თქვენგანი აქ?

93
00:05:26,070 --> 00:05:30,200
[სტუდენტი] N შესვლა n. >> ეს იქნება უარესი. შესვლა n.

94
00:05:30,200 --> 00:05:32,930
>> ასე რომ შედით N, მაშინაც კი თუ თქვენ არ საკმაოდ გახსოვთ რა logarithm არის,

95
00:05:32,930 --> 00:05:38,410
ახლა, უბრალოდ ვაფასებ, რომ ეს ეხება რატომღაც ამ საჯელის განახევრებას და საჯელის განახევრებას და საჯელის განახევრებას.

96
00:05:38,410 --> 00:05:41,000
იგი არ უნდა იყოს ფაქტორი 2. ეს შეიძლება იყოს ფაქტორი 3.

97
00:05:41,000 --> 00:05:46,560
მაგრამ ამ გამეორებას მსგავსი ფაქტორი ისეთი, რომ ზომა პრობლემა აქ იწყება

98
00:05:46,560 --> 00:05:49,620
მაგრამ შემდეგ მაშინვე მიდის აქ, მაშინ აქ, მაშინ აქ, მაშინ აქ.

99
00:05:49,620 --> 00:05:53,580
თქვენ არ იღებენ პატარა ნაკბენები გარეთ პრობლემა, თქვენ ნამდვილად chopping away at it

100
00:05:53,580 --> 00:05:56,160
დიდი დაეცა swoop ყოველ ჯერზე.

101
00:05:56,160 --> 00:06:00,810
ამიტომ ჩვენ გვქონდა 50 ადამიანი, მაშინ 25, მაშინ 12 ½ ან 13 ადამიანი იდგა,

102
00:06:00,810 --> 00:06:05,370
მაშინ 6 ½ და ა.შ. სანამ საბოლოოდ მხოლოდ ენდრიუ დარჩა იდგა.

103
00:06:05,370 --> 00:06:08,710
ამიტომ, ჩვენ ვაპირებთ, რომ მოვუწოდებთ შესვლა of n, და თქვენ შეგიძლიათ ვიზუალიზაციისთვის ეს შემდეგნაირად.

104
00:06:08,710 --> 00:06:12,570
შეგახსენებთ, ამ სურათის აქ სადაც ხაზოვანი ალგორითმი ჰგავს წითელი ხაზი არსებობს,

105
00:06:12,570 --> 00:06:17,520
ყვითელი ხაზი იყო დათვლა მიერ 2S ალგორითმი რომ ჩვენ გამოიყენება დათვლის სტუდენტები

106
00:06:17,520 --> 00:06:22,300
წარსულში, მაგრამ დღეს წმიდა გრაალი აპირებს დარჩეს ამ მწვანე ზოლის

107
00:06:22,300 --> 00:06:25,470
აქ თუ ჩვენ გაორმაგდა რაოდენობის ხალხი ორკესტრი მონაკვეთზე ან უბრალოდ განაცხადა,

108
00:06:25,470 --> 00:06:29,170
ჯოჯოხეთი, მოდით ყველას მთელი ოთახი აღუდგეს, არ ასეთი დიდი გარიგება

109
00:06:29,170 --> 00:06:31,560
იმიტომ, რომ ჩვენ დაახლოებით გაორმაგდება რამდენი ადამიანი ქვემოთ აქ,

110
00:06:31,560 --> 00:06:33,500
1 მეტი iteration, პრობლემას არ წარმოადგენს.

111
00:06:33,500 --> 00:06:36,200
>> ჩვენ ნაპოვნი ენდრიუ ან ვინც ხდება იყოს გრძელია ვიდრე ენდრიუ

112
00:06:36,200 --> 00:06:38,770
წელს ანტრესოლით ან აივანი.

113
00:06:38,770 --> 00:06:42,140
ასე რომ, ეს მარტივი იდეა, რომ ავიღეთ იმდენად თავისთავად სატელეფონო წიგნი,

114
00:06:42,140 --> 00:06:46,170
გააცნობიეროს, რომ არსებობს ამდენი სხვადასხვა ადგილას, სადაც ჩვენ შეიძლება მიმართოს მას.

115
00:06:46,170 --> 00:06:50,810
მხოლოდ Slap გარკვეული jargon - რეალურად, ვიდრე jargon პირველი,

116
00:06:50,810 --> 00:06:52,750
ნება მომეცით წასვლა ამ სურათს აქ.

117
00:06:52,750 --> 00:06:56,970
ამ დროისათვის ჩვენ ვისაუბრეთ N და N / 2 და შემდეგ შედით of n,

118
00:06:56,970 --> 00:07:00,500
მაგრამ შეგვიძლია თქმა ამუშავება, როგორც ჩვენ მეტი კურსი სემესტრის

119
00:07:00,500 --> 00:07:05,130
სხვა სახის მათემატიკური ფორმულები აღწერს ამ ზოგადი ცნება ქრონომეტრაჟი.

120
00:07:05,130 --> 00:07:07,580
ეს არის გარეთ კონტექსტში, რადგან ჩვენ ვხედავთ, სანამ ხანგრძლივი

121
00:07:07,580 --> 00:07:09,900
ალგორითმები, რომ ეს რეალურად წარმოადგენენ.

122
00:07:09,900 --> 00:07:17,990
>> მაგრამ შეამჩნევს აქ ხაზოვანი ხაზი N, სწორი ხაზი, არის ძალიან დაბალი მიუთითებს ახლავე.

123
00:07:17,990 --> 00:07:22,950
სწორედ ერთგვარი ოპტიკური ილუზია, რომ ჩვენ უბრალოდ შეცვალეთ რა x ღერძი წარმოადგენს

124
00:07:22,950 --> 00:07:26,130
და Y ღერძი და ჩვენ შეგვიძლია სწორი ხაზის წერტილი ნებისმიერი მიმართულებით გვინდა.

125
00:07:26,130 --> 00:07:30,350
მაგრამ იმ მიზეზით, რომ ეს ასე ჩანს, ბინა არის

126
00:07:30,350 --> 00:07:35,690
არის იმიტომ რომ ჩვენ საჭიროა რათა ოთახში ამ გრაფაში ამისთვის ბევრად ნელი გაშვებული ჯერ.

127
00:07:35,690 --> 00:07:39,030
ახლა ვიცი, რომ არსებობს საკმაოდ ცუდი ალგორითმები ცხოვრებაში,

128
00:07:39,030 --> 00:07:43,790
რომელთაგან ზოგიერთი არ იღებს N ნაბიჯები, ან კიდევ უკეთესი, შეხვიდეთ N ნაბიჯები, მაგრამ კიდევ უფრო.

129
00:07:43,790 --> 00:07:48,820
ამიტომ ხაზს ზემოთ n აქ ბოლოში გაფრთხილების არსებობს N ჯერ შესვლა of n,

130
00:07:48,820 --> 00:07:51,410
და ვნახავთ, რას ნიშნავს ადრე ხანგრძლივი.

131
00:07:51,410 --> 00:07:56,010
ზემოთ რომ არის n კვადრატში, და ჩვენ არ მინახავს არც ერთი N კვადრატში ალგორითმები გაუკეთებია, მაგრამ ჩვენ შესახებ.

132
00:07:56,010 --> 00:07:57,660
და რომ გამოიყურება მართლა ცუდია.

133
00:07:57,660 --> 00:08:01,610
არსებობს 2 დან N, რაღაც exponential, რომელიც გრძნობს უარესი.

134
00:08:01,610 --> 00:08:05,760
და მაინც, საინტერესოა, მაშინ არსებობს N cubed, რომელიც თუ თქვენ ერთგვარი ფიქრი ადრე,

135
00:08:05,760 --> 00:08:10,000
თუ სახის გავაკეთოთ მათემატიკის, 2 დან N რეალურად ხდება ბევრად straighter,

136
00:08:10,000 --> 00:08:15,930
ბევრად უფრო მაღალია, ვიდრე up n cubed თუ გადავხედავთ ცულები შორს საკმარისი აღმოჩნდა.

137
00:08:15,930 --> 00:08:19,890
ასე რომ შეამჩნია ახლავე ამ ცულები არიან თვითნებურად 2 დან 10 წლის x ღერძი.

138
00:08:19,890 --> 00:08:21,770
>> და რას ნიშნავს ეს?

139
00:08:21,770 --> 00:08:23,890
ეს იმას ნიშნავს, 2 ადამიანს 10 ადამიანი ოთახში.

140
00:08:23,890 --> 00:08:27,200
სულ ეს x საშუალებები: ზომა პრობლემა, რაც კონტექსტში.

141
00:08:27,200 --> 00:08:30,420
და ვერტიკალური ღერძი ახლავე არის რიცხვი, ან მთელი რიგი ზომების -

142
00:08:30,420 --> 00:08:31,840
ზოგიერთი ერთეულის დრო.

143
00:08:31,840 --> 00:08:34,740
მაგრამ შეამჩნია, რომ 0 დან 60 და 0 დან 10.

144
00:08:34,740 --> 00:08:38,549
მაგრამ თუ ჩვენ სახის დააშორებს, როგორც თქვენ შეიძლება Excel-ან დიაგრამების აწყობა პროგრამული უზრუნველყოფა,

145
00:08:38,549 --> 00:08:43,370
და ჩვენ ახვიდეთ 200,000 შეამჩნევთ, რომ რაღაც 2 დან N

146
00:08:43,370 --> 00:08:47,520
აპირებს მთლიანად overwhelm გაშვებული ჯერ N კვადრატში,

147
00:08:47,520 --> 00:08:50,960
N cubed, N შესვლა N - ყველაფერი ჩვენ ვისაუბრეთ დღემდე.

148
00:08:50,960 --> 00:08:54,190
და მაინც დაჭერა არის, როდესაც თქვენ დავიწყოთ ლაპარაკი რამ, როგორიცაა Facebook

149
00:08:54,190 --> 00:08:57,150
სადაც თქვენ ბევრი, ბევრი, ძალიან ბევრი ადამიანი ყველა ურთიერთდაკავშირებული,

150
00:08:57,150 --> 00:09:00,650
თქვენ არ n ადამიანი, თითოეული მათგანი შეიძლება იმდენი როგორც n მეგობრები

151
00:09:00,650 --> 00:09:02,860
თუ ყველას სახის buddy-buddy მსოფლიოში,

152
00:09:02,860 --> 00:09:08,100
კარგად, რომ N ჯერ N უკვე, ასე რომ n კვადრატში შესაძლო მეგობრობას,

153
00:09:08,100 --> 00:09:10,950
ყოველ შემთხვევაში 1 მიმართულებით, N კვადრატში შესაძლო მეგობრობას.

154
00:09:10,950 --> 00:09:15,330
ასე რომ უკვე ვარაუდობს, რომ ჩხრეკის Facebook სოციალური გრაფაში, ასე ვთქვათ,

155
00:09:15,330 --> 00:09:18,090
შეგიძლიათ დაიწყოთ უნდა გამოიხატოს ასეთი ფორმულები.

156
00:09:18,090 --> 00:09:19,820
>> ჩვენ დავბრუნდებით და ამ ბევრად უფრო კონკრეტული,

157
00:09:19,820 --> 00:09:23,280
მაგრამ ახლა, ობიექტური მომდევნო მრავალი კვირის განმავლობაში

158
00:09:23,280 --> 00:09:27,170
იქნება დარწმუნებული არ წასულიყო შესახებ ახორციელებს ალგორითმები ან კოდი

159
00:09:27,170 --> 00:09:29,870
რომ დასრულდება მდე მიღების როგორც ბევრი დრო როგორც რაღაც მოსწონს ეს.

160
00:09:29,870 --> 00:09:33,110
მაგრამ მომხიბლავი ის კომპიუტერულ მეცნიერებათა თუ გაგრძელდება ამ სფეროში

161
00:09:33,110 --> 00:09:38,320
აღების კლასების მოსწონს CS121, CS124, ორივე მათგანი თეორიის კურსები,

162
00:09:38,320 --> 00:09:41,300
ის არის, რომ არსებობს გარკვეული პრობლემები, რომელიც არსებობს ამ სამყაროში

163
00:09:41,300 --> 00:09:45,710
რომ ფუნდამენტურად, რამდენადაც ჩვენ ვიცით, არ შეიძლება გადაწყდეს რაიმე უფრო სწრაფად

164
00:09:45,710 --> 00:09:48,880
ვიდრე უარესი ამ გრაფიკების ფაქტობრივად გვთავაზობს.

165
00:09:48,880 --> 00:09:53,660
ამიტომ იქ ბევრი ღია პრობლემები ამ სამყაროში ბევრი რამ უკეთესად ადამიანები გვყავს ჯერჯერობით.

166
00:09:53,660 --> 00:09:56,130
>> მოდით ახლა გადავიდეთ შემდეგ ეს მაგალითი.

167
00:09:56,130 --> 00:09:59,650
ჩვენ ვნახეთ შონ ბრძოლაში ეს კამერა, ძალიან უხერხულად on video.

168
00:09:59,650 --> 00:10:05,270
მაგრამ რეალობა იყო, როცა შონ დაევალა მოძიებაში on მონიშნე მოსწონს ეს ნომერი 7,

169
00:10:05,270 --> 00:10:10,300
გავიხსენოთ, რომ მე ვთქვი, რომ "არსებობს სადღაც მიღმა ამ ცალი ქაღალდის ან თეთრი კარები

170
00:10:10,300 --> 00:10:12,570
"ნომერი 7. შონ, ის ჩვენთვის."

171
00:10:12,570 --> 00:10:14,200
და ეს იყო შესანიშნავად უხერხულია უყუროთ

172
00:10:14,200 --> 00:10:15,790
რადგან იგი მართლაც ბრძოლა ამ პრობლემის.

173
00:10:15,790 --> 00:10:19,720
მაგრამ რეალობა იყო შონ გააკეთა ასევე ვინმეს ოთახში შეეძლო.

174
00:10:19,720 --> 00:10:21,890
მან პატარა აღარ, ვიდრე ტიპიური პირი შესაძლოა,

175
00:10:21,890 --> 00:10:24,760
მაგრამ ის ვარაუდი, რომ გარკვეული შეასრულა ამ პრობლემას,

176
00:10:24,760 --> 00:10:26,590
მან აიღო, რომ მას აკლია რაღაც.

177
00:10:26,590 --> 00:10:29,320
და ეს არ დაეხმარება, რომ ასობით თვალები ნოტარიულად down on მას.

178
00:10:29,320 --> 00:10:34,250
>> მაგრამ რეალობა იყო თუ შეყვანის რომ პრობლემა არის bunch of შემთხვევითი ნომრები

179
00:10:34,250 --> 00:10:37,120
და თქვენ მიმდინარეობს სთხოვა მოძიების 1 ასეთი ნომერი,

180
00:10:37,120 --> 00:10:39,770
საუკეთესო შეგიძლიათ გააკეთოთ ხაზოვანი ძებნა.

181
00:10:39,770 --> 00:10:44,060
დაწყება at მარცხენა გადატანა უფლება, ან დაიწყება უფლება გადატანა მარცხენა.

182
00:10:44,060 --> 00:10:48,300
Retroactively, ჩვენ შეიძლება ფიქრი ", შონ, რატომ არ დავიწყო მეორე ბოლოს?"

183
00:10:48,300 --> 00:10:52,120
ისე, 7 შეეძლო ასევე ადვილად აქ შემთხვევით,

184
00:10:52,120 --> 00:10:54,980
მაგრამ მე შეგნებულად თქვა იქ რადგან I figured ის არ აპირებს დაიწყოს დასასრულს.

185
00:10:54,980 --> 00:10:59,320
ასე, რომ სახის მანიპულირება სიტუაცია, არამედ შემთხვევითი შანსი 7 შეიძლებოდა ყოფილიყო სადმე.

186
00:10:59,320 --> 00:11:02,380
ასე დაწყებული უფლება ბოლომდე შეიძლება უკეთესია,

187
00:11:02,380 --> 00:11:04,320
მაგრამ რა, თუ მომავალ წელს მე გადაადგილება 7 სხვაგან?

188
00:11:04,320 --> 00:11:06,830
ეს არ არის ფუნდამენტურად ახალი გადაწყვეტა პრობლემა -

189
00:11:06,830 --> 00:11:10,520
დაწყებული 1 ბოლოს ან სხვა - როდესაც თქვენ და საერთოდ არ სხვა ვარაუდები.

190
00:11:10,520 --> 00:11:13,620
ასე შონ დაიწყო გადახედეთ ნომრები და განაცხადა მან, "5. ეს არ აქ."

191
00:11:13,620 --> 00:11:17,280
შემდეგ იგი წავიდა აქ და ვნახე 19, მაშინ ის ათვისება დაახლოებით 20 წამი,

192
00:11:17,280 --> 00:11:22,330
შემდეგ მან გახსნა ეს 13, და შემდეგ ნათელი გახდა

193
00:11:22,330 --> 00:11:24,270
რომ იქ არ ჩანს, ეს ნიმუში აქ.

194
00:11:24,270 --> 00:11:28,090
ეს არ იყო 1, 2, 3, 4 ან ანალოგიური. იყო ხარვეზები ციფრები, რომლებიც არ უშველა.

195
00:11:28,090 --> 00:11:32,320
და ძალიან, ის ფაქტი, რომ მე გამოიყენება ამ იაფი ცალი ქაღალდის რათა დაფაროს ნომრები

196
00:11:32,320 --> 00:11:35,270
ფაქტიურად მიზანმიმართული, რადგან თუ მე ამოღებულ ყველა ამ ცალი ქაღალდის,

197
00:11:35,270 --> 00:11:38,760
ყველაზე მეტად ჩვენს შონ შედის, ალბათ არ მოხვდა სახის macroscopically

198
00:11:38,760 --> 00:11:43,410
ზე დაფაზე და თქვა: "ოჰ, 7 აშკარად უფლება არსებობს." ჩვენ ეს გავაკეთეთ მყისიერად.

199
00:11:43,410 --> 00:11:46,460
>> და რომ შეიძლება იყოს გზა ადამიანის ტვინი მუშაობს გარკვეულწილად,

200
00:11:46,460 --> 00:11:50,730
მაგრამ სინამდვილეში, მისი თვალების ან გონება ალბათ skimming ნომრები მარჯვნიდან მარცხნივ,

201
00:11:50,730 --> 00:11:55,190
მარცხნიდან მარჯვნივ, შუაში ჩვენს - რაღაც ხდებოდა ფიზიოლოგიურად

202
00:11:55,190 --> 00:11:57,640
ასეთი, რომ იგრძნო, როგორც ეს ხდებოდა მყისიერად,

203
00:11:57,640 --> 00:12:01,360
მაგრამ შანსები კიდევ იძულებით იყო გარკვეული მეთოდის მოძიებაში 7.

204
00:12:01,360 --> 00:12:05,160
მართლაც, ახლა რომ ჩვენ ვსაუბრობთ კოლექტორები და მონაცემთა სტრუქტურები

205
00:12:05,160 --> 00:12:08,780
და მეხსიერების შიგნით კომპიუტერი, ერთადერთი, რაც ჩვენ ადამიანები შეგვიძლია გავაკეთოთ

206
00:12:08,780 --> 00:12:13,070
არის შევხედოთ ინდივიდუალური მეხსიერების ადგილებში 1 დროს.

207
00:12:13,070 --> 00:12:16,600
>> ასე რომ, ყველა სხვა საიდან შეიძლება ასევე იყოს დაფარული რაიმე ნაჭერი ქაღალდი

208
00:12:16,600 --> 00:12:21,170
იმიტომ, რომ ჩვენ ვერ ვხედავთ მაინც. ჩვენ შეგვიძლია მხოლოდ 1 რამ დროს.

209
00:12:21,170 --> 00:12:25,030
ასე რომ ამ შემთხვევაში, შონ საქმე, წავედით აქ და მერე წავედით აქ

210
00:12:25,030 --> 00:12:31,040
და მერე წავედით აქ, აქ, აქ, აქ, მიიღო ჭკვიანი ბოლოსთვის

211
00:12:31,040 --> 00:12:34,450
და მხოლოდ სახის გამოტოვებენ ამ ერთი თვითნებურად და ნაპოვნია 7 არსებობს.

212
00:12:34,450 --> 00:12:37,470
ეს ერთი არ იყო განსაკუთრებით სპეციალური. ეს ძალიან იყო მწყობრიდან.

213
00:12:37,470 --> 00:12:39,530
მაგრამ მან საბოლოოდ ნაპოვნია 7.

214
00:12:39,530 --> 00:12:45,360
მაგრამ ახლა takeaway მართლაც რომ საუკეთესო შეგიძლიათ გააკეთოთ, როდესაც მოცემული ინფორმაცია არ არის

215
00:12:45,360 --> 00:12:50,400
გარდა შემთხვევით დახარისხებული ციფრები უნდა დაიწყოს მარცხნიდან ან დაიწყება უფლება.

216
00:12:50,400 --> 00:12:54,950
ან heck, შეგიძლიათ შემთხვევით გახსენით კარები, მაგრამ მაშინაც რას ნიშნავს უნდა იყოს შემთხვევითი?

217
00:12:54,950 --> 00:12:57,220
ისე, ჩვენ გვინდა უნდა როგორღაც formalize რას ნიშნავს დაიწყოს აქ,

218
00:12:57,220 --> 00:13:01,150
მერე აქ, მერე აქ. შონ გააკეთეს დიდი, და ეს მხოლოდ გართობა უყუროთ.

219
00:13:01,150 --> 00:13:06,340
რა მოხდება, თუ ნაცვლად შევცვლით პრობლემა ცოტა და ზრდიან ამ წლის შონ, თუ გნებავთ?

220
00:13:06,340 --> 00:13:09,460
რომ ვინმე იყოს კომფორტული ახლოვდება სცენაზე და გადაჭრის ოდნავ განსხვავებული პრობლემა

221
00:13:09,460 --> 00:13:12,330
და გამოჩენა კამერა?

222
00:13:12,330 --> 00:13:15,720
>> მოდით სცილდება ორკესტრი იმიტომ, რომ თქვენ ბიჭები უკვე საკმაოდ ჩართული დღეს უკვე.

223
00:13:15,720 --> 00:13:21,430
როგორ შესახებ წელს ვარდისფერი, წელს ქუდი? Come on ქვემოთ. რა არის შენი სახელი? >> ალექსი. >> ალექსი. Okay.

224
00:13:21,430 --> 00:13:24,580
ასე რომ ალექს იქნება ამ წლის შონ და გამოჩნდება შემდეგი რამდენიმე წლის

225
00:13:24,580 --> 00:13:27,770
ღირებულების CS50 ლექციებს.

226
00:13:27,770 --> 00:13:30,340
ალექს, კარგია თქვენთან შეხვედრა. >> Nice შეხვდება თქვენც.

227
00:13:30,340 --> 00:13:33,470
გამოწვევა ხელთ თქვენთვის არის, რომ თქვენ გაქვთ ცოტა ადვილი

228
00:13:33,470 --> 00:13:38,950
ამ მე გეუბნებოდით იგივე ციფრები აქ, მაგრამ ისინი ახლა დახარისხებული.

229
00:13:38,950 --> 00:13:41,800
ახლა თქვენი მიზანია ვიპოვოთ ნომერი 7.

230
00:13:41,800 --> 00:13:45,370
და ფაქტობრივად, ჩვენ უნდა ნამდვილად რომ ეს - you're სახის მოტყუების, როგორიცაა კომპიუტერი არა,

231
00:13:45,370 --> 00:13:47,990
მიერ ეძებს რა ციფრები იყო მომენტი წინ.

232
00:13:47,990 --> 00:13:50,360
With ცარცის ამ რეალურად არ აპირებს დაეხმაროს ყველა რომ ბევრი რამ,

233
00:13:50,360 --> 00:13:52,810
მაგრამ მოდით ვიტყვი, რომ თქვენ არ იცით, რა ორიგინალური წყობა.

234
00:13:52,810 --> 00:13:56,600
ყველა თქვენ იცით ახლა ის არის, რომ თქვენ გაქვთ მასივი დახარისხებული ნომრები

235
00:13:56,600 --> 00:14:00,360
რომ შესაძლოა ხარვეზები, მათ შორის, და თქვენი მიზანია ვიპოვოთ ნომერი 7.

236
00:14:00,360 --> 00:14:05,080
რა, გონივრული ადამიანის, წასვლა დაახლოებით მოძიებაში ნომერი 7?

237
00:14:05,080 --> 00:14:07,770
>> გადასვლა დაბლიდან მაღალი? >> Okay. გადავიდეთ დაბალი მაღალი.

238
00:14:07,770 --> 00:14:10,990
და არ გაანადგურეს ისინი. მოდით უბრალოდ გააუქმოს ისინი ასე შეგვიძლია reuse მათ.

239
00:14:10,990 --> 00:14:14,730
Okay, ასე 1. დაელოდეთ. სანამ შენარჩუნებას აპირებს, რომ იყო 1, აშკარად არასწორია.

240
00:14:14,730 --> 00:14:17,270
ასე რომ, რა ხდება საშუალებით თქვენი გონება შემდეგი? რა არის თქვენი მომავალი ნაბიჯი?

241
00:14:17,270 --> 00:14:23,250
შემდეგი ერთი. >> Okay. შემდეგი ერთი. კარგი. 3, ასე რომ არასწორია. რა არის თქვენი მომავალი ნაბიჯი?

242
00:14:23,250 --> 00:14:27,670
შეინახეთ მიმდინარე. >> ყველა უფლება. შეინახეთ მიმდინარე. 5.

243
00:14:27,670 --> 00:14:31,110
გააგრძელეთ მიმდინარე და ნება მომეცით გადასცემს თქვენ ამ შთამომავლობას.

244
00:14:31,110 --> 00:14:35,720
7. >> შესანიშნავი. ძალიან კარგი. ნაპოვნია ნომერი 7. [ტაში]

245
00:14:35,720 --> 00:14:39,720
ასე რომ კარგი იყო, მაგრამ შონ ძალიან ი ნომერზე 7.

246
00:14:39,720 --> 00:14:44,490
მე ამტკიცებენ, რომ თქვენ არ ნამდვილად ისარგებლა ამ დამატებითი ნაჭერი ინფორმაციას,

247
00:14:44,490 --> 00:14:47,780
რაც არის, რომ ეს ციფრები დახარისხებული.

248
00:14:47,780 --> 00:14:51,520
ასე გავაკეთოთ უკეთესი? რაიმე შემოთავაზება აქ? ჰო, წელს უკან.

249
00:14:51,520 --> 00:14:54,710
[სტუდენტი] ორობითი ძებნა. >> არ ვიცი რა ორობითი ძებნის.

250
00:14:54,710 --> 00:14:58,030
>> [სტუდენტი] დაწყება შუა. >> დაწყება შუა. Okay. მოდით ვნახოთ, თუ შევძლებთ იქ.

251
00:14:58,030 --> 00:15:02,580
ასე რომ, თუ ნაცვლად თქვენ განუცხადა იწყება შუა, წავიდეთ წინ და ქმნის შუა კარი.

252
00:15:02,580 --> 00:15:04,580
არსებობს 8 მათგანი, ასე რომ თქვენ აპირებთ უნდა თვითნებურად აირჩიოს ერთი

253
00:15:04,580 --> 00:15:09,800
ოდნავ მარცხნივ ან მარჯვნივ. Okay. 7! [ტაში] ძალიან ლამაზი.

254
00:15:09,800 --> 00:15:11,410
Okay, მაგრამ სადაც ჩვენ ვაპირებთ ამ?

255
00:15:11,410 --> 00:15:14,990
დავუშვათ უბრალოდ შესვენება ჰალსტუხი თქვენ დაიწყო აქ

256
00:15:14,990 --> 00:15:16,670
იმიტომ, რომ თანაბრად შეიძლება მომხდარიყო, ისევე.

257
00:15:16,670 --> 00:15:19,540
ჩვენ უბრალოდ მოხდა ვიცით, რომ 7 იყო. ასე რომ, ეს არის 13.

258
00:15:19,540 --> 00:15:21,980
ასე რომ, თუ ისინი დახარისხებული და ჩვენ უბრალოდ დაიწყო ახლო,

259
00:15:21,980 --> 00:15:24,600
რა ოპტიმალური შემდეგი ნაბიჯი უკვე?

260
00:15:24,600 --> 00:15:27,740
ზემოთ მარცხენა. და ა.შ. აქ მოდის სატელეფონო წიგნი მაგალითად ერთხელ.

261
00:15:27,740 --> 00:15:30,130
თუ 13 აქ არის და ჩვენ ვიცით სია დალაგებულია,

262
00:15:30,130 --> 00:15:33,900
მაშინ ყველა ამ ცალი ქაღალდის არიან uninteresting ჩვენთვის არის

263
00:15:33,900 --> 00:15:37,400
იმიტომ, რომ ჩვენ უკვე ვიცით, რომ 7 უნდა იყოს მარცხენა

264
00:15:37,400 --> 00:15:39,510
თუ ეს ციფრები დახარისხებული და აღმოვაჩინეთ 13.

265
00:15:39,510 --> 00:15:42,500
>> რა არის თქვენი შემდეგი ნაბიჯი აქ? >> გადადი მარცხენა. >> Okay, კარგი.

266
00:15:42,500 --> 00:15:45,080
ასე მარცხნივ, და - დაველოდოთ, Hey, Hey, Hey. რომ პატაშური.

267
00:15:47,140 --> 00:15:51,350
ასე რომ თქვენ ი 7, მაგრამ რა იყო ალგორითმი ჩვენ უბრალოდ გამოიყენება?

268
00:15:51,350 --> 00:15:56,450
დაწყება შუა. >> კარგი. რა არის ლოგიკური გაგრძელების იმავე იდეას?

269
00:15:56,450 --> 00:15:58,970
ოჰ, მხოლოდ ამ. >> ზუსტად. >> ასე რომ დავიწყოთ აქ. >> კარგი.

270
00:15:58,970 --> 00:16:02,020
ახლა წავედით ოდნავ მარცხნივ ისევ. ეს 3.

271
00:16:02,020 --> 00:16:05,310
მაგრამ საინტერესო takeaway ახლა არის რაც ერთი თუ არ აინტერესებს?

272
00:16:05,310 --> 00:16:08,040
ეს 2. >> ეს 2. ახლა ამ ადამიანს შეუძლია წავიდეს, ეს შეიძლება წავიდეს.

273
00:16:08,040 --> 00:16:12,330
არის პრობლემა, რომელიც იყო 8 მაშინ იყო ზომა 4 ახლა არის ზომა 2.

274
00:16:12,330 --> 00:16:16,430
ჩვენ ვიღებთ საკმაოდ ახლოს. ერთხელ, წასვლა შუა ამ 2 ელემენტებს.

275
00:16:16,430 --> 00:16:20,430
>> Okay. ასე რომ სახის სამწუხაროა, რომ ახლა ჩვენ მუდმივად მიმდინარეობდა დაუტოვებიათ რადგან ჩვენ დამრგვალება ქვემოთ.

276
00:16:20,430 --> 00:16:25,150
მაგრამ ეს ჯარიმა, რადგან ახლა ჩვენ გადაყარეთ ამ მოშორებით და ყველაფერი, რის გამოც ჩვენთვის მხოლოდ 7.

277
00:16:25,150 --> 00:16:30,490
მოდით მივცეთ რაუნდი ტაში. ჩვენ ვნახეთ 7 ერთხელ. [ტაში] Okay. დარწმუნებული.

278
00:16:30,490 --> 00:16:32,220
Hang on მხოლოდ 1 მეტი მეორე.

279
00:16:32,220 --> 00:16:36,630
მიუხედავად იმისა, რომ შემდეგი პროცესი სახის აიღო პატარა აღარ, ვიდრე ჩვენ გრძნობდა ხოლმე,

280
00:16:36,630 --> 00:16:40,150
გულწრფელად, თქვენი პირველი ინსტინქტები იყო საუკეთესო, არა? ჩვენ ვნახეთ 7 მომენტალურად.

281
00:16:40,150 --> 00:16:46,740
მაგრამ ჩვენ რომ არ ი 7 უფრო სწრაფად, არ აქვს მნიშვნელობა, რა, ამ მაგალითში წინააღმდეგ ამ ერთი

282
00:16:46,740 --> 00:16:50,100
რადგან თუ ციფრები ყველა დახარისხებული, ჰგავს გვერდების სატელეფონო წიგნი,

283
00:16:50,100 --> 00:16:54,580
შეგიძლიათ მართლაც Chop ნახევარში პრობლემა ისევ და ისევ და ისევ.

284
00:16:54,580 --> 00:16:56,740
და ეს არ არის საკმაოდ მარტივი, რომ ეს მხოლოდ 8 ნომრები

285
00:16:56,740 --> 00:17:00,100
როგორც ეწინააღმდეგებოდა 1000 გვერდი სატელეფონო წიგნი, სადაც თქვენ ნამდვილად ჩანს ვიზუალურად,

286
00:17:00,100 --> 00:17:03,120
მაგრამ ამ შემთხვევაში აქ როცა შონ იყო ეძებს 7,

287
00:17:03,120 --> 00:17:06,020
რამდენი ნაბიჯები უარეს შემთხვევაში უნდა ჰქონოდა მას? >> [სტუდენტი] 7.

288
00:17:06,020 --> 00:17:11,670
7 ყველაზე ცუდ შემთხვევაში. ისე, ყველაზე ცუდ შემთხვევაში არ 7 თუ არა 8 კარი აქ.

289
00:17:11,670 --> 00:17:13,440
ეს იქნებოდა მიღებული მისთვის 8 ნაბიჯები.

290
00:17:13,440 --> 00:17:18,170
>> ასე რომ, თუ არსებობს N კარები, მას ჰქონოდა შონ რამდენიმე წლის წინ N ნაბიჯები.

291
00:17:18,170 --> 00:17:21,520
ახლა კი, თქვენი საქმის, ალექსი, თუ გავითვალისწინებთ, რომ ეს ციფრები დალაგებულია -

292
00:17:21,520 --> 00:17:25,130
და ჩვენ შეგვიძლია სახის infer ამ საიდანაც ჩვენ დღემდე ამ სიუჟეტი -

293
00:17:25,130 --> 00:17:28,300
რა ქრონომეტრაჟი ალექს ბევრად უფრო ინტელექტუალური ალგორითმი

294
00:17:28,300 --> 00:17:30,770
დაწყების შუა და შემდეგ იმეორებს?

295
00:17:30,770 --> 00:17:36,490
[სტუდენტი] 3. >> ამიტომ იქნება 3, უხეშად, თუ თქვენ გადასვლა 8 დან 4 დან 2 მდე 1.

296
00:17:36,490 --> 00:17:40,660
ასე 3 ნაბიჯები ან, უფრო ზოგადად, რომ შესვლა n ერთხელ.

297
00:17:40,660 --> 00:17:43,380
ნებისმიერ დროს თქვენ საჯელის განახევრებას და საჯელის განახევრებას და საჯელის განახევრებას და საჯელის განახევრებას,

298
00:17:43,380 --> 00:17:45,290
რომ გამოხატვის ამ იდეას შესვლა n.

299
00:17:45,290 --> 00:17:48,140
და ასე რომ აქვთ აღებული თქვენ მხოლოდ 3 ნაბიჯებს, და მართლაც ასე იყოს

300
00:17:48,140 --> 00:17:50,890
ერთხელ გავხსენით კარები საჯელის განახევრებას და საჯელის განახევრებას,

301
00:17:50,890 --> 00:17:53,770
ხოლო ამ იქნებოდა მიღებული შონ დაახლოებით 7 ან 8 ნაბიჯები.

302
00:17:53,770 --> 00:17:56,330
მადლობას მოგახსენებთ იმისთვის, რომ ჩვენთან ამ წელიწადში. >> გმადლობთ. Nice შეხვედრა თქვენ.

303
00:17:56,330 --> 00:18:00,170
გმადლობთ, რომ ალექსი. >> ანალოგიურად. [ტაში]

304
00:18:00,170 --> 00:18:02,150
>> რა არის მაშინ რეალური გავლენა ამ?

305
00:18:02,150 --> 00:18:06,050
ახლა წარმოიდგინეთ, რომ ის 8 კარი, რომელიც, სიმართლე გითხრათ, ყველა ჩვენგანის იპოვა რაღაც

306
00:18:06,050 --> 00:18:10,430
უკან 8 კარები საკმაოდ სწრაფად მხოლოდ tearing ცალი ქაღალდის და ვაპირებთ ჩვენს ინსტინქტებს.

307
00:18:10,430 --> 00:18:14,430
მაგრამ მერე რა, რომ მილიონი კარები? მერე რა, რომ 4 მილიარდი კარები?

308
00:18:14,430 --> 00:18:19,630
იმ შემთხვევაში, თუ 4 მილიარდი კარები, თქვენ მართლაც აპირებს მინდა დავუკავშირდეთ Alex-ს ალგორითმი,

309
00:18:19,630 --> 00:18:23,150
ორობითი ძებნა როგორც დავიწყებთ უწოდა ან გათიშე და დაიპყროთ, ზოგადად,

310
00:18:23,150 --> 00:18:25,220
აქ თქვენ გაქვთ საჯელის განახევრებას და საჯელის განახევრებას პრობლემა,

311
00:18:25,220 --> 00:18:30,510
რადგან თუ თქვენ გაქვთ 4 მილიარდი კარები, რამდენჯერ შეგიძლიათ Chop 4 მილიარდი ნახევარი?

312
00:18:30,510 --> 00:18:33,870
[სტუდენტი] 32. >> სინამდვილეში 32. თქვენ შეგიძლიათ იმუშაოთ ამ წლის ნაჭერი ქაღალდი ან თქვენს უფროსს.

313
00:18:33,870 --> 00:18:38,490
თქვენ გადასვლა 4 მილიარდი 2 მილიარდი 1 მილიარდი ნახევარი მილიარდი, რომ 250 მილიონი აშშ დოლარი, dot, dot, dot.

314
00:18:38,490 --> 00:18:41,620
და თუ გარეთ მათემატიკის, თქვენ აპირებს მართლაც მიიღოს 32,

315
00:18:41,620 --> 00:18:44,950
და რომ რეალურად ეხება კომპიუტერული მეცნიერებისა რადგან ჩვენ, როგორც წესი, დათვლის უფლებამოსილება 2.

316
00:18:44,950 --> 00:18:47,600
2 დან 32 ხდება იქნება 4 მილიარდი.

317
00:18:47,600 --> 00:18:51,440
ასე რომ არსებობს ბევრი შესაბამისობა ამ სახის უფლებამოსილება 2 კომპიუტერულ მეცნიერებაში.

318
00:18:51,440 --> 00:18:55,120
>> მაგრამ რა დაახლოებით 8 მილიარდი? რამდენი ნაბიჯების რომ აპირებს თუ არსებობს 8 მილიარდ კარები?

319
00:18:55,120 --> 00:19:00,350
[სტუდენტი] 33. >> ასე 33. რა მოხდება თუ არსებობს 16 მილიარდი კარები? რამდენი ნაბიჯების რომ აპირებს?

320
00:19:00,350 --> 00:19:05,020
[სტუდენტი] 34. >> 34. ჩვენ შეგვეძლო სახის გაგრძელდება განცხადებაზე nauseam. მაგრამ ამით ძლიერი რამ.

321
00:19:05,020 --> 00:19:09,430
შეგიძლიათ გააცნობს მილიარდობით უფრო საშუალებებით თქვენს პრობლემა, მაგრამ, არ დიდი გარიგება,

322
00:19:09,430 --> 00:19:14,140
უბრალოდ მიიღოს 1 დამატებითი bite გარეთ და ამით გვაძლევს რაღაც ორობითი ძებნა

323
00:19:14,140 --> 00:19:15,920
ან გათიშე და დაიპყროთ, უფრო ზოგადად.

324
00:19:15,920 --> 00:19:17,990
მაგრამ მე სახის პატაშური აქ, არა?

325
00:19:17,990 --> 00:19:22,410
იმ შემთხვევაში, ალექს ს ალგორითმი, მას უპირატესობა შონ.

326
00:19:22,410 --> 00:19:27,780
მან იცოდა, რომ ეს ციფრები იყო დახარისხებული, მაგრამ ალექს არ უნდა დასალაგებლად მათ თავად.

327
00:19:27,780 --> 00:19:30,520
მე წინასწარ მოვიდა დაფაზე და სახის გააკეთა დარწმუნებული

328
00:19:30,520 --> 00:19:33,670
რომ მე მიიპყრო მათ ყველა გარეთ დახარისხებული მიზნით, მაშინ მე დაფარული მათ ქაღალდზე.

329
00:19:33,670 --> 00:19:35,850
თუმცა, რამდენად მუშაობა საერთოდ რომ Take Me?

330
00:19:35,850 --> 00:19:40,110
თუ ჩვენ დაიწყო off ერთად ამ ნომრებზე ზოგიერთ შეხედვით შემთხვევითი მიზნით -

331
00:19:40,110 --> 00:19:43,320
ამ შემთხვევაში ეს უფრო მარტივი რიცხვები, 1 მეშვეობით 8 აქ -

332
00:19:43,320 --> 00:19:46,090
როგორ უნდა წავიდეს შესახებ დახარისხება ამ ღირებულებებს?

333
00:19:46,090 --> 00:19:52,530
თუ იყო ადამიანის მოცემული ამ ამოცანის, რა სახის ინტუიციური მიდგომა იქნებოდა თუ არა

334
00:19:52,530 --> 00:19:54,800
to დახარისხება მთელი bunch of ციფრები?

335
00:19:54,800 --> 00:19:57,050
ეს ყველაფერი იყო ასახული, როგორც თავსატეხი ცალი. Yeah.

336
00:19:57,050 --> 00:19:59,950
>> [სტუდენტი] მინდა მიიღოს თითოეული ნომრის და შეადაროთ იგი თითოეული

337
00:19:59,950 --> 00:20:03,180
შენარჩუნებას და აპირებს მარცხნივ. >> Okay, კარგი.

338
00:20:03,180 --> 00:20:05,720
ასე რომ მიიღოს თითოეული ნომერი, შეადაროთ იგი ერთი შემდეგი მას,

339
00:20:05,720 --> 00:20:09,610
და მაშინ უბრალოდ შეინახოს მოძრავი გასწვრივ სიაში, სახის rejiggering რამ როგორც თქვენ გადასვლა.

340
00:20:09,610 --> 00:20:13,800
ასე რომ აქ გვაქვს შანსი იქნებ კიდევ რამდენიმე FOLKS ჩაერთოს.

341
00:20:13,800 --> 00:20:16,290
გვაქვს 8 მეტი მოხალისეები ვინც რომ მიყვარს ამუშავება?

342
00:20:16,290 --> 00:20:23,950
ცოტა ნაკლები ზეწოლა რადგან თქვენ არ მხოლოდ ერთი. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Come on ქვემოთ. თქვენ ბიჭები ვაპირებთ იყოს ციფრები 1 მეშვეობით 8.

344
00:20:28,190 --> 00:20:36,050
ვნახოთ, შევძლებთ თუ არა ამის გაკეთება დახარისხება ამისთვის ალექს გაცილებით ისევე მე ეს წინასწარ.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
წავიდეთ წინ და თუ, გამოდიან სცენაზე შორის მუსიკა სტენდი და მე აქ

347
00:20:40,760 --> 00:20:44,960
იმავე მიზნით, როგორც slide ეკრანზე.

348
00:20:47,910 --> 00:20:49,680
Uh-Oh.

349
00:20:50,370 --> 00:20:53,230
ჩვენ ვიმუშავებთ თქვენ შევიდა შემდეგი მაგალითი. ოჰ, დაველოდოთ, დაველოდოთ. Here We Go. დაელოდეთ.

350
00:20:53,230 --> 00:20:57,570
შემდეგი მაგალითი არის. აი ისიც. ხმების 8. Come on up.

351
00:20:57,570 --> 00:21:00,270
ყველა უფლება. დალაგების თქუენგან მიხედვით ამ.

352
00:21:00,270 --> 00:21:03,620
Slide უბრალოდ ცოტა იმ მხარეს მუსიკა დავდგეთ აქ.

353
00:21:03,620 --> 00:21:12,310
ასე რომ, ჩვენ გვაქვს 4, 2, 6 - მიიღონ იქ, მეტი აქ, უფლება არსებობს - 3.

354
00:21:12,310 --> 00:21:17,570
Yeah. Okay. თქვენ გადასვლა ზე მეტი აქ. არა, თქვენ იქ.

355
00:21:17,570 --> 00:21:21,840
ჰო, უფლება არსებობს. მე ვარ არასწორია. უფლება არსებობს. Okay, ძალიან კარგი. Okay.

356
00:21:21,840 --> 00:21:24,930
ახლა მოდით დასალაგებლად მათ იზრდება ბრძანებით.

357
00:21:24,930 --> 00:21:26,210
>> როგორ შემიძლია წასვლა შესახებ ამით?

358
00:21:26,210 --> 00:21:28,630
ალგორითმი, რომ შემოთავაზებული იყო მომენტში წინ იყო, რატომ არ ვართ, უბრალოდ შევადარებთ

359
00:21:28,630 --> 00:21:31,970
FOLKS რომლებიც სახის შემდეგი ერთმანეთს და შემდეგ დააფიქსირონ ნებისმიერი შეცდომები,

360
00:21:31,970 --> 00:21:33,540
მოძრავი მარცხნიდან მარჯვნივ.

361
00:21:33,540 --> 00:21:36,580
ასე რომ აქ გვაქვს 4 და 2, აშკარად მწყობრიდან. მოდით სვოპ თქვენ. Okay.

362
00:21:36,580 --> 00:21:40,760
ახლა მე ვაპირებ ქვევით ხაზი. 4 და 6, nope. [სიცილის]

363
00:21:40,760 --> 00:21:45,010
6 და 8, საკმაოდ კარგი. 8 და 1 ნება მიბოძეთ, სვოპ თქვენ ბიჭები. ყველა უფლება.

364
00:21:45,010 --> 00:21:48,030
ასე რომ 8 და 3, სვოპ თქვენ ბიჭები.

365
00:21:48,030 --> 00:21:52,280
8 და 7, ნება მომეცით სვოპ თქვენ ბიჭები. 5 და 8, შესანიშნავი.

366
00:21:52,280 --> 00:21:54,820
მე გაძლევთ დახარისხებული სია.

367
00:21:54,820 --> 00:21:56,860
ყველა უფლება. ასე რომ არ საკმაოდ.

368
00:21:56,860 --> 00:22:01,180
მაგრამ სჯობს, რადგან უფრო დიდი ციფრები, - მაგალითია 8 -

369
00:22:01,180 --> 00:22:04,030
არ სახის bubbled მდე მარცხენა მეტი უფლება.

370
00:22:04,030 --> 00:22:08,010
ამიტომ მე მივიღე 1 მათგანი უფლება, მაგრამ ეს იგრძნობა ამ არ საკმაოდ პრობლემის მოგვარებას.

371
00:22:08,010 --> 00:22:11,150
>> ასე რომ რას შესთავაზოს გავაკეთოთ შემდეგი? >> [სტუდენტი] ნუ ვაკეთებთ. >> ჩვენ გვაქვს ვაკეთებთ.

372
00:22:11,150 --> 00:22:13,740
და გააცნობიეროს, კიდევ ერთხელ, ჩვენ დავსახეთ რამ მიერ მხოლოდ მქონე ყველა ადამიანისა

373
00:22:13,740 --> 00:22:17,180
სახის ჭკვიანურად მოწყობა თავად ეფუძნება, რომ სურათი,

374
00:22:17,180 --> 00:22:19,040
მაგრამ ახლა ჩვენ უფრო მეთოდური.

375
00:22:19,040 --> 00:22:21,510
ჩვენ უნდა ვიყოთ ალგორითმული ამის შესახებ, თითქოს ჩვენ წერილობით კოდი -

376
00:22:21,510 --> 00:22:23,520
ამ შემთხვევაში სიტყვიერი pseudocode.

377
00:22:23,520 --> 00:22:26,040
ნება მომეცით, სცადეთ რომ ერთხელ. რომ მუშაობდა კარგად. ეს არ გადაჭრის იგი.

378
00:22:26,040 --> 00:22:30,400
მაგრამ როდესაც ეჭვი, სცადეთ და სცადეთ კიდევ ერთხელ. ასე რომ 2 და 4, არ უშველა უქმნით.

379
00:22:30,400 --> 00:22:33,200
4 და 6. Ah! 6 და 1, ოდნავ უკეთესი არის.

380
00:22:33,200 --> 00:22:39,740
6 და 3, კარგი. 6 და 7, 7 და 5, 7 და 8, კარგი.

381
00:22:39,740 --> 00:22:44,060
და თქვენ იცით, მე ალბათ შეუძლია იგნორირება 8 არის, რადგან ის დასასრულს სიაში.

382
00:22:44,060 --> 00:22:47,250
იქნებ ჩვენ არ გვაქვს ფიქრი ვინმე აპირებს წარსულში მას.

383
00:22:47,250 --> 00:22:49,240
მაგრამ ვნახოთ, თუ რომ უსაფრთხო ვარაუდი.

384
00:22:49,240 --> 00:22:52,340
ახლა სია - Damn - არ დახარისხებული. მოდით ვეცადოთ ეს კიდევ ერთხელ.

385
00:22:52,340 --> 00:22:56,440
ასე რომ 2 და 4, 4 და 1, 4 და 3.

386
00:22:56,440 --> 00:22:59,230
4 და 6, კარგი. 6 და 5, კარგი.

387
00:22:59,230 --> 00:23:04,890
6, 7, 8 და, კარგი. მაგრამ ცნობა, შემიძლია მხოლოდ შეწყვიტოს აქ არის და შეწყვიტოს აქ არის?

388
00:23:04,890 --> 00:23:07,770
[სტუდენტი] დიახ. >> Yeah?

389
00:23:07,770 --> 00:23:11,160
რა მოხდება, თუ ერთი თქვენგანი იყო ნომერი 9 ყველა გზა იქ?

390
00:23:11,160 --> 00:23:13,640
ეს იქნებოდა დახარისხებული. >> კარგი. ეს იქნებოდა დახარისხებული პირველად გარშემო.

391
00:23:13,640 --> 00:23:16,050
კარგი. მოდით დავუბრუნდეთ ისევ. ჩვენ თითქმის იქ.

392
00:23:16,050 --> 00:23:22,800
1 და 2, 2 და 3, 3 და 4, 4 და 5, 5 და 6, 6 და 7, 7 და 8.

393
00:23:22,800 --> 00:23:26,640
>> მე კეთდება ახლა მაგრამ, ისევ, მე კომპიუტერი, რომელიც მხოლოდ რა მე მითხრეს, რომ გააკეთოს,

394
00:23:26,640 --> 00:23:30,120
და ჩემი ერთადერთი მოგონებაა ახლა ის არის, რომ მე რეალურად მხოლოდ გააკეთეს ცოტა მუშაობა.

395
00:23:30,120 --> 00:23:31,700
რაღაც შეცვლილა.

396
00:23:31,700 --> 00:23:37,100
ასე რომ მე არ ტექნიკურად დაადასტურა ვიზუალურად ან algorithmically რომ ამ სიაში მართლაც დახარისხებული.

397
00:23:37,100 --> 00:23:40,720
ასე რომ მხოლოდ კარგი ღონისძიება, უბრალოდ უნდა იყოს anal შესახებ, მოდით ეს 1 მეტი დრო.

398
00:23:40,720 --> 00:23:44,040
ასე რომ 1 და 2, 2 და 3, 3 და 4. და თქვენ იცით, რა ხდება?

399
00:23:44,040 --> 00:23:46,190
მხოლოდ კარგი ღონისძიება, მე ვაპირებ შენარჩუნება სიმღერა ჩემს მხრივ, ეს დრო

400
00:23:46,190 --> 00:23:51,110
რამდენი სვოპების მე მხოლოდ ისე, რომ მე ვიცი, რამდენად იმუშავებს მე კეთდება.

401
00:23:51,110 --> 00:23:56,930
3 და 4, 4 და 5, 5 და 6, 6 და 7, 7 და 8. არარის გაცვლებს.

402
00:23:56,930 --> 00:24:00,800
ახლა მინდა ლეგიტიმურად იყოს იდიოტი, რომ ეს კიდევ ერთხელ გავაკეთოთ

403
00:24:00,800 --> 00:24:03,330
რადგან მე რომ არ მუშაობდა ამ უღელტეხილზე ადამიანები,

404
00:24:03,330 --> 00:24:06,710
მაშინ ნათლად რომ აპირებს განმეორდეს, თუ არც ერთი მათგანი არ არის ერთგვარი შემთხვევით

405
00:24:06,710 --> 00:24:10,410
adversarially მოძრავი თავად გარშემო. ახლა შემიძლია შეწყვიტოს.

406
00:24:10,410 --> 00:24:15,120
ახლა მოდით ვთხოვოთ კითხვაზე, რამდენად მუშაობა ეს პრაქტიკულად me?

407
00:24:15,120 --> 00:24:18,260
რამდენი ნაბიჯები საერთოდ რომ მიიღოს? >> N კვადრატში.

408
00:24:18,260 --> 00:24:20,400
ჰო, ისე N კვადრატში. სად იღებთ N კვადრატში საწყისი?

409
00:24:20,400 --> 00:24:22,660
თქვენ უნდა შეამოწმოთ თითოეულ num -

410
00:24:22,660 --> 00:24:26,530
არსებობს N ციფრები, და თქვენ უნდა შეამოწმოთ თითოეული ნომერი სხვა N ნომრები.

411
00:24:26,530 --> 00:24:29,030
კარგი. >> ამიტომ n კვადრატში. >> კარგი.

412
00:24:29,030 --> 00:24:31,060
>> ასე რომ იგრძნობა ეს შეიძლება ძალიან კარგად იყოს N კვადრატში, არა?

413
00:24:31,060 --> 00:24:33,820
აქ ნ ეს ბიჭები, 8 კონკრეტულად ამ შემთხვევაში,

414
00:24:33,820 --> 00:24:37,590
მაგრამ ყოველ ჯერზე, მე გაიარა ამ სიაში მე შედარებით პირველი პირი წინააღმდეგ მეორე,

415
00:24:37,590 --> 00:24:39,650
მეორე წინააღმდეგ მესამე ისევ და ისევ და ისევ,

416
00:24:39,650 --> 00:24:42,450
და როცა ბოლომდე, რა გავაკეთო? მე redid იგი.

417
00:24:42,450 --> 00:24:46,280
ასე რომ, თუ ჩვენ განზოგადება ამ განმარტებით, ჩვენ n ხალხი

418
00:24:46,280 --> 00:24:51,090
და მე მიღების, ცხადია, 8 ნაბიჯები, N ნაბიჯები, ყოველ ჯერზე მე გავლა ეს ალგორითმი.

419
00:24:51,090 --> 00:24:56,070
მაგრამ როგორ ბევრჯერ უარეს შემთხვევაში უნდა გაიაროს ამ სიაში ხალხს?

420
00:24:56,070 --> 00:24:59,370
[სტუდენტი] N ჯერ. >> ალბათ N, უფლება, რადგან უარეს შემთხვევაში,

421
00:24:59,370 --> 00:25:03,410
რა ალბათ უარეს შემთხვევაში მოწყობა ამ ბიჭებს საწყისი მიიღოთ-go?

422
00:25:03,410 --> 00:25:06,520
თუ ისინი სრულიად საპირისპიროა მიზნით

423
00:25:06,520 --> 00:25:09,310
რადგან მხოლოდ ვივარაუდოთ გონებრივად, let's - რა არის თქვენი სახელი? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Okay. ამიტომ Bowen, მოდის, აქ მხოლოდ ერთი წუთით.

425
00:25:12,510 --> 00:25:16,150
>> ვარაუდობენ, რომ Bowen იყო აქ დასაწყისში ალგორითმი,

426
00:25:16,150 --> 00:25:19,790
და ჩვენ არ ვიცით, რა ყველას არის, მაგრამ აქ Bowen თანახმად, ეს ალგორითმი -

427
00:25:19,790 --> 00:25:23,820
და თუ გნებავთ უბრალოდ სეირნობა ჩემთან - აპირებს ბუშტი up, როგორც მან პირველად გარშემო,

428
00:25:23,820 --> 00:25:25,740
ყველა გზა ბოლომდე.

429
00:25:25,740 --> 00:25:29,400
მაგრამ ვარაუდობენ, რომ პირის შემდეგ Bowen იყო ნომერი 7.

430
00:25:29,400 --> 00:25:33,450
მე უნდა დაბრუნდეს და მიიღეთ ნომერი 7, რაც იმას ნიშნავს, მე უნდა წავიდეთ ყველა გზა უკან აქ.

431
00:25:33,450 --> 00:25:36,980
ახლა კი უნდა ჰქონდეს, რომ იგივე სეირნობა ერთად პირს, რომელიც ხმების 7.

432
00:25:36,980 --> 00:25:40,140
მაგრამ რა, თუ შემდეგ ნომერზე 6 იყო შემდეგი მისთვის ისევე?

433
00:25:40,140 --> 00:25:42,180
მაშინ მე უნდა დაბრუნდეს და კიდევ 6.

434
00:25:42,180 --> 00:25:46,490
ასე რომ კიდევ ერთხელ, ყოველ iteration ამ loop ვსაუბრობ თითოეულ N ადამიანი,

435
00:25:46,490 --> 00:25:50,090
და ალბათ უნდა გააკეთოთ n ამ სეირნობა რომ დავრწმუნდეთ მე გამწევ

436
00:25:50,090 --> 00:25:53,760
ყველა უმსხვილესი ელემენტების უკან და უკან და უკან, ძალიან სიის ბოლოში.

437
00:25:53,760 --> 00:25:58,230
ამიტომ N რამ N ჯერ მხოლოდ N ჯერ n ან N კვადრატში.

438
00:25:58,230 --> 00:26:02,050
>> ასე რომ აქ უკვე გვაქვს ალგორითმი რომ აღარ N, რომ აღარ შესვლა N,

439
00:26:02,050 --> 00:26:04,820
სინამდვილეში უარესი არაფერი ჩვენ გავაკეთეთ ადრე.

440
00:26:04,820 --> 00:26:09,840
ასე რომ ალექს სახის მიიღო გაუმართლა, რომ მე ყველა სამუშაო სავარაუდოდ up წინა მისთვის,

441
00:26:09,840 --> 00:26:14,690
ყველა ძვირი მუშაობა, რათა მან შეიძლება ისარგებლოს ამ ბინარული ძებნის ალგორითმი,

442
00:26:14,690 --> 00:26:16,420
რაც შესვლა of n.

443
00:26:16,420 --> 00:26:18,240
მაგრამ ეს შეესაბამება ორშაბათს თემა.

444
00:26:18,240 --> 00:26:23,260
მივეცით ცოტა მეტი სივრცე, ჩვენ გამოყენებული მეტი ბიტი, რათა დაჩქარდეს ჩვენი გაშვებული დრო.

445
00:26:23,260 --> 00:26:26,170
ასე ჰგავს არსებობს ამ შორის ვაჭრობის დრო და სივრცე,

446
00:26:26,170 --> 00:26:31,060
შეიძლება ასევე მხოლოდ ვაჭრობის ღ შორის გატარებული დრო up წინა სახის მიღების რამ მზად ვართ წავიდეთ

447
00:26:31,060 --> 00:26:35,000
და ფაქტობრივად შესრულებაში ალგორითმი მოსწონს ძებნა. მოდით ვეცადოთ კიდევ ერთი.

448
00:26:35,000 --> 00:26:39,050
თუ ბიჭები არ იბადება უბრალოდ სწრაფად rearranging თქუენგან ემთხვევა, რომ კიდევ ერთხელ,

449
00:26:39,050 --> 00:26:42,240
მოდით ძიებასა ოდნავ განსხვავებული, სადაც ეს არ საკმაოდ მარტივია

450
00:26:42,240 --> 00:26:45,760
როგორც მხოლოდ დაფიქსირება ყველა pairwise შეცდომები, რაც სუპერ ინტუიციური.

451
00:26:45,760 --> 00:26:48,150
მოდით ნაცვლად იყოს უფრო მიზანმიმართული და ამის გაკეთება.

452
00:26:48,150 --> 00:26:51,010
ეს ერთი ძალიან მინდა შესთავაზოს ალბათ საკმაოდ ინტუიციური.

453
00:26:51,010 --> 00:26:55,070
>> მოდით აირჩიეთ პატარა პირის სიიდან ისევ და ისევ. ასე რომ აქ ჩვენ მივდივართ.

454
00:26:55,070 --> 00:26:57,350
4, თქვენ პატარა პირი მე რითაც ჩანს ჯერჯერობით

455
00:26:57,350 --> 00:27:00,520
ამიტომ მე ვაპირებ სულიერად გვახსოვდეს, რომ მხოლოდ მიუთითებს თქვენ ახლა.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! დაივიწყეთ ნომერი 4. მე უბრალოდ ი ახალი პატარა ელემენტს ამ სიაში.

457
00:27:05,020 --> 00:27:07,410
მე ვაპირებ სახის გვახსოვდეს, რომ. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Goodbye. ახლა მე ვაპირებ გვახსოვს ნომერი 1.

459
00:27:11,190 --> 00:27:14,790
ჩვენ ვიცით, რომ 1 არის ყველაზე მცირე, მაგრამ მე კომპიუტერში. რა მოხდება თუ არსებობს 0?

460
00:27:14,790 --> 00:27:17,140
რა მოხდება თუ არსებობს -1? მე შენარჩუნება აპირებს.

461
00:27:17,140 --> 00:27:20,990
ასე რომ 3, 7, 5, nope. Okay. ამიტომ ნომერი 1 იყო პატარა.

462
00:27:20,990 --> 00:27:23,640
ნება მომეცით აირჩიეთ თქვენ სიიდან - we'll ამ გზით -

463
00:27:23,640 --> 00:27:27,760
და ამით თქვენ თვითნებურად დასაწყისში სიაში.

464
00:27:27,760 --> 00:27:29,740
ახლა დაველოდოთ წუთში. I ტიპის იწყებენ.

465
00:27:29,740 --> 00:27:34,010
თუ ეს ბიჭები წარმოადგენენ არა სიაში 8 ადამიანი მაგრამ მასივი,

466
00:27:34,010 --> 00:27:37,050
8 მოცულობით მიმდებარე მეხსიერება - თქვენ იბადება სტეპინგზე უკან მხოლოდ ამ მომენტში?

467
00:27:37,050 --> 00:27:39,060
არსებობს რეალურად არ სივრცე თქვენ უფლება აქ.

468
00:27:39,060 --> 00:27:41,840
ასე როგორ უნდა გააკეთოს ფართი - რა გქვია? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
როგორ ვაწარმოებთ ფართი Sammy?

470
00:27:43,710 --> 00:27:46,760
>> ჩვენ გადაადგილება N, რომლებიც ჩემ წინაშე. >> Okay.

471
00:27:46,760 --> 00:27:48,850
ამიტომ ვერ გადავა N ადამიანები, რომლებიც მის წინაშე,

472
00:27:48,850 --> 00:27:52,400
ასე რომ, თუ თქვენ ბიჭები სურს 1 მიზანმიმართული და დრამატული ნაბიჯი მარცხნივ.

473
00:27:52,400 --> 00:27:57,000
ისინი ყველა გააკეთეს, რომ უნისონში, მაგრამ ბოლო დროს დავწერე რაღაც კოდი,

474
00:27:57,000 --> 00:27:59,740
ვერ სახის გადაადგილება ბევრი რამ ერთდროულად.

475
00:27:59,740 --> 00:28:02,450
ჩვენ შეგვეძლო ამას მარყუჟის, მოძრავი ყველას ერთხელ დროს.

476
00:28:02,450 --> 00:28:04,340
ასე რომ, თუ თქვენ ბიჭები არ იბადება სტეპინგზე თავში უფლება,

477
00:28:04,340 --> 00:28:07,230
და Sammy, თუ შეიძლება უკან დახევას, რადგან იქ მაინც არ ოთახი თქვენთვის,

478
00:28:07,230 --> 00:28:11,420
ახლა მოდით ეს. სად იყო Sammy მომენტში წინ? უფლება არსებობს.

479
00:28:11,420 --> 00:28:16,140
ასე რომ არსებობს შეუსაბამობა არსებობს. ასე, რომ თქვენ შეიძლება გადაინაცვლოს Sammy ნახვა ადგილზე.

480
00:28:16,140 --> 00:28:20,580
ახლა შემდეგი პირი up და ახლა შემდეგი პირი, ახლა შემდეგი პირს. ახლა ჩვენ გვაქვს ოთახში Sammy.

481
00:28:20,580 --> 00:28:23,490
ახლა, ვინმე აუდიტორიის - ეს იყო კარგი, რომ იყო ზუსტი,

482
00:28:23,490 --> 00:28:27,070
ეს იგრძნო პატარა შრომატევადი - რა სწრაფად? Yeah.

483
00:28:27,070 --> 00:28:29,440
[სტუდენტი] ახალი მასივი? >> რა არის რომ? >> [სტუდენტი] ახალი მასივი? >> Okay, კარგი.

484
00:28:29,440 --> 00:28:33,200
>> ასე რომ შეესაბამება ამ თემაზე მხოლოდ ვაჭრობის ღ, რატომ არ მე უბრალოდ მიიღოს ახალი მასივი

485
00:28:33,200 --> 00:28:36,570
 და შემდეგ Sammy იქნება საცურაო სივრცეში წინაშე ეს ადამიანები, მაგალითად,

486
00:28:36,570 --> 00:28:39,600
და ჩვენ შეგვიძლია დავიწყო შევსების ახალი array საერთოდ. რომ ძალიან იმუშავებს.

487
00:28:39,600 --> 00:28:42,450
მაგრამ მე არ აინტერესებს ხარჯვის მეტი სივრცე დღეს. რა არის კიდევ ერთი მიდგომა?

488
00:28:42,450 --> 00:28:46,630
[სტუდენტი] სვოპი. >> Okay. ჩვენ შეგვეძლო მხოლოდ სვოპ ამ 2 guys. რა არის შენი სახელი?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. ამიტომ Mario, იყავით გაკეთებული აქ.

490
00:28:49,390 --> 00:28:52,480
Sammy, შეგიძლიათ უკან up მხოლოდ ამ მომენტში? მარიო იყო აქ.

491
00:28:52,480 --> 00:28:55,830
ჩვენ არ გვაქვს ოთახში თქვენ აღარ ასე რომ, თუ თქვენ არ იბადება აპირებს, სადაც Sammy არის,

492
00:28:55,830 --> 00:29:02,430
ჩვენ დააყენა Sammy აქ და ახლა მინდა ამტკიცებენ, რომ Sammy ს შევცვალე ოპერაცია იყო ბევრად უფრო სწრაფად.

493
00:29:02,430 --> 00:29:06,370
ჩვენ 1 ოპერაცია სვოპ ამ ბიჭებს, ან იქნებ 2 to სვოპ ამ ბიჭებს,

494
00:29:06,370 --> 00:29:11,210
მაგრამ ჩვენ არ 1, 2, 3, 4, ისე, რომ თავს კარგად გრძნობს. ახლა დაველოდოთ წუთში.

495
00:29:11,210 --> 00:29:14,660
I ტიპის გააკეთა პრობლემა უარესი იმიტომ ნომერი 4 იყო სახის ახლოს დასაწყისია.

496
00:29:14,660 --> 00:29:19,470
ახლა ნომერი 4 არის პატარა დაახლოება ამ მიზნით, მაგრამ მე არ ვიცი ან აინტერესებს, რომ.

497
00:29:19,470 --> 00:29:23,330
ასე რომ, ეს უბრალოდ ცუდი იღბალი რომ ნომერი 4 არის ოდნავ მოშორებით დაშორებით თავისი განკუთვნილი ადგილი.

498
00:29:23,330 --> 00:29:25,110
მოდით ახლა ვიმეორებ ეს ალგორითმი.

499
00:29:25,110 --> 00:29:28,410
>> To recap, რადგან, რომ ამბავი იყო, ყველა ჩვენ არ იყო გავლა სია

500
00:29:28,410 --> 00:29:31,130
ეძებს პატარა დანომრილი პირი.

501
00:29:31,130 --> 00:29:34,530
ახლა მოდით ეს კიდევ ერთხელ. ჩვენ არ გვაქვს ფიქრი Sammy უქმნით.

502
00:29:34,530 --> 00:29:37,590
ჩვენ შეგვიძლია უბრალოდ აქ. Ooh! ხმების 2. სწორედ საკმაოდ მცირე რაოდენობით.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Okay, კარგი.

504
00:29:41,180 --> 00:29:43,770
და საბედნიეროდ, დაემთხვა, მე არ უნდა გადავიდეთ - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie რადგან ის თავის ადგილს მიუჩენს ახლა.

506
00:29:45,910 --> 00:29:48,110
მოდით ეს კიდევ ერთხელ გავაკეთოთ და იგნორირება ამ 2 guys.

507
00:29:48,110 --> 00:29:50,460
6. სწორედ საკმაოდ მცირე რაოდენობით. Ooh! 8 ნამდვილად დიდია.

508
00:29:50,460 --> 00:29:53,410
4. მოდით ფოკუსირება 4. Ooh! 3 არის უფრო უკეთესი.

509
00:29:53,410 --> 00:29:58,290
7 და 5. ასე რომ რას ვაკეთებთ ახლა - >> როჯერ. >> როჯერ?

510
00:29:58,290 --> 00:30:00,250
მოდით სვოპ მას ხმების 6.

511
00:30:00,250 --> 00:30:03,570
ასე რომ, თუ 6 და 3 მინდა სვოპ,

512
00:30:03,570 --> 00:30:07,320
ჩვენ ახლა სახის მიღებული გაუმართლა, რომ 6 უფრო ახლოსაა, სადაც იგი უნდა იყოს,

513
00:30:07,320 --> 00:30:10,300
მაგრამ ეს მხოლოდ დამთხვევა აქ. მოდით ეხლა აქ.

514
00:30:10,300 --> 00:30:13,430
8 არის საკმაოდ მცირე რაოდენობით. Ooh! 4 პატარაა.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. რას ახლა? >> სვოპი. >> ზუსტად.

516
00:30:17,130 --> 00:30:19,010
ახლა მოდით ეს ერთგვარი სწრაფად.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. სად 5 წავიდეთ? კარგი. Okay.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 იღებს დარჩენა, სადაც ის არის. რა არის შენი სახელი? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie იღებს დარჩენა, სადაც ის არის. 7 იღებს - ვნახოთ. 7, 8. Okay.

520
00:30:31,770 --> 00:30:35,100
ასე რომ 7 იღებს დარჩენა, სადაც ის არის. რა არის შენი სახელი? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> ამიტომ Amna იღებს დარჩენა, სადაც ის არის, და ნომერი 8 უკვე სადაც ახლა უნდა იყოს.

522
00:30:39,670 --> 00:30:43,960
Okay, კარგი. მიდრეკილება ჩვენ უბრალოდ შექმნის სამუშაოები ვდებთ აქ, თუმცა.

523
00:30:43,960 --> 00:30:47,440
რა არის საბოლოოდ ქრონომეტრაჟი ამ ალგორითმი?

524
00:30:47,440 --> 00:30:51,900
თუ ჩვენ ვფიქრობ ამ ადამიანებს არა როგორც 8 მაგრამ, როგორც N? >> ეს n.

525
00:30:51,900 --> 00:30:55,440
ეს n ნაბიჯები, მაგრამ ჩვენ შემოწმების თითოეული დრო.

526
00:30:55,440 --> 00:30:57,570
Okay. N მაგრამ თქვენ შემოწმების თითოეულ დროს?

527
00:30:57,570 --> 00:31:03,450
Okay, მაგრამ თუ ის n ნაბიჯები, არ უნდა მე ვერ დასალაგებლად თქვენ მიერ მხოლოდ აპირებს 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Okay, რომ დიდი განსხვავება.

529
00:31:05,590 --> 00:31:08,050
ამიტომ N კვადრატში რატომ? რა ხდება რეალურად?

530
00:31:08,050 --> 00:31:12,130
არსებობს N ხალხი ამ სიაში, მაგრამ იპოვონ ყველაზე მცირე პირი სია

531
00:31:12,130 --> 00:31:16,200
ყველაზე ცუდ შემთხვევაში, თუ რამდენი ნაბიჯები უნდა გადადგას? >> ნ

532
00:31:16,200 --> 00:31:19,160
>> N, უფლება, რადგან უარეს შემთხვევაში, ნომერი 1 არის ყველა გზა იქ,

533
00:31:19,160 --> 00:31:20,990
ამიტომ უნდა წახვიდე კიდევ მას.

534
00:31:20,990 --> 00:31:25,500
და მაშინ როდესაც მე საბოლოოდ გააცნობიეროს 1 იყო პატარა, მაშინ იგი საკმაოდ სწრაფია სვოპ მათ.

535
00:31:25,500 --> 00:31:28,450
მაგრამ ახლა უნდა დაიწყოს თავიდან და ვეძებთ ვინ?

536
00:31:28,450 --> 00:31:31,980
შემდეგი ყველაზე პატარა პირი, რომელიც 2. სადაც უარეს შემთხვევაში არის 2?

537
00:31:31,980 --> 00:31:34,320
ოჰ, ღმერთი ჩემი. ეს ყველა გზა აქ დასასრულს.

538
00:31:34,320 --> 00:31:37,000
ახლა მე უბრალოდ გაკეთდეს კიდევ ერთი N ნაბიჯები, მეორე n ნაბიჯები.

539
00:31:37,000 --> 00:31:41,200
და თუ გვაქვს N ხალხს და უარეს შემთხვევაში პატარა პირი N ნაბიჯის მოშორებით,

540
00:31:41,200 --> 00:31:45,230
რომ კვლავ N ჯერ N, და ამიტომ ჩვენ ისევ არ n კვადრატში.

541
00:31:45,230 --> 00:31:47,280
ეს არ არის შეგრძნება იმდენად კარგი.

542
00:31:47,280 --> 00:31:52,150
ფაქტია, მაშინაც კი, საუკეთესო შემთხვევაში - ვივარაუდოთ, რომ ისინი დაიწყება off დახარისხებული -

543
00:31:52,150 --> 00:31:59,080
რამდენი ნაბიჯები სჭირდება ჩემთვის გამოყენებისას ალგორითმი დასალაგებლად ამ N ხალხს?

544
00:31:59,080 --> 00:32:01,010
N კვადრატში. >> გავიგე N კვადრატში. რატომ N კვადრატში?

545
00:32:01,010 --> 00:32:05,240
იმიტომ, რომ თქვენ კვლავ უნდა შეამოწმოს თითოეული დრო. >> Yeah.

546
00:32:05,240 --> 00:32:08,060
და თქვენ უნდა სვოპ მათ. >> მიუხედავად იმისა, რომ ჩვენ ადამიანები ვართ სახის omniscient

547
00:32:08,060 --> 00:32:10,770
იმ გაგებით, ვიზუალურად, რომ ჩვენ უბრალოდ სახის ვნახავთ, რომ ეს დახარისხებული,

548
00:32:10,770 --> 00:32:12,140
კომპიუტერი არაა, რომ smart.

549
00:32:12,140 --> 00:32:14,040
იგი აპირებს გამოიყურებოდეს აქ და აქ და აქ,

550
00:32:14,040 --> 00:32:16,610
მაგრამ თუ რასაც ის ეძებს ყველაზე პატარა ელემენტის,

551
00:32:16,610 --> 00:32:22,110
თქვენ მხოლოდ ვიცი, რომ თქვენ ი ყველაზე პატარა ელემენტს რა წერტილი? ერთხელ თქვენ დასასრულს.

552
00:32:22,110 --> 00:32:25,880
მაგრამ იმ ეტაპზე თქვენ მხოლოდ გაკეთებული პატარა ელემენტს.

553
00:32:25,880 --> 00:32:28,810
თქვენ არ აუცილებლად ვიცი არაფერი მდგომარეობის შესახებ მსოფლიოში.

554
00:32:28,810 --> 00:32:30,880
ასე რომ თქვენ არ წასვლა ისევ და ისევ და ისევ.

555
00:32:30,880 --> 00:32:34,880
>> ასე რომ, ეს დრო მართლაც გამოიყურებოდეს მუნჯები რადგან მე შემოწმების, okay, 2, თქვენ ყველაზე პატარა,

556
00:32:34,880 --> 00:32:37,530
მაგრამ არ ვიცი, რომ სულ არ არის.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Okay, კარგი. 2 მართლაც ყველაზე პატარა.

558
00:32:41,090 --> 00:32:43,150
ახლა მოდით მოვძებნოთ შემდეგი პატარა. Okay.

559
00:32:43,150 --> 00:32:48,350
3, თქვენ გაკეთებული პატარა. ვნახოთ. 4, 5, 6, 7, 8. Okay, მივიღე გაუმართლა ერთხელ.

560
00:32:48,350 --> 00:32:53,170
3 მართლაც სწორი ადგილი. მაგრამ მე ვაპირებ აკეთეთ ეს კიდევ ერთხელ და ისევ და ისევ.

561
00:32:53,170 --> 00:32:55,990
როგორ გავაკეთოთ ოდესმე ისე ოდნავ უკეთესი?

562
00:32:55,990 --> 00:33:00,120
იმის მაგივრად რომ ხალხს ბუშტი up pairwise საწყისი პატარა რომ უდიდესი

563
00:33:00,120 --> 00:33:04,350
და ნაცვლად აპირებს უკან და მეოთხე მეშვეობით სიის შერჩევის შემდეგ ყველაზე პატარა პირი,

564
00:33:04,350 --> 00:33:09,780
რატომ არ გვაქვს ნაცვლად ჩადეთ ეს ადამიანები ახალ სიაში ეტაპობრივად?

565
00:33:09,780 --> 00:33:13,080
მოდით ცდილობენ ამ. ახლა ნება მომეცით დაარქვით რამ Insertion ჯიშია.

566
00:33:13,080 --> 00:33:17,250
ასე რომ აქ ვართ აქ. ხმების 1. მე არ აინტერესებს ვინმეს ამ სიაში.

567
00:33:17,250 --> 00:33:21,310
ჩემი მიზანი სწორედ ახლა არის დააყენოს ნომერი 1 წლის დასაწყისში დახარისხებული სია.

568
00:33:21,310 --> 00:33:23,910
და მე ვაპირებ შესთავაზოს რადგან მე მხოლოდ 8 მოცულობით მეხსიერება,

569
00:33:23,910 --> 00:33:28,670
თვითნებურად ახლავე ვარ კედელს ჩემი სავარაუდოდ არასორტირებული სია,

570
00:33:28,670 --> 00:33:32,740
და ვინც არის ჩემს უკან მე ვაპირებ პრეტენზია არის დახარისხებული.

571
00:33:32,740 --> 00:33:34,680
ახლა ჩვენ გვაქ რიცხვი 1.

572
00:33:34,680 --> 00:33:39,240
მინდა ჩადეთ მას ჩემი დახარისხებული სია, ასე რომ მე უბრალოდ აპირებს გადავიდეს ჩემი კედლის მეტი აქ,

573
00:33:39,240 --> 00:33:43,930
და ახლა ადასტურებენ, რომ ამ სიაში დალაგებულია, ამ სიაში არასორტირებული - მინიმუმ რამდენადაც ვიცი.

574
00:33:43,930 --> 00:33:46,070
მე ვერ ვხედავ ყველა ნომრები ერთდროულად.

575
00:33:46,070 --> 00:33:49,000
>> ახლა კი მოხდეს ექმნებათ ნომერი 2. რა ვუყოთ მას?

576
00:33:49,000 --> 00:33:54,380
მე ჩადეთ თქვენ ახლა შევიდა დახარისხებული სია. მაგრამ შეამჩნია რა ადვილი რომ იყო.

577
00:33:54,380 --> 00:33:59,650
მე უბრალოდ უნდა გამოიყურებოდეს. ხმების 1 არის. ოჰ, აშკარად 2 ღებულობენ მხარეს ნომერი 1.

578
00:33:59,650 --> 00:34:03,700
ახლა რა ვუყოთ 3? მე ჩადეთ თქვენ შევიდა დახარისხებული სია. მაგრამ ეს იყო სუპერ მარტივია.

579
00:34:03,700 --> 00:34:07,250
ეს არის სუპერ მარტივია, ეს არის სუპერ მარტივია, ეს არის სუპერ მარტივი, სუპერ მარტივია, სუპერ მარტივია.

580
00:34:07,250 --> 00:34:12,790
და ახლა ყველაფერი დალაგებულია ჩემს უკან, და რამდენი ნაბიჯები საერთოდ რომ მიიღოს?

581
00:34:12,790 --> 00:34:15,620
[სტუდენტი] ნ >> ამიტომ მხოლოდ n. ჩვენ გაუმართლა.

582
00:34:15,620 --> 00:34:18,860
ეს იყო მხოლოდ N რატომ? >> [სტუდენტი] იმიტომ სია დახარისხებული.

583
00:34:18,860 --> 00:34:21,630
სიაში უკვე დახარისხებული. ამიტომ მივიღეთ გაუმართლა.

584
00:34:21,630 --> 00:34:25,639
მაგრამ ჩვენ შემუშავებული ალგორითმი ამ დროს harnesses რომ სახის წარმატებას,

585
00:34:25,639 --> 00:34:29,420
რომ საუკეთესო შემთხვევაში სცენარი, რომელსაც არ კარგვაა ზედმეტი დრო.

586
00:34:29,420 --> 00:34:31,750
ამიტომ, ჩვენ ახლა რა ჩვენ მოვუწოდებთ ბუშტი ჯიშები

587
00:34:31,750 --> 00:34:33,949
სადაც ადამიანებს სახის ბუშტი up pairwise.

588
00:34:33,949 --> 00:34:38,100
ჩვენ ახლა აქვს შერჩევის დალაგების სადაც ჩვენ pluck გარეთ პატარა პირი ისევ და ისევ.

589
00:34:38,100 --> 00:34:42,350
და ახლა ჩვენ გვაქვს Insertion დალაგების სადაც ჩვენ ერთგვარი აქტიურად დააყენა ხალხი, სადაც ისინი მიეკუთვნებიან

590
00:34:42,350 --> 00:34:45,000
მზარდი დახარისხებული სია.

591
00:34:45,000 --> 00:34:49,679
თუ შეგვეძლო, რაუნდი ტაში ამ ბიჭებს აქ. [ტაში]

592
00:34:49,679 --> 00:34:52,310
ავიღოთ ჩვენი 5 წუთიანი შესვენება აქ.

593
00:34:52,310 --> 00:34:55,139
და როდესაც ჩვენ დავბრუნდებით, ჩვენ აფეთქება ყველა ამ ალგორითმები წყლიდან

594
00:34:55,139 --> 00:35:00,260
რაღაც უკეთესი. ყველა უფლება. მადლობა ძალიან. თქვენ შეგიძლიათ შენარჩუნება იმ სახით სუვენირები.

595
00:35:01,710 --> 00:35:04,330
ყველა უფლება. ჩვენ უკან.

596
00:35:04,330 --> 00:35:08,420
>> და recap რეალური სწრაფი, ჩვენ გვქონდა ამ 3 სხვადასხვა მიდგომების დაფასოების,

597
00:35:08,420 --> 00:35:13,000
მთელი წერტილი იყო მისაღებად წერტილში, სადაც ვინმე მოსწონს ალექს

598
00:35:13,000 --> 00:35:16,930
შეიძლება ძებნის სიაში ნომრები უფრო სწრაფად, ვიდრე ვინმეს მოსწონს შონ შეეძლო.

599
00:35:16,930 --> 00:35:19,830
და მიუხედავად იმისა, რომ გვაქვს ასეთი მარტივი მაგალითები, 8 ნომრები,

600
00:35:19,830 --> 00:35:24,000
თქვენ შეიძლება extrapolate ადვილად 8 ვებ გვერდები, 8 მილიარდ ვებ გვერდები,

601
00:35:24,000 --> 00:35:26,680
ან 800 მილიონი მეგობრები Facebook-ზე.

602
00:35:26,680 --> 00:35:30,090
ასე რომ ეს ალგორითმები შეიძლება თქმა მასშტაბის იმ სახის ღირებულებები,

603
00:35:30,090 --> 00:35:32,300
და იდეები საბოლოოდ იგივე.

604
00:35:32,300 --> 00:35:36,140
ამიტომ ბუშტი დალაგების იყო პირველი, სადაც ჩვენ ერთგვარი bubbled up ყველაზე დიდი პირი

605
00:35:36,140 --> 00:35:39,110
ყველა გზა უფლება მიერ შევცვალე ხალხი pairwise.

606
00:35:39,110 --> 00:35:42,040
მაშინ ჩვენ გვქონდა რა ჩვენ მოვუწოდებთ შერჩევის დალაგების სადაც მე ცოტა მეტი განზრახ

607
00:35:42,040 --> 00:35:46,480
ინახება გადახედეთ სიას, შერჩევა ყველაზე პატარა ნომერი ისევ და ისევ და ისევ,

608
00:35:46,480 --> 00:35:49,530
ლოგიკური შედეგია, რომელიც არის ის, რომ სიაში საბოლოოდ დახარისხებული.

609
00:35:49,530 --> 00:35:53,780
მერე მესამე, მე ჩასმული ადამიანები თავიანთ შესაბამის ადგილზე,

610
00:35:53,780 --> 00:35:57,720
და ჩვენ ძალიან contrived მაგალითად, რომ სიაში უკვე დახარისხებული,

611
00:35:57,720 --> 00:36:01,100
მაგრამ, რომ მან გამოაგზავნა გაგზავნა, რომ Insertion დალაგების საქმე,

612
00:36:01,100 --> 00:36:02,670
შეგიძლიათ მიიღოთ გაუმართლა.

613
00:36:02,670 --> 00:36:07,930
თუ ციფრები უკვე დახარისხებული, ეს მხოლოდ აპირებს თქვენ N ნაბიჯები, რათა დაადასტუროს იმდენი,

614
00:36:07,930 --> 00:36:10,870
ხოლო შერჩევის დალაგების თქვენ ცოტა მეტი გვირაბი ხედვა

615
00:36:10,870 --> 00:36:14,360
და თქვენ არ ოდესმე მიხვდებიან, რომ სიაში უკვე დახარისხებული.

616
00:36:14,360 --> 00:36:16,830
ასე რომ ვნახოთ bubble sort მოქმედებაში აქ.

617
00:36:16,830 --> 00:36:19,590
მიმდინარე მაგალითში, ჩვენ შესახებ, რომ ნახოთ ვერტიკალური ბარები

618
00:36:19,590 --> 00:36:23,030
რომლის სიმაღლეებზე წარმოადგენენ ციფრები ისე, რომ ჩვენ შეგვიძლია სახის ვიზუალიზაციისთვის დახარისხება მოხდეს.

619
00:36:23,030 --> 00:36:26,630
პატარა ბარი, პატარა ნომერი; უფრო დიდი ბარი, მით უფრო დიდია რიცხვი.

620
00:36:26,630 --> 00:36:28,860
>> და ჩვენ ითამაშოთ ამ ნაგულისხმევი სიჩქარე.

621
00:36:28,860 --> 00:36:33,460
იგი აპირებს გადავიდეს ცოტა სწრაფად, მაგრამ წითელი არის რა გვიჩვენებს 2 ბარები

622
00:36:33,460 --> 00:36:35,480
მიმდინარეობს შედარებით თალიზში.

623
00:36:35,480 --> 00:36:39,520
და თუ თქვენ უყურებთ მჭიდროდ, რა მოხდება, თუ ბარები მწყობრიდან გამოსულია,

624
00:36:39,520 --> 00:36:42,300
პატარა ერთი იღებს გადავიდა მარცხენა, მით უფრო დიდია ერთი მარჯვნივ,

625
00:36:42,300 --> 00:36:44,360
და მაშინ თქვენ გაქვთ მიიწევს.

626
00:36:44,360 --> 00:36:48,520
ასე რომ, თუ ჩვენ ამას ვაკეთებთ, ისევ და ისევ შეამჩნევთ, რომ პატარა ბარები

627
00:36:48,520 --> 00:36:51,090
ვაპირებთ შენარჩუნება inching მათი გზა მარცხენა

628
00:36:51,090 --> 00:36:54,130
და ყველაზე დიდი ბარები ვაპირებთ შენარჩუნება inching მათი გზა უფლება.

629
00:36:54,130 --> 00:36:58,490
მართლაც, ჩვენ ვიწყებთ ვხედავთ ნიმუში ყველა გზა ზე მარჯვენა მხარეს

630
00:36:58,490 --> 00:37:04,790
ისევე, როგორც დავინახეთ, 8 და შემდეგ 7 საბოლოოდ bubbling მდე შორს ბოლოს ჩვენი ადამიანის სიაში.

631
00:37:04,790 --> 00:37:08,750
ასე რომ, ეს აპირებს ძალიან სწრაფად მიიღოთ ცოტა რუტინული, ნება მომეცით, შეაჩერონ ეს ერთი მომენტი.

632
00:37:08,750 --> 00:37:10,980
ნება მომეცით შეცვალოს სიჩქარე უნდა იყოს ბევრად უფრო სწრაფად.

633
00:37:10,980 --> 00:37:15,380
მე არ იცვლება ალგორითმი, მე უბრალოდ მიღების ანიმაცია მოხდეს სწრაფად.

634
00:37:15,380 --> 00:37:18,410
უძრავი bubble sort, იმავე ალგორითმი,

635
00:37:18,410 --> 00:37:21,910
მაგრამ ახლა ხედავთ ბევრად უფრო სწრაფად, ვიდრე ჩვენი სიტყვიერი დემონსტრაცია

636
00:37:21,910 --> 00:37:25,900
რომ ყველაზე დიდი ელემენტები მართლაც bubbling მდე დაბრუნება.

637
00:37:25,900 --> 00:37:29,860
>> როგორც განზე, ამ პატარა კვადრატების ქვედა მარცხენა და ქვედა მარჯვენა

638
00:37:29,860 --> 00:37:33,520
უბრალოდ პატარა შეგახსენებთ, თუ როგორ ბევრი შედარებები თქვენ აკეთებთ.

639
00:37:33,520 --> 00:37:37,620
მაგრამ ახლა, შეგვიძლია ფოკუსირება პირამიდის რომ აღების ფორმის, და იქ მიდის.

640
00:37:37,620 --> 00:37:41,510
ყველაზე პატარა ელემენტი მარცხენა, უმსხვილესი მარჯვენა, და ყველაფერი შორის.

641
00:37:41,510 --> 00:37:44,470
ახლა მოდით ნაცვლად შევხედოთ შერჩევის ჯიშია.

642
00:37:44,470 --> 00:37:47,260
მე ვაპირებ წავიდეთ წინ და მოხვდა Stop. ჩვენ ვაპირებთ, რომ მიიღოთ ახალი შემთხვევითი კომპლექტი ბარები.

643
00:37:47,260 --> 00:37:50,930
შერჩევა დახარისხების, გაწვევას, გადის სიაში ისევ და ისევ და ისევ,

644
00:37:50,930 --> 00:37:54,900
plucking გარეთ პატარა ელემენტს. ასე რომ აქ არის შერჩევა ჯიშია.

645
00:37:54,900 --> 00:37:58,390
როგორც ჩანს იქ ნაკლები მუშაობა ხდება ახლა, რადგან ჩვენ არ ვართ შედარებით pairwise

646
00:37:58,390 --> 00:38:02,590
მაგრამ ჩვენ უბრალოდ სახის ალუბლის კრეფა პატარა ელემენტები მარჯვნიდან მარცხნივ.

647
00:38:02,590 --> 00:38:06,890
გადადგა ძალიან ცოტა დრო, ასე რომ იქ dichotomy უკვე.

648
00:38:06,890 --> 00:38:11,820
მხოლოდ იმიტომ, რომ ალგორითმი განაცხადა მიიღოს N კვადრატში დრო, ისევე როგორც ბუშტი დალაგება

649
00:38:11,820 --> 00:38:16,100
და მოსწონს შერჩევის დალაგება, იმ მართლაც უარეს შემთხვევაში გაშვებული ჯერ.

650
00:38:16,100 --> 00:38:21,790
მაგალითად, იმ შემთხვევაში, ასე ვთქვათ, შერჩევის დახარისხების,

651
00:38:21,790 --> 00:38:27,240
მე რეალურად ვარ შერჩევის პატარა პირი და აყენებს მას აქ,

652
00:38:27,240 --> 00:38:29,620
მაშინ მე ვაკეთებ ამას კიდევ ერთხელ, მაშინ მე ვაკეთებ ამას კიდევ ერთხელ,

653
00:38:29,620 --> 00:38:32,070
მაგრამ უმნიშვნელო ოპტიმიზაციის შემეძლო მიიღოს.

654
00:38:32,070 --> 00:38:35,040
>> როგორც კი გადავიდა ნომერი 1 აქ - Sammy ამ შემთხვევაში -

655
00:38:35,040 --> 00:38:38,630
რა უნდა გავაკეთოთ, მასთან შემდგომში? >> [სტუდენტი] დატოვეს.

656
00:38:38,630 --> 00:38:40,140
დატოვეს, არა? არაფერი.

657
00:38:40,140 --> 00:38:44,310
მე არ უნდა ოდესმე გაიგო Sammy ერთხელ რადგან მე რომ შერჩეული პატარა ელემენტს

658
00:38:44,310 --> 00:38:48,580
და მას აქ, რატომ ნარჩენები დრო აპირებს ბოლომდე ჩემი მთელი სია?

659
00:38:48,580 --> 00:38:54,590
მეორე iteration ნება მომეცით რეალურად გადაადგილება მხოლოდ რიცხვი 2, მხოლოდ ნომერი 3.

660
00:38:54,590 --> 00:38:57,640
ასე რომ, რეალურად, მე არ აკეთებს N რამ N ჯერ.

661
00:38:57,640 --> 00:39:05,380
მე აკეთებდა N რამ, მაშინ N - 1 რამ, მაშინ N - 2 რამ, მაშინ N - 3 რამ,

662
00:39:05,380 --> 00:39:07,080
მაშინ N - 4, dot, dot, dot.

663
00:39:07,080 --> 00:39:09,470
ჩვენ გვყავს ცოტა გეომეტრიული სერია, რომელიც უბრალოდ ნიშნავს

664
00:39:09,470 --> 00:39:11,450
თქვენ დასძინა up თანდათანობით პატარა ნომრები.

665
00:39:11,450 --> 00:39:17,940
არ N + N + N + N მაგრამ N + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
და რა, რომ ზოგადად მუშაობს აღმოჩნდება -

667
00:39:21,380 --> 00:39:24,280
მე ვაპირებ mess up ჩემი მონიშნე აქ მხოლოდ მომენტში -

668
00:39:24,280 --> 00:39:28,990
რომ იმუშავებს აღმოჩნდება რაღაც n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
თუ ჩვენ მხოლოდ სახის შევხედოთ უკან მათემატიკის წიგნი, სადაც თქვენ ყველა მოტყუებას sheets

670
00:39:31,930 --> 00:39:33,410
ამისთვის ფორმულები.

671
00:39:33,410 --> 00:39:37,760
თუ თქვენ მხოლოდ დასძინა რაღაც N + N - 1 + N - 2, მუშაობს აღმოჩნდება მსგავსი რამ.

672
00:39:37,760 --> 00:39:42,320
და თუ ჩვენ მხოლოდ სახის გავამრავლოთ ამ გარეთ, რომ n კვადრატში მინუს N / 2.

673
00:39:42,320 --> 00:39:46,400
მე ამბობდა N კვადრატში, თუმცა, და ეს იმიტომ, რომ მე ვიყავი სახის აღების გონებრივი მალსახმობი

674
00:39:46,400 --> 00:39:51,950
რადგან რეალურად, N კვადრატში მინუს n იყოფა 2 მართლაც ჭეშმარიტი რაოდენობის ნაბიჯები

675
00:39:51,950 --> 00:39:55,510
რომ ალგორითმი მოსწონს შერჩევის დალაგების მიიღებს თუ ჩვენ მართლაც დათვლილი მდე

676
00:39:55,510 --> 00:39:58,800
ყველა იმ პარალელებისა და ყველა პატარა დატვირთული მუშაობის ვაკეთებდით.

677
00:39:58,800 --> 00:40:03,210
მაგრამ გულწრფელად ვამბობ, ერთხელ N იღებს უნდა იყოს ერთი მილიონი ან მილიარდი, რომელიც heck ზრუნავს

678
00:40:03,210 --> 00:40:07,160
თუ თქვენ აკეთებთ მილიარდი კვადრატში მინუს მილიარდი იყოფა 2?

679
00:40:07,160 --> 00:40:09,320
მილიარდი კვადრატში არის დიდი რაოდენობით.

680
00:40:09,320 --> 00:40:13,580
შეგიძლიათ მიიღოს სხვა მილიარდი გამორთვა იგი - ო. ეს არ არის ისეთი დიდი გარიგება.

681
00:40:13,580 --> 00:40:18,770
ასე უფრო დიდი ციფრები კიდევ, ნაკლებად მნიშვნელოვანია ამ ქვედა უბრძანა პირობები.

682
00:40:18,770 --> 00:40:24,230
ვინ ზრუნავს თუ დაყოფის მიერ 2 თუ თქვენ ვსაუბრობთ quadrillions ნომრები ნაბიჯები?

683
00:40:24,230 --> 00:40:29,710
>> ასე რომ ზოგადად, კომპიუტერის მეცნიერები ტენდენცია გადაყარეთ ყველაფერი მაგრამ ყველაზე დიდი ვადით,

684
00:40:29,710 --> 00:40:33,140
და ჩვენ უბრალოდ სახის გაამარტივებს მსოფლიოს და აცხადებენ, რომ ალგორითმი

685
00:40:33,140 --> 00:40:38,130
აიღო უხეშად N კვადრატში ნაბიჯები. სწორედ გაშვებული დრო ალგორითმი.

686
00:40:38,130 --> 00:40:40,760
ამიტომ ჩვენ დავბრუნდებით ამ რაღაც მომენტში გარკვეული კონკრეტული მაგალითები,

687
00:40:40,760 --> 00:40:45,940
მაგრამ ახლა, რომ სახის ინტუიციური მოტივაცია უკან მხოლოდ გამარტივების ჩვენი სამყაროს

688
00:40:45,940 --> 00:40:51,170
და ვსაუბრობთ ყველაზე მნიშვნელოვანი თვალსაზრისით, ვიდრე მისაღებად შევიდა ყველა ამ ლამაზი ფორმულები.

689
00:40:51,170 --> 00:40:53,540
ასე რომ იყო შერჩევის დალაგების, და მივიღეთ პატარა გაუმართლა იქ.

690
00:40:53,540 --> 00:40:57,360
მოდით შევხედოთ Insertion ჯიშია. ნება მომეცით წავიდეთ წინ და დავიწყოთ ამ ერთი ასევე.

691
00:40:57,360 --> 00:41:00,330
ახლა შეამჩნია ნიმუში, რომ ხდება არის პატარა სხვადასხვა,

692
00:41:00,330 --> 00:41:03,410
და დავიწყეთ ერთად შემთხვევითი რიცხვების,

693
00:41:03,410 --> 00:41:06,890
მაგრამ თუ ჩვენ რეალურად ითვლიან up რაოდენობის ნაბიჯები უარეს შემთხვევაში,

694
00:41:06,890 --> 00:41:11,070
თუ სიაში დაიწყო სრულიად სწორი მიზნით,

695
00:41:11,070 --> 00:41:13,380
ჩვენ მხოლოდ იმ n ნაბიჯები უნდა გააცნობიეროს იმდენი.

696
00:41:13,380 --> 00:41:18,240
>> მაგრამ თუ სიაში იყვნენ რეალურად უკან - მაგალითად, ამ შემთხვევაში აქ -

697
00:41:18,240 --> 00:41:23,860
მაშინ შეამჩნია ჩვენ რეალურად უნდა გავაკეთოთ ბევრი მუშაობა ამ შემთხვევაში.

698
00:41:23,860 --> 00:41:27,080
უნდა სახის გრძნობენ თქვენ მოსწონს ეს ერთი სახის სამუშაო რთული

699
00:41:27,080 --> 00:41:30,900
მიიღოს იმ პატარა ელემენტები მარცხენა, და ეს იმიტომ, რომ ჩვენ მივიღეთ უიღბლო.

700
00:41:30,900 --> 00:41:34,210
სია დალაგებულია შემთხვევით წელს საპირისპირო.

701
00:41:34,210 --> 00:41:38,110
პირიქით, ერთად Insertion დალაგების თუ ჩვენ mimic რა გავაკეთეთ ჩვენს ადამიანებში აქ

702
00:41:38,110 --> 00:41:42,670
მიერ დაწყებული ყველას დახარისხებული და შემდეგ დაიწყება, ეს საკმაოდ კარგი ალგორითმი, არა?

703
00:41:42,670 --> 00:41:45,010
უკვე, ფაქტობრივად, დახარისხებული.

704
00:41:45,010 --> 00:41:48,670
მოდით ცდილობენ შეაჯამოს ზუსტად რამდენ დროს ეს ყველაფერი ხდება ჩვენს

705
00:41:48,670 --> 00:41:52,360
შემოღების უბრალოდ ცოტა jargon ან ნოტაცია, რომ სინამდვილეში ბევრად უფრო მარტივია

706
00:41:52,360 --> 00:41:54,320
ვიდრე fanciness სახის გვთავაზობს.

707
00:41:54,320 --> 00:41:59,030
ეს რამ აქ, ამ დიდ O ეკრანზე, არის ის, რაც კომპიუტერის მეცნიერი, ზოგადად გამოიყენოთ

708
00:41:59,030 --> 00:42:03,640
აღწერისთვის უარეს შემთხვევაში გაშვებული დრო ალგორითმი.

709
00:42:03,640 --> 00:42:07,360
>> ერთხელ, რომელსაც უარეს შემთხვევაში, ეს სრულიად კონტექსტში დამოკიდებული.

710
00:42:07,360 --> 00:42:10,890
რა ვგულისხმობთ უარეს შემთხვევაში სრულიად განსხვავდება ეფუძნება პრობლემა ჩვენ ვსაუბრობთ.

711
00:42:10,890 --> 00:42:14,550
მაგრამ იმ შემთხვევაში, დახარისხება, რა ყველაზე უარესი სცენარით?

712
00:42:14,550 --> 00:42:17,860
ყველაფერი უკან, რადგან ის უბრალოდ იგრძნობა, რაც იმას ნიშნავს ბევრი სამუშაოა ჩვენთვის.

713
00:42:17,860 --> 00:42:21,330
მე jotted ქვემოთ რამდენიმე ალგორითმები, რომ ჩვენ ვნახეთ დღემდე:

714
00:42:21,330 --> 00:42:24,930
ხაზოვანი ძებნა, ორობითი ძებნა ისევე, როგორც სატელეფონო წიგნი ან ცალი ქაღალდის,

715
00:42:24,930 --> 00:42:28,960
მაშინ ბუშტი დახარისხების, შერჩევის დალაგების, და Insertion დალაგების მოსწონს დავინახეთ ჩვენს ადამიანებში,

716
00:42:28,960 --> 00:42:31,770
და შემდეგ 1 სხვა რომ საბოლოოდ აპირებს ეწოდოს შერწყმა ჯიშია.

717
00:42:31,770 --> 00:42:37,710
ასე ხაზოვანი ძიება უარეს შემთხვევაში, რამდენი ნაბიჯები სჭირდება იპოვოს ნომერი 7

718
00:42:37,710 --> 00:42:40,690
თუ არსებობს N კარები მოსწონს შონ სახიანი? >> [სტუდენტი] ნ

719
00:42:40,690 --> 00:42:44,180
ნ ამიტომ, ჩვენ ვაპირებთ დავწეროთ დიდი O of n.

720
00:42:44,180 --> 00:42:47,010
მე უბრალოდ აპირებს შეავსოთ ზოგიერთ ბლანკები. ეს არის უბრალოდ ქსელში ბლანკები.

721
00:42:47,010 --> 00:42:52,990
მაგრამ საუკეთესო შემთხვევაში ხაზოვანი ძებნა, 7 შესაძლოა ზუსტად იმ დაწყების სია,

722
00:42:52,990 --> 00:42:55,520
და შონ შესაძლოა დაიწყო ეძებს დაწყების სიაში.

723
00:42:55,520 --> 00:42:58,940
ასე რომ, თუ თქვენ იყენებთ ხაზოვანი ძებნა და მხოლოდ შემოწმების მარცხნიდან მარჯვნივ ან იქნებ მარჯვნიდან მარცხნივ -

724
00:42:58,940 --> 00:43:02,650
ისინი ექვივალენტი - საუკეთესო შემთხვევაში რამდენი ნაბიჯები შეიძლება ხაზოვანი ძებნა,

725
00:43:02,650 --> 00:43:05,550
მოსწონს შონ ს ალგორითმი, მიიღოს? მხოლოდ 1 ნაბიჯი.

726
00:43:05,550 --> 00:43:09,450
>> ამიტომ მე ვაპირებ ვთქვა, რომ არის ომეგა ნოტაცია.

727
00:43:09,450 --> 00:43:11,570
ეს არის მხოლოდ დედაქალაქში omega.

728
00:43:11,570 --> 00:43:15,000
Omega მხოლოდ sexy გზას ვამბობ, საუკეთესო შემთხვევაში ქრონომეტრაჟი.

729
00:43:15,000 --> 00:43:18,900
ასე რომ, საუკეთესო შემთხვევაში ქრონომეტრაჟი არის ერთი ნაბიჯი ან მუდმივი რიგი ზომების -

730
00:43:18,900 --> 00:43:24,270
1 ამ შემთხვევაში - მაგრამ უარეს შემთხვევაში, დიდი O, ეს არის რეალურად N ნაბიჯები.

731
00:43:24,270 --> 00:43:28,110
და ეს ერთი აქ, Theta, ჩვენ რეალურად არ აპირებს შევხედოთ ახლავე.

732
00:43:28,110 --> 00:43:30,090
ეს არ არის შესაბამისი ამ კონკრეტულ მაგალითს.

733
00:43:30,090 --> 00:43:31,990
მაგრამ ახლა მოდით შევეცადოთ ორობითი ძებნა.

734
00:43:31,990 --> 00:43:35,990
ყველაზე ცუდ შემთხვევაში ორობითი ძებნა, რამდენი ნაბიჯების იგი აპირებს მოძიების ნომერი 7

735
00:43:35,990 --> 00:43:38,340
ან რასაც ჩვენ ვეძებთ? >> [სტუდენტი] შესვლა n.

736
00:43:38,340 --> 00:43:40,980
კვლავ აპირებს შესვლა N რადგან ისევე, როგორც ალექს მიიღო უიღბლო

737
00:43:40,980 --> 00:43:44,030
როდესაც ჩვენ მართლაც მუშაობდა მეშვეობით პრობლემა მეთოდურად

738
00:43:44,030 --> 00:43:48,220
და მან ვერ ნომერი 7 სანამ ძალიან ბოლო კარი მას შევხედე,

739
00:43:48,220 --> 00:43:51,720
მიუხედავად იმისა, რომ სამართლიანობა, She Got to გადაყარეთ გარკვეული კარები გზაზე,

740
00:43:51,720 --> 00:43:56,920
ორობითი ძიება უარეს შემთხვევაში აქვს გაშვებული დროს შესვლა n.

741
00:43:56,920 --> 00:43:59,230
ისევ და ისევ, რომ საუბრობს ამ გამყოფი და დაპყრობის.

742
00:43:59,230 --> 00:44:01,140
კი მაგრამ საუკეთესო შემთხვევაში?

743
00:44:01,140 --> 00:44:04,790
და ალექსი რეალურად გამოცდილი, რომ საუკეთესო შემთხვევაში უფლება როდესაც იგი გამოვიდა სცენაზე.

744
00:44:04,790 --> 00:44:07,290
რამდენი ნაბიჯები საერთოდ რომ მიიღოს ორობითი ძებნა? >> [სტუდენტი] 1.

745
00:44:07,290 --> 00:44:09,380
1, მხოლოდ იმიტომ, რომ მან მიიღო იღბლიანი.

746
00:44:09,380 --> 00:44:12,520
მაგრამ ეს ჯარიმა, რადგან omega ეხება საუკეთესო შემთხვევაში სცენარი,

747
00:44:12,520 --> 00:44:15,770
საუკეთესო შემთხვევაში საშუალებებით, მაშინაც კი, თუ ეს მხოლოდ შემთხვევითი dumb luck.

748
00:44:15,770 --> 00:44:18,900
>> ახლა, ამ ძალიან ჩვენ ვაპირებთ მხოლოდ სახის დატოვეთ ცარიელი ახლა.

749
00:44:18,900 --> 00:44:21,010
როგორ შესახებ არის ბუშტი დალაგება?

750
00:44:21,010 --> 00:44:24,290
ყველაზე ცუდ შემთხვევაში bubble sort, ყველას არის საპირისპირო მიზნით,

751
00:44:24,290 --> 00:44:26,380
ამიტომ ჩვენ უნდა გავაკეთოთ ბევრი bubbling.

752
00:44:26,380 --> 00:44:30,190
მაგრამ რამდენი ნაბიჯების რომ აპირებს ყველაზე ცუდ შემთხვევაში? >> [სტუდენტი] N კვადრატში.

753
00:44:30,190 --> 00:44:32,550
ეს იყო N კვადრატში, რადგან თუ ფიქრობთ ამის შესახებ,

754
00:44:32,550 --> 00:44:36,410
თუ სიაში არის სრულიად უკან - 8 დასრულდა აქ, 1 არის აქ -

755
00:44:36,410 --> 00:44:40,530
როგორც რამ დაიწყება ბუშტი, ნომერი 8 აპირებს გადაადგილება ამ გზით, ამ გზით,

756
00:44:40,530 --> 00:44:44,540
ამ გზით, ამ გზით, მაგრამ სად არის ნომერი 7 ყველაზე ცუდ შემთხვევაში?

757
00:44:44,540 --> 00:44:47,720
აქ იგი ისევ იქ. ამიტომ, ჩვენ უნდა გავაკეთოთ ისევ და ისევ.

758
00:44:47,720 --> 00:44:53,190
სწორედ აქ მივიღებთ N ნაბიჯები, მაშინ N - 1 ნაბიჯები, მაშინ N - 2 Steps.

759
00:44:53,190 --> 00:44:55,960
და თუ თქვენ მიიღოს სიტყვას მისთვის - რომ თუ სახის გავამრავლოთ ის,

760
00:44:55,960 --> 00:45:00,110
ის უხეშად n კვადრატში დასასრულს რამდენიმე სხვა თვალსაზრისით, რომ ჩვენ უბრალოდ იგნორირება ახლა -

761
00:45:00,110 --> 00:45:06,890
მერე უარეს შემთხვევაში bubble sort არის n კვადრატში, მისცეს ან მიიღოს.

762
00:45:06,890 --> 00:45:09,490
მაგრამ რაც შეეხება საუკეთესო შემთხვევაში bubble sort?

763
00:45:09,490 --> 00:45:13,050
რა არის საუკეთესო შემთხვევაში სცენარი? ყველა ციფრები დალაგებულია უკვე.

764
00:45:13,050 --> 00:45:15,920
და რა იყო heuristic მე გამოიყენება, ხრიკი მე გამოიყენება,

765
00:45:15,920 --> 00:45:20,110
გააცნობიეროს, რომ გაკეთდეს არ მუშაობა და შესაბამისად მოგვიანებით შეწყვიტოს დასაწყისში?

766
00:45:20,110 --> 00:45:23,590
[სტუდენტი] შეამოწმეთ იგი ერთხელ. >> შეამოწმეთ იგი ერთხელ. მაგრამ რა იყო მე აკეთებს გზაზე?

767
00:45:23,590 --> 00:45:26,130
მე შენახვა ტრეკზე რამდენი სვოპების მივიღე.

768
00:45:26,130 --> 00:45:30,650
და მივხვდი, თუ მე არ დათვლილი ნებისმიერი სვოპების ჩემს თითებს, მაშინ მე ვაკეთებ არ მუშაობა.

769
00:45:30,650 --> 00:45:34,300
მე რა თქმა უნდა არ უნდა ვეცადოთ გავაკეთოთ არ მუშაობის ერთხელ, ასე, რომ შეიძლება უბრალოდ შეწყვიტოს.

770
00:45:34,300 --> 00:45:37,830
>> ასე რომ, საუკეთესო შემთხვევაში bubble sort, როდესაც სიაში უკვე დახარისხებული,

771
00:45:37,830 --> 00:45:41,530
რას იტყვით omega ნოტაცია არის, საუკეთესო შემთხვევაში ქრონომეტრაჟი?

772
00:45:41,530 --> 00:45:48,040
უბრალოდ n. ჩვენ უნდა გავაკეთოთ გარკვეული მუშაობა, მაგრამ ჩვენ მხოლოდ უნდა გავაკეთოთ 1 სეირნობა მისი ღირებულების სამუშაოს.

773
00:45:48,040 --> 00:45:50,490
და აქაც მე ვაპირებ დატოვეთ ეს ნაწილი ცარიელი.

774
00:45:50,490 --> 00:45:52,430
და ახლა შერჩევის ჯიშია.

775
00:45:52,430 --> 00:45:56,010
შერჩევა დალაგების ჰქონდა ჩემთვის plucking პატარა პირი ისევ და ისევ.

776
00:45:56,010 --> 00:45:58,380
და რა მივიღეთ ამბობენ გაშვებული დროს რომ იყო?

777
00:45:58,380 --> 00:46:00,590
ეს იყო N კვადრატში ყველაზე ცუდ შემთხვევაში.

778
00:46:00,590 --> 00:46:05,220
და სამწუხაროდ, საუკეთესო შემთხვევაში ის ასევე n კვადრატში

779
00:46:05,220 --> 00:46:08,840
რადგან მე არ მაქვს სახის omniscient ხედი მთელ მსოფლიოში;

780
00:46:08,840 --> 00:46:13,140
მე მხოლოდ ვიცი საფუძველზე სრული iteration, რომ მე მართლაც ნაპოვნი პატარა პირი.

781
00:46:13,140 --> 00:46:15,860
ამიტომ შერჩევას დალაგების სახის sucks ამ თვალსაზრისით,

782
00:46:15,860 --> 00:46:17,920
მაგრამ Upside არის მისი სახის ინტუიციური.

783
00:46:17,920 --> 00:46:21,470
ეს საკმაოდ ადვილი კოდი up რადგან ყველა თქვენ უნდა გააკეთოთ წერენ რამდენიმე წყობილი ამისთვის მარყუჟების,

784
00:46:21,470 --> 00:46:24,620
ტიპიურად, რომ გადის ეძებს პატარა ელემენტს

785
00:46:24,620 --> 00:46:27,840
და შემდეგ აყენებს პატარა ელემენტს, სადაც მას ეკუთვნის დასასრულს სიაში.

786
00:46:27,840 --> 00:46:29,900
ასე რომ აქაც არსებობს იქნება ვაჭრობის საგანი.

787
00:46:29,900 --> 00:46:34,440
თანხის დრო სჭირდება თქვენ ვიფიქროთ და რეალურად განვითარდეს რაღაც წერილობით კოდი

788
00:46:34,440 --> 00:46:39,460
შეიძლება ძალიან კარგად მიიღოს მეტი დრო თუ გინდათ უკეთესი ალგორითმი და სწრაფად შესრულება.

789
00:46:39,460 --> 00:46:41,780
>> მაგრამ თუ მართლაც მხოლოდ სახის კოდი რაღაც up სწრაფი და ბინძური

790
00:46:41,780 --> 00:46:45,000
და მხოლოდ სახის მიიღოს stupidest შესაძლო იდეა შეგიძლიათ წარმოიდგინოთ, რომ,

791
00:46:45,000 --> 00:46:47,580
რომ შესაძლოა თქვენ რამდენიმე წუთში კოდი, მაგრამ დიდი მონაცემები კომპლექტი

792
00:46:47,580 --> 00:46:49,580
თქვენი ალგორითმი შესაძლოა საათის გასაშვებად.

793
00:46:49,580 --> 00:46:51,690
და კიდევ მე ასპირანტურაში რომ ზოგჯერ ამ ვაჭრობის ღ.

794
00:46:51,690 --> 00:46:55,660
კარგი იქნება 3am, მე ვცდილობდი ანალიზი ზოგიერთი ძალიან დიდი მონაცემები კომპლექტი

795
00:46:55,660 --> 00:46:59,650
დაკავშირებული უსაფრთხოების კვლევის I აკეთებდა, და ეს იყო ან დახარჯავს 5 წუთი

796
00:46:59,650 --> 00:47:03,210
tweaking ჩემი პროგრამის ანალიზი მონაცემები და წასვლა სძინავთ

797
00:47:03,210 --> 00:47:08,420
ან დახარჯავს 8 საათი მისაღებად მას მხოლოდ უფლება, ასე რომ ეშვება მყისიერად და წასვლა არ სძინავთ.

798
00:47:08,420 --> 00:47:10,530
და ა.შ. იქაც ეს სახის შეგნებული გადაწყვეტილება.

799
00:47:10,530 --> 00:47:12,740
ნაკლებია განვითარების დროს, უფრო ძილის.

800
00:47:12,740 --> 00:47:14,780
In retrospect, მე ალბათ არ უნდა წაახალისოს, რომ

801
00:47:14,780 --> 00:47:19,120
როცა მიზანი აქ არის ოპტიმიზაციის ხარისხის კოდი,

802
00:47:19,120 --> 00:47:21,280
მაგრამ რომ ძალიან რეალურ ცხოვრებაში არის ძალიან გონივრული ვაჭრობის საგანი.

803
00:47:21,280 --> 00:47:25,130
ნაკლებ დროს, ნაკლებად შესრულების ან პირიქით.

804
00:47:25,130 --> 00:47:28,110
ასე რომ აქ ჩვენ საბოლოოდ მიიღოს შანსი საუბრობენ Theta.

805
00:47:28,110 --> 00:47:32,830
Theta ნოტაცია რაღაც კომპიუტერის მეცნიერები ვერ ზრდიან საუბარში

806
00:47:32,830 --> 00:47:36,160
როდესაც დიდი O და ომეგა მოხდეს იყოს იგივე.

807
00:47:36,160 --> 00:47:40,160
თქვენ ამბობთ Theta ნამდვილად გაგზავნას გაგზავნა, რომ ეს არის სახის მჭიდრო შეკრული.

808
00:47:40,160 --> 00:47:43,340
არ აქვს მნიშვნელობა თუ არა სცენარი არის კარგი ან ცუდი, ის n კვადრატში.

809
00:47:43,340 --> 00:47:46,510
ასე რომ, ეს უბრალოდ არ შეესაბამება ამ ისტორიებს აქ.

810
00:47:46,510 --> 00:47:48,560
Insertion დალაგების არის ბოლო ერთი ჩვენ შევხედეთ,

811
00:47:48,560 --> 00:47:50,830
სადაც მე უბრალოდ ჩასმა ყველას სწორი ადგილი.

812
00:47:50,830 --> 00:47:54,930
საუკეთესო შემთხვევაში რა იყო გაშვებული დრო Insertion დალაგების როგორც ვნახეთ აქ?

813
00:47:54,930 --> 00:47:57,250
[სტუდენტი] საუკეთესო შემთხვევაში? >> საუკეთესო შემთხვევაში.

814
00:47:57,250 --> 00:48:00,100
>> იგი n რადგან საუკეთესო შემთხვევაში ყველას დახარისხებული,

815
00:48:00,100 --> 00:48:02,580
და Sammy და არავინ მართლაც იძულებული იყო ყველა.

816
00:48:02,580 --> 00:48:04,610
ისინი უკვე თავიანთ ადგილას.

817
00:48:04,610 --> 00:48:08,570
ამიტომ Insertion დალაგების საუკეთესო შემთხვევაში არის, ამ შემთხვევაში, n.

818
00:48:08,570 --> 00:48:12,770
მაგრამ უარეს შემთხვევაში ეს სახის n კვადრატში. რატომ?

819
00:48:12,770 --> 00:48:16,230
თუ ჩემი სია ადამიანისა არის საპირისპირო მიზნით,

820
00:48:16,230 --> 00:48:21,260
მე პირველად იწყება ნომერი 8 და მე ჩადეთ მას სწორი პოზიცია, რომელიც სწორედ აქ.

821
00:48:21,260 --> 00:48:25,270
I ტიპის ნაბიჯი მხარეს. ეს ბიჭები არიან არასორტირებული, იგი დახარისხებული.

822
00:48:25,270 --> 00:48:28,970
მაგრამ ახლა მე ემართება ვინ შემდეგი? >> [სტუდენტი] 7.

823
00:48:28,970 --> 00:48:31,250
7 ყველაზე ცუდ შემთხვევაში იმიტომ რომ წელს საპირისპირო მიზნით.

824
00:48:31,250 --> 00:48:34,920
>> ასე რომ აქ არის 7. სად 7 ეკუთვნის? აუცილებლად ჩემს უკან.

825
00:48:34,920 --> 00:48:39,460
მაგრამ ახლა 7 რეალურად ეკუთვნის არა მაშინვე ჩემს უკან, მაგრამ უკან ნომერი 8,

826
00:48:39,460 --> 00:48:41,880
ასე უნდა ვთქვა, "ბოდიში, ნომერი 8, შეგიძლიათ გთხოვთ გადაადგილება ამ გზით

827
00:48:41,880 --> 00:48:44,640
"იმისათვის, რომ ოთახი 7?" ახლა კი ექმნებათ 6.

828
00:48:44,640 --> 00:48:48,530
"ოჰ, მაპატიეთ, ნომერი 8 და ნომერი 7, შეგიძლიათ გადაადგილება, რათა ოთახი 6?"

829
00:48:48,530 --> 00:48:52,360
ასე რომ, სხვა სიტყვებით, ერთად Insertion დახარისხების, მიუხედავად იმისა, რომ მე არ აკეთებს გაცილებით მოძრაობა,

830
00:48:52,360 --> 00:48:56,330
ხალხი ჩემს უკან ვაკეთებთ უფრო მეტს მუშაობა, და ეს მივიღე ეღირება ვინმე დრო.

831
00:48:56,330 --> 00:48:58,000
იგი აპირებს ეღირება კომპიუტერის დრო.

832
00:48:58,000 --> 00:49:01,450
ასე რომ იმ შემთხვევაში Insertion დალაგების ჩვენ კვლავ განიცდიან.

833
00:49:01,450 --> 00:49:06,260
თუ დაიწყება დასძინა up საერთო რაოდენობის ნაბიჯები, ჩვენ დასრულდება მდე hitting უხეშად N კვადრატში

834
00:49:06,260 --> 00:49:11,160
რადგან ეს ბიჭები მოგიწევთ ოთახში ადამიანის უნდა ჩამატებულია ისევ რომ სიაში.

835
00:49:11,160 --> 00:49:15,960
და ა.შ. ამ შემთხვევაში Theta მხოლოდ არ გამოიყენება კონკრეტული ამბავი ხელთ.

836
00:49:15,960 --> 00:49:21,100
ეს იყო ლამაზი და კარგი. ჩვენ გვყავს ამ 3 სხვადასხვა გზა ვსაუბრობთ ქრონომეტრაჟი.

837
00:49:21,100 --> 00:49:26,370
მაგრამ რას უნდა ნიშნავდეს რეალურად რეალური თვალსაზრისით, თუ ჩვენ რეალურად ცდილობენ კოდი up ალგორითმი?

838
00:49:26,370 --> 00:49:31,620
>> ნება მომეცით შესთავაზოს, რომ არსებობს კიდევ უკეთესი ალგორითმი არსებობს

839
00:49:31,620 --> 00:49:33,740
რომელიც თვითონ აქვს გარკვეული ვაჭრობის ღ.

840
00:49:33,740 --> 00:49:36,890
ჩვენ ვაპირებთ ეძახით შერწყმა დალაგების, და ეს ერთგვარი ამ ჯადოსნური ალგორითმი

841
00:49:36,890 --> 00:49:42,840
რომ მუშაობს სწრაფად რატომღაც, და ეს ისე ადვილია, რათა გამოხატოს მაინც, pseudocode.

842
00:49:42,840 --> 00:49:46,900
განხორციელების ამ ალგორითმის შერწყმა დალაგების იქნება შემდეგნაირად.

843
00:49:46,900 --> 00:49:50,860
როდესაც თქვენ მოცემული n ელემენტებს - N ციფრები, N ხალხს, რასაც - პირველი არსებობს საღი აზრის ქვითარი.

844
00:49:50,860 --> 00:49:56,340
თუ n ნაკლებია, ვიდრე 2, შერწყმა დალაგება მხოლოდ აჩერებს. ის დააბრუნებს, ასე ვთქვათ.

845
00:49:56,340 --> 00:50:00,830
რატომ შეწყვიტოს თუ N ნაკლებია, ვიდრე 2? >> [Inaudible სტუდენტი საპასუხოდ]

846
00:50:00,830 --> 00:50:04,480
მარჯვენა. ისევ და ისევ, N არ არის ნომერი სიაში, N არის ზომა სიაში.

847
00:50:04,480 --> 00:50:07,660
თუ n ნაკლებია, ვიდრე 2, ეს ნიშნავს, რომ თქვენი სია ან 1,

848
00:50:07,660 --> 00:50:09,640
აქ თქვენ აშკარად დალაგებულია თუ 1 ნომერი,

849
00:50:09,640 --> 00:50:11,710
ან 0, ამ შემთხვევაში არაფერი დასალაგებლად,

850
00:50:11,710 --> 00:50:13,570
ამიტომ ჩვენ გვჭირდება ასეთი ბაზის შემთხვევაში.

851
00:50:13,570 --> 00:50:20,350
თუ სიაში არის ასე მოკლე, რომ იქ უბრალოდ არაფერ შუაშია, სიტყვასიტყვით არ არაფერი. დაბრუნება.

852
00:50:20,350 --> 00:50:25,090
წინააღმდეგ შემთხვევაში დასალაგებლად მარცხენა ნახევარში ელემენტები, მაშინ დასალაგებლად მარჯვენა ნახევარში ელემენტები,

853
00:50:25,090 --> 00:50:27,410
მაშინ შერწყმა 2 დახარისხებული halves.

854
00:50:27,410 --> 00:50:32,130
>> ასეთი თითქოს პატარა cheat რომლითაც მე თქვენ გეკითხებით როგორ დასალაგებლად ელემენტები

855
00:50:32,130 --> 00:50:34,900
და თქვენ მეუბნებოდა, "Sort მარცხენა ნახევარში, დასალაგებლად მარჯვენა ნახევარში."

856
00:50:34,900 --> 00:50:37,240
მე მოსწონს, "ყველა უფლება. როგორ დასალაგებლად მარცხენა ნახევარი?"

857
00:50:37,240 --> 00:50:40,670
"Sort მარცხენა ნახევარში მარცხენა ნახევარში, დასალაგებლად მარჯვენა ნახევარში მარცხენა ნახევარში, შემდეგ გაკეთდეს."

858
00:50:40,670 --> 00:50:44,060
თქვენ სახის ციკლურად განსაზღვრის რას ნიშნავს დასალაგებლად,

859
00:50:44,060 --> 00:50:46,790
მაგრამ აღმოჩნდება, რომ სინამდვილეში ბრწყინვალე ამ შემთხვევაში.

860
00:50:46,790 --> 00:50:50,230
ეს არ არის ჭეშმარიტად ამ მანკიერი ციკლი, რომ არასოდეს მთავრდება

861
00:50:50,230 --> 00:50:52,550
იმიტომ, რომ ეს არ დასრულდება, როდესაც? >> [სტუდენტი] როდესაც თქვენ მივაღწიოთ 1 რამ.

862
00:50:52,550 --> 00:50:54,220
როდესაც თქვენ მივაღწიოთ 1 რამ.

863
00:50:54,220 --> 00:50:57,850
ასე რომ მიუხედავად იმისა, რომ თქვენ შეიძლება დაიწყოს 8 ადამიანი და მე ვიტყვი, "Sort მარცხენა ნახევარში ამ ხალხს,

864
00:50:57,850 --> 00:51:00,480
ამ 4 ადამიანი ", მაშინ მე ვიტყვი," როგორ დასალაგებლად მარცხენა ნახევარი? ​​"

865
00:51:00,480 --> 00:51:03,450
"ისე, დასალაგებლად 2 ადამიანი აქ." და მაშინ თქვენ მოსწონს, "ყველა უფლება, ჯარიმა."

866
00:51:03,450 --> 00:51:05,520
"როგორ დასალაგებლად მარცხენა ნახევარში იმ ხალხს?"

867
00:51:05,520 --> 00:51:09,040
"სამართლიანი დასალაგებლად ამ 1 ადამიანი აქ." რა არის ბრწყინვალე აღმოჩენა არის?

868
00:51:09,040 --> 00:51:13,050
მაქვს დასალაგებლად 1 ადამიანი. შესრულებულია. მე არ მაქვს რაიმე მუშაობა.

869
00:51:13,050 --> 00:51:16,580
მაგრამ ახლა უნდა დასალაგებლად ამ ადამიანს, მაგრამ ისინი ერთი ადამიანი, არაფერ შუაშია.

870
00:51:16,580 --> 00:51:21,490
>> ამიტომ Magic აშკარად არის ამ მესამე ნაბიჯი: შერწყმა დახარისხებული halves.

871
00:51:21,490 --> 00:51:25,770
ასე რომ შერწყმა დალაგების იღებს ამ ბრწყინვალე ინსაითი, რომ თუ თქვენ შესვენება დიდი პრობლემა ქვემოთ

872
00:51:25,770 --> 00:51:28,650
შევიდა 2 პატარა, იდენტურად ზომის პრობლემები

873
00:51:28,650 --> 00:51:32,710
და მაშინ უბრალოდ სახის წებო პატარა გადაწყვეტილებები ერთად დასასრულს,

874
00:51:32,710 --> 00:51:34,720
მე ვთავაზობ, რომ ჩვენ შეგვიძლია გავაკეთოთ ბევრად, ბევრად უკეთესი [მოსმენების sound]

875
00:51:34,720 --> 00:51:38,050
ვიდრე ნებისმიერი შერჩევის დალაგების ან Insertion ჯიშია.

876
00:51:38,050 --> 00:51:40,690
მე პრაქტიკულად იგნორირება, რომ ნახევარი საათის განმავლობაში, მაგრამ მე ნამდვილად არ ვიცი რა ხდება

877
00:51:40,690 --> 00:51:45,040
გარეთ დღეს. [Whirring sound] [სიცილის]

878
00:51:45,040 --> 00:51:49,660
მოდით ვნახოთ, თუ ვხედავთ ამ პატარა დახმარება ჩვენი მეგობარი რობ Bowden.

879
00:51:49,660 --> 00:51:52,810
არის 2 დიდი ნაბიჯები პროცესში შერწყმა ჯიშია.

880
00:51:52,810 --> 00:51:56,400
პირველი, განუწყვეტლივ გაყოფილი სიაში შევიდა თასები halves

881
00:51:56,400 --> 00:51:59,610
სანამ ჩვენ გვაქვს bunch of სიები მხოლოდ 1 ჭიქა მათში.

882
00:51:59,610 --> 00:52:02,150
არ ინერვიულოთ, თუ სია შეიცავს კენტი ნომერი

883
00:52:02,150 --> 00:52:04,830
და ვერ მიიღოს შესანიშნავად სუფთა cut მათ შორის.

884
00:52:04,830 --> 00:52:08,740
უბრალოდ თვითნებურად აირჩიოთ რომელიც სიაში შედის ზედმეტი თასი სისტემაში

885
00:52:08,740 --> 00:52:11,320
მოდით გაყოფილი ამ სიებში.

886
00:52:12,420 --> 00:52:14,570
ახლა ჩვენ გვაქვს 2 სიები.

887
00:52:18,930 --> 00:52:20,930
ახლა ჩვენ გვაქვს 4 სიები.

888
00:52:25,730 --> 00:52:28,740
ახლა ჩვენ გვაქვს 8 სიები ერთი ჭიქა ყოველ სიაში.

889
00:52:28,740 --> 00:52:31,520
ასე რომ ეს ნაბიჯი 1.

890
00:52:31,520 --> 00:52:37,280
ამისთვის ნაბიჯი 2 ჩვენ არაერთხელ შერწყმა წყვილი სიები გამოყენებით შერწყმა ალგორითმი გავიგეთ ადრე.

891
00:52:37,280 --> 00:52:44,320
შერწყმა 108 და 15 ჩვენ დასრულდება up ერთად სიაში 15, 108.

892
00:52:45,240 --> 00:52:51,330
შერწყმა და 50 4 ჩვენ დასრულდება up ერთად 4, 50.

893
00:52:51,330 --> 00:52:56,950
შერწყმა 8 და 42 ჩვენ დასრულდება მდე, 8, 42.

894
00:52:57,790 --> 00:53:04,360
და შერწყმის 23 და 16 ჩვენ დასრულდება მდე, 16, 23.

895
00:53:04,360 --> 00:53:08,030
ახლა ყველა ჩვენი სიები არის ზომა 2.

896
00:53:08,030 --> 00:53:10,980
გაითვალისწინეთ, რომ ყოველი 4 სიები დალაგებულია,

897
00:53:10,980 --> 00:53:14,230
ამიტომ ჩვენ შეგვიძლია დავიწყოთ შერწყმის წყვილი სიები კიდევ ერთხელ.

898
00:53:14,230 --> 00:53:22,150
შერწყმა 15 და 108 და 4 და 50 ჩვენ პირველი მიიღოს 4, შემდეგ 15,

899
00:53:22,150 --> 00:53:26,250
მაშინ 50, მაშინ 108.

900
00:53:26,250 --> 00:53:33,020
შერწყმა 8, 42 და 16, 23 ჩვენ პირველი მიიღოს 8, შემდეგ 16,

901
00:53:33,020 --> 00:53:37,170
მაშინ 23, მაშინ 42.

902
00:53:37,170 --> 00:53:42,490
ახლა ჩვენ გვაქვს მხოლოდ 2 სიები ზომა 4, რომელთაგან თითოეული დალაგებულია.

903
00:53:42,490 --> 00:53:45,940
ახლა ჩვენ შევაერთებთ ამ 2 სიები.

904
00:53:45,940 --> 00:53:54,230
პირველი ჩვენ ვიღებთ 4, მაშინ ჩვენ ვიღებთ 8, მაშინ ჩვენ ვიღებთ 15

905
00:53:54,230 --> 00:54:05,280
და 16 და 23 და 42 და 50 და 108.

906
00:54:05,280 --> 00:54:09,020
და ჩვენ გავაკეთეთ. ჩვენ ახლა აქვს დახარისხებული სია.

907
00:54:09,020 --> 00:54:13,740
>> რობ იყო სახის მიღების უპირატესობა რაღაც რომ ჩვენ ჯერ არ გაკეთებულა.

908
00:54:13,740 --> 00:54:16,540
იგი უარყო, მაგრამ ჩვენ არ რეალურად გავაკეთოთ.

909
00:54:16,540 --> 00:54:19,230
იგი აკეთებს რაღაც ფიზიკურად ერთად თასები რომ ვარაუდობს

910
00:54:19,230 --> 00:54:23,680
მას ხარჯავს ზოგიერთი რესურსის გარდა დრო. >> [სტუდენტი] ფართი. >> ეს იყო სივრცეში.

911
00:54:23,680 --> 00:54:27,360
ფაქტი, რომ მას ამ ტიპის ბი დონის მაგიდასთან, სადაც სივრცეში აქ

912
00:54:27,360 --> 00:54:31,960
და სივრცეში ქვემოთ აქ სინამდვილეში გულისხმობს, რომ ის გამოყენებით ორჯერ იმდენი სივრცე

913
00:54:31,960 --> 00:54:36,390
როგორც ჩვენს ნებისმიერ ალგორითმები დღემდე - Insertion დახარისხების, bubble sort, ან შერჩევის დალაგება -

914
00:54:36,390 --> 00:54:40,780
მაგრამ მას leveraging ამ დამატებითი ფართის სახის ნაბიჯი რამ უკან და მეოთხე

915
00:54:40,780 --> 00:54:42,600
ხოლო შენახვა რამ მიზნით.

916
00:54:42,600 --> 00:54:47,540
და მიუხედავად იმისა, რომ იგრძნობა მივიღეთ, რათა დახარისხებული სიის, რომ იგრძნო, როგორიცაა დასჭირდა ხოლო.

917
00:54:47,540 --> 00:54:51,060
სინამდვილეში, რა რობ აკეთებდა იყო ზუსტად ეს ალგორითმი.

918
00:54:51,060 --> 00:54:56,780
მან პირველი აიღო პრობლემა ზომა N, გაყოფილი ის მარცხენა ნახევარში და მარჯვენა ნახევარში.

919
00:54:56,780 --> 00:54:59,380
სწორედ მაშინ ის გადავიდა თასები. შემდეგ მან კიდევ ერთხელ გაიმეორა, რომ პროცესი.

920
00:54:59,380 --> 00:55:03,390
მან გაყოფილი 4 შევიდა 2 კომპლექტი 2 ზე აქ და აქ.

921
00:55:03,390 --> 00:55:08,520
შემდეგ მან კიდევ ერთხელ გაიმეორა, რომ პროცესი და გაყოფილი 2 შევიდა 2 კომპლექტი 1 თითოეული იმ სხვადასხვა თასები.

922
00:55:08,520 --> 00:55:11,000
სწორედ აქ ბრწყინვალე შესაძლებლობა ჩნდება.

923
00:55:11,000 --> 00:55:15,840
იმ დროისთვის ამბავი, რობ ჰქონდა 8 სიები ზომა 1,

924
00:55:15,840 --> 00:55:18,860
ყველა რომლებიც დალაგებულია უკვე.

925
00:55:18,860 --> 00:55:20,630
>> ასეა, მაშინ რა უნდოდა მას გაგრძელება უნდა გავაკეთოთ?

926
00:55:20,630 --> 00:55:25,260
Pairwise მან აიღო ეს დახარისხებული სია და ამ დახარისხებული სიის და მათ შეუერთდა.

927
00:55:25,260 --> 00:55:28,200
შემდეგ მან აიღო ეს ერთი და შეუერთდა მათ, მაშინ ეს ერთი და შეუერთდა მათ,

928
00:55:28,200 --> 00:55:30,670
მაშინ ეს ერთი და შეუერთდა მათ.

929
00:55:30,670 --> 00:55:32,390
და მერე რა ის გავაკეთოთ შემდეგი?

930
00:55:32,390 --> 00:55:36,580
შემდეგ მან ხელახლა გაერთიანდა დიდია სიები და შემდეგ ხელახლა გაერთიანდა დიდია სიები.

931
00:55:36,580 --> 00:55:41,170
და თუ ფიქრობთ ამის შესახებ მხოლოდ ინტუიციურად ახლა, რა იყო ის ნამდვილად აკეთებს?

932
00:55:41,170 --> 00:55:45,450
იგი გამყოფი პრობლემა ნახევარი, ნახევარ, ნახევარ, ნახევარ

933
00:55:45,450 --> 00:55:47,600
რათა მიიღოთ ამ სუპერ მცირე სიები.

934
00:55:47,600 --> 00:55:51,290
შემდეგ იგი იყო სახის აერთიანებს ორმაგი, ორმაგი, ორმაგი, ორმაგი.

935
00:55:51,290 --> 00:55:54,120
ასე რომ იგი აკეთებს ორჯერ კიდევ ბევრი სამუშაოა, როგორც ჩვენ ვნახეთ დღემდე

936
00:55:54,120 --> 00:55:56,930
ერთად რაც ეხება გათიშე და დაიპყროთ, მაგრამ არა დიდი გარიგება.

937
00:55:56,930 --> 00:55:59,630
ორჯერ კიდევ ბევრი სამუშაოა არ არის ასეთი დიდი გარიგება. უბრალოდ მუდმივი ფაქტორი.

938
00:55:59,630 --> 00:56:03,920
და ჰგავს ჩვენი არითმეტიკის გამოხატვის ადრე, მე უბრალოდ აპირებს გადაკვეთა გარეთ მუდმივი ფაქტორები

939
00:56:03,920 --> 00:56:10,170
მოსწონს ჯერ 2. ვინ ზრუნავს? თუ ეს 2 მილიარდობით ჯერ 2, რომ ჯერ კიდევ ბევრი ნაბიჯები.

940
00:56:10,170 --> 00:56:13,160
ასე რომ, ეს ნაბიჯი შერწყმის ჩანს გასაღები ინსაითი.

941
00:56:13,160 --> 00:56:17,000
მოდით გავლა ამ უბრალოდ რიცხობრივი ადრე - Oh, რომ არ უნდა გაგრძელდეს ამჟამად.

942
00:56:17,000 --> 00:56:22,890
მოდით გავლა ამ რიცხობრივი მხოლოდ რეალურად ვხედავ როგორ უკრავს გარეთ.

943
00:56:22,890 --> 00:56:25,940
ეს არის ძირითადად მხოლოდ პატარა ღარიბი ადამიანის ანიმაცია.

944
00:56:25,940 --> 00:56:27,750
მოდით შესთავაზოს ამ.

945
00:56:27,750 --> 00:56:31,480
გაშვებული დრო შერწყმა დალაგება - ჩვენ უბრალოდ უნდა გზა ვსაუბრობთ ამ.

946
00:56:31,480 --> 00:56:34,380
ეს არ არის მათემატიკის; ეს მხოლოდ სახის ლაკონური გზით გამოხატვის საკუთარ თავს.

947
00:56:34,380 --> 00:56:39,080
ასე T წარმოადგენს დრო და N წარმოადგენს რა? >> [სტუდენტი] ზომა -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] ზომა პრობლემა, ადამიანების რიცხვი.

949
00:56:41,400 --> 00:56:45,470
ამიტომ მე იმის თაობაზე, რომ გაშვებული დრო დასალაგებლად N ხალხი იქნება 0 დროის

950
00:56:45,470 --> 00:56:50,290
თუ n ნაკლებია, ვიდრე 2, რადგან თუ თქვენ გაქვთ 1 ჭიქა ან არა ჭიქები, თქვენ არაფერს დასალაგებლად.

951
00:56:50,290 --> 00:56:55,160
მაგრამ ზოგადად, მე ვაპირებ, რომ შესთავაზოს ქრონომეტრაჟი დასალაგებლად N ელემენტები

952
00:56:55,160 --> 00:56:59,350
იქნება დრო სჭირდება დასალაგებლად მარცხენა ნახევარში Plus მარჯვენა ნახევარში

953
00:56:59,350 --> 00:57:03,110
Plus - რა არის ეს დამატებითი + N? >> [სტუდენტი] Merge ჯიშია.

954
00:57:03,110 --> 00:57:07,260
[Malan] სინამდვილეში შერწყმის, რადგან თუ თქვენ გაქვთ N / 2 ელემენტები აქ

955
00:57:07,260 --> 00:57:11,500
და თქვენ გაქვთ N / 2 ელემენტები აქ, რამდენი დრო სჭირდება შერწყმა მათ?

956
00:57:11,500 --> 00:57:15,050
ისევე, რობ, თქვენ უნდა pluck ამ ერთი მეტი აქ, იქნებ pluck მეტი აქ,

957
00:57:15,050 --> 00:57:17,120
pluck მეტი აქ, pluck მეტი აქ, pluck მეტი აქ.

958
00:57:17,120 --> 00:57:19,400
თქვენ უნდა შეეხოთ თითოეული თასები ერთხელ.

959
00:57:19,400 --> 00:57:22,030
და თუ არსებობს 4 ჭიქა Plus 4 ჭიქა, რომ 8 თასები

960
00:57:22,030 --> 00:57:25,200
ან, უფრო ზოგადად, 8 N თასები.

961
00:57:25,200 --> 00:57:28,470
ამიტომ შერწყმის ნაბიჯი შეგვიძლია გამოვხატოთ, როგორც N,

962
00:57:28,470 --> 00:57:31,330
და რომ სიტყვასიტყვით მოიცავს რამდენჯერმე რობ ფიზიკურად შეეხო

963
00:57:31,330 --> 00:57:33,410
ერთი იმ Styrofoam თასები.

964
00:57:33,410 --> 00:57:35,850
მოდით ახლა გავაკეთოთ თვითნებური მაგალითად.

965
00:57:35,850 --> 00:57:41,850
თუ არსებობს 16 თასები, რა გაშვებული დრო დახარისხება გამოყენებით Rob-ს ალგორითმი, 16 ჭიქა?

966
00:57:41,850 --> 00:57:44,710
ეს 2 ჯერ ოდენობით დრო სჭირდება დასალაგებლად 8 თასები

967
00:57:44,710 --> 00:57:46,920
იმიტომ რომ ჩვენ გვაქვს 8 თასები აქ, 8 თასები აქ.

968
00:57:46,920 --> 00:57:51,520
არ ვიცი, რამდენ ხანს, რომ იღებს, ამიტომ ჩვენ generalizing, როგორც T მომენტისათვის.

969
00:57:51,520 --> 00:57:53,320
ვინ იცის რა არის?

970
00:57:53,320 --> 00:57:58,990
მაგრამ ახლა მე შემიძლია სახის რეკურსიული ან განმეორებით ვთხოვ იგივე კითხვა.

971
00:57:58,990 --> 00:58:01,920
რა დრო სჭირდება დასალაგებლად 8 ჭიქა?

972
00:58:01,920 --> 00:58:07,030
8 ჭიქა მე ვაპირებ ვთქვა იღებს თანხის დრო სჭირდება დასალაგებლად 4 ჭიქა Plus 4 ჭიქა,

973
00:58:07,030 --> 00:58:08,880
მაშინ შერწყმის მათი ერთად.

974
00:58:08,880 --> 00:58:13,080
სახვითი. ჩვენ მისაღებად შევიდა ციკლი უკვე. როგორ სჭირდება დასალაგებლად 4 ჭიქა?

975
00:58:13,080 --> 00:58:19,150
დრო სჭირდება დასალაგებლად 4 ჭიქა არის 2 ჭიქა Plus 2 ჭიქა დახარისხება Plus შერწყმის პროცესი.

976
00:58:19,150 --> 00:58:21,440
სახვითი. როგორ სჭირდება დასალაგებლად 2 ჭიქა?

977
00:58:21,440 --> 00:58:26,290
2 ჭიქა არის დროის სჭირდება დასალაგებლად 1 ჭიქა Plus დრო სჭირდება დასალაგებლად მეორე თასი

978
00:58:26,290 --> 00:58:29,040
პლუს თანხის დრო სჭირდება შერწყმა, რომელიც მხოლოდ 2.

979
00:58:29,040 --> 00:58:33,340
>> სახვითი. ბოლო შეკითხვა. როგორ სჭირდება დასალაგებლად 1 ჭიქა?

980
00:58:33,340 --> 00:58:37,260
აქ არის ბაზის შემთხვევაში, რომ ჩვენ იწინასწარმეტყველა ჩვენ ავღნიშნო მოხვდა ადრე.

981
00:58:37,260 --> 00:58:42,250
ფაქტი, რომ იგი იღებს არ მუშაობაში ჩაბმის დასალაგებლად პატარა პრობლემები

982
00:58:42,250 --> 00:58:44,120
ნიშნავს, რომ ახლა, ერთგვარი Grade სკოლის სტილის,

983
00:58:44,120 --> 00:58:46,460
ჩვენ შეგვიძლია უბრალოდ დაიწყოს ჩართვის ამ ნომრებზე უკან შემოსული

984
00:58:46,460 --> 00:58:50,630
ახლა ჩვენ ვიცით, რა T 1 არის, ასე, რომ შეიძლება შეაერთედ in 0 ამისთვის T 1.

985
00:58:50,630 --> 00:58:54,420
ეს ხელს მაძლევს პასუხი T 2, რომელიც მე მაშინ შეგიძლიათ შეაერთედ უმაღლეს up.

986
00:58:54,420 --> 00:58:56,930
ეს ხელს მაძლევს T, 4, რომელიც შემიძლია შეაერთედ უმაღლეს up.

987
00:58:56,930 --> 00:58:58,920
ეს ხელს მაძლევს T 8, რომელიც შემიძლია შეაერთედ უმაღლეს up.

988
00:58:58,920 --> 00:59:04,330
და თუ მართლაც, რომ მათემატიკის მიერ ჩართვის ეს პასუხები,

989
00:59:04,330 --> 00:59:08,590
მე მაშინ კიდევ T of 16 არის 64.

990
00:59:08,590 --> 00:59:12,090
და რა 64 წარმოადგენს?

991
00:59:12,090 --> 00:59:15,700
თუ T არის 16, ჰო 16 ჯერ 4.

992
00:59:15,700 --> 00:59:20,120
ასე, რომ აცხადებენ, რომ ქრონომეტრაჟი ამ რამ მოუწოდა შერწყმა დალაგება -

993
00:59:20,120 --> 00:59:22,590
და ეს იქნება fanciest of პირობა ჩვენ ვნახეთ დღემდე -

994
00:59:22,590 --> 00:59:26,160
აპირებს ეწოდოს N შესვლა N

995
00:59:26,160 --> 00:59:31,140
რადგან რამდენჯერ შეიძლება რობ გაყოფილი მთელი bunch of თასები ნახევარ? შესვლა n.

996
00:59:31,140 --> 00:59:34,370
ეს იგივეა, რაც ტელეფონის წიგნი მაგალითად, ეს იგივეა, რაც თვითმმართველობის დათვლა მაგალითად.

997
00:59:34,370 --> 00:59:36,380
>> რამდენჯერ შეგიძლიათ გაყოფა რაღაც ნახევარ?

998
00:59:36,380 --> 00:59:38,410
თუმცა, არსებობს ამ შერწყმის ნაბიჯი.

999
00:59:38,410 --> 00:59:42,920
ალბათ გაყავით ჭიქა შევიდა ნახევარი ისევ და ისევ და ისევ,

1000
00:59:42,920 --> 00:59:45,640
მაგრამ ყოველ ჯერზე, რომ თქვენ აპირებთ უნდა შერწყმა.

1001
00:59:45,640 --> 00:59:48,270
ჩვენ ცოტა ხნის წინ განაცხადა, რომ გაერთიანების N თასები იღებს N ნაბიჯები

1002
00:59:48,270 --> 00:59:52,060
იმიტომ, რომ თქვენ უნდა pluck გარეთ თასი, pluck გარეთ თასი, და თქვენ უნდა შეეხოთ ყველა თასი ერთხელ,

1003
00:59:52,060 --> 00:59:53,510
ისევე, როგორც რობ გააკეთა.

1004
00:59:53,510 --> 00:59:59,430
ასე რომ, თუ ვაკეთებთ რაღაც შესვლა N ჯერ და ვაკეთებთ N რამ თითოეულ იმ iterations,

1005
00:59:59,430 --> 01:00:03,090
თითოეული მათგანი halvings, ჩვენ გვაქვს N ჯერ შესვლა n.

1006
01:00:03,090 --> 01:00:07,220
ასე რომ, თუ ჩვენ შეაერთედ in 16 ამ მაგალითად, 16 ჯერ შეხვიდეთ of 16 -

1007
01:00:07,220 --> 01:00:10,600
არ ინერვიულოთ შესახებ, თუ რატომ არის ამ შემთხვევაში, რადგან მე არ შედგა ბაზა -

1008
01:00:10,600 --> 01:00:16,100
მაგრამ შესვლა არაძვირფასი 2 of 16 არის 4, 16 ჯერ 4 არის 64.

1009
01:00:16,100 --> 01:00:22,350
მაგრამ ამის საპირისპიროდ, თუ გვქონდა გამოყენებული bubble sort ან შერჩევის დალაგების ან Insertion დალაგების, 16 ნომრები,

1010
01:00:22,350 --> 01:00:26,420
რა ქრონომეტრაჟი არ ყოფილა, თუ N არის 16?

1011
01:00:26,420 --> 01:00:33,310
ეს იქნება 16 კვადრატში, რომელიც 256, რომელიც მაშინაც კი თუ თქვენ არ საკმაოდ მოყვება ყველა მათემატიკის,

1012
01:00:33,310 --> 01:00:38,390
256 მეტია, ვიდრე 64. რომ მართლაც ჯადოსნური takeaway აქ.

1013
01:00:38,390 --> 01:00:41,990
და გააცნობიეროს, რომ სამუშაო მეშვეობით ამ მცირე მაგალითები როგორც თქვენ ნება pset

1014
01:00:41,990 --> 01:00:44,260
ხდის ყველა ბევრად უფრო ინტუიტიური.

1015
01:00:44,260 --> 01:00:49,070
მაგრამ რა, რომ ნამდვილად ნიშნავს თვალსაზრისით შეგრძნებას ეს ალგორითმი არის ამ:

1016
01:00:49,070 --> 01:00:54,520
თუ ჩვენ რეალურად შევხედოთ შერწყმა დალაგების აქ - ნება მომეცით დახევის it up ამ ფანჯრის აქ -

1017
01:00:54,520 --> 01:00:58,560
ეს ოდნავ განსხვავებული მაგალითი, რომლითაც ჩვენ ყველანი 3 ამ ალგორითმები -

1018
01:00:58,560 --> 01:01:01,440
ბუშტი, შერჩევა, და შერწყმა - უბრალოდ თალიზში.

1019
01:01:01,440 --> 01:01:03,740
>> მათ ყველა დაიწყო შემთხვევითი ბარები, და ეგ კარგია.

1020
01:01:03,740 --> 01:01:06,240
არავის არ აქვს ფუნდამენტური უპირატესობა სხვა.

1021
01:01:06,240 --> 01:01:09,500
მე ვაპირებ წელს მომენტში დააწკაპუნეთ თითოეულ ამ ანიმაციის - დაწყება, დაწყება, დაწყება -

1022
01:01:09,500 --> 01:01:13,270
სწრაფად შემიძლია ასე რომ, უხეშად, ისინი ყველა დაწყება ამავე დროს,

1023
01:01:13,270 --> 01:01:17,450
და მოდით მიიჩნევენ, რომ ბუშტი დალაგების ს უარესი შემთხვევაში ქრონომეტრაჟი არის რა? >> [სტუდენტი] N კვადრატში.

1024
01:01:17,450 --> 01:01:21,560
N კვადრატში. შერჩევა დალაგების ს უარეს შემთხვევაში ქრონომეტრაჟი არის? N კვადრატში.

1025
01:01:21,560 --> 01:01:25,150
და შერწყმის დალაგების აშკარად - მაშინაც კი თუ თქვენ არ საკმაოდ დაიცვას ყველა მათემატიკის ახლა,

1026
01:01:25,150 --> 01:01:30,610
ეს გავხდებით ბევრად უფრო ინტუიტიური დროთა განმავლობაში - ეს არის, ჩვენ ვამბობთ,, N ჯერ შესვლა n.

1027
01:01:30,610 --> 01:01:35,210
და რადგან შესვლა N არის მკაცრად ნაკლები n ერთხელ გვაქვს დიდი ციფრები,

1028
01:01:35,210 --> 01:01:40,230
N ჯერ შესვლა N მცირეა N ჯერ n ან N კვადრატში.

1029
01:01:40,230 --> 01:01:44,410
ასე რომ რას გრძნობენ რეალურად იყოს უკეთესი ალგორითმი თვალსაზრისით ქრონომეტრაჟი,

1030
01:01:44,410 --> 01:01:50,380
N ჯერ შესვლა N ნაცვლად N კვადრატში? Here We Go. დაწკაპუნება, click, click.

1031
01:01:55,690 --> 01:01:58,650
>> სწორედ რას ნიშნავს გამოიყენოთ რაღაც შერწყმა ჯიშია.

1032
01:01:58,650 --> 01:02:01,680
ჩვენ გვყავს მომენტში. ვნახოთ რა ხდება აქ.

1033
01:02:09,440 --> 01:02:12,440
[Chuckles] ვისი ფული არის ბუშტი დალაგება?

1034
01:02:14,960 --> 01:02:16,730
ეს საკმაოდ დამოკიდებულია შეყვანის ხანდახან.

1035
01:02:16,730 --> 01:02:18,120
ვნახოთ.

1036
01:02:18,120 --> 01:02:23,320
Come on. ეს იგრძნობა ის catching up. >> [სტუდენტი] წადი, bubble sort!

1037
01:02:23,320 --> 01:02:27,370
[სტუდენტი murmuring]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Yeah, yeah.

1039
01:02:29,120 --> 01:02:34,520
[სტუდენტი murmuring] წადი, წადით, წავიდეთ!

1040
01:02:37,210 --> 01:02:40,450
[ყველა cheering] [ტაში]

1041
01:02:40,450 --> 01:02:46,240
ასე რომ ახლა 1 ბოლო, საბოლოო დემო, თუ ცოტა სახიფათო უნდა გადაიტანოთ თქვენი აზრით გარშემო მათემატიკის

1042
01:02:46,240 --> 01:02:49,280
ან სახის ვიზუალიზაცია არსებობს, თქვენ შეგიძლიათ რეალურად მოვისმინოთ სიჩქარეზე

1043
01:02:49,280 --> 01:02:51,000
სხვადასხვა ალგორითმები განსხვავებულად.

1044
01:02:51,000 --> 01:02:53,900
ეს არის ანიმაცია ვინმე გააკეთა, რომ რეალურად Associates ხმები

1045
01:02:53,900 --> 01:02:56,980
ერთად პროცესი შევცვალე და სიმაღლე ბარები.

1046
01:02:56,980 --> 01:03:00,440
როგორც ვნახავთ, აქ, იქ კიდევ რამდენიმე დახარისხება ალგორითმები out არსებობს, რომ ეგ არ მიფიქრია.

1047
01:03:00,440 --> 01:03:03,660
ეს პირველი იქნება Insertion დალაგების, და ეს იქნება ფრენა მეშვეობით

1048
01:03:03,660 --> 01:03:07,090
და მოგცემთ Audible გრძნობა როგორ შეიძლება ამ სხვადასხვა ალგორითმები მუშაობა.

1049
01:03:07,090 --> 01:03:09,080
აქ არის Insertion ჯიშია.

1050
01:03:09,080 --> 01:03:18,410
[ელექტრონული beeping]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Bubble ჯიშია.

1052
01:03:20,730 --> 01:03:46,850
[სწრაფად ელექტრონული beeping]

1053
01:03:46,850 --> 01:03:48,950
[Malan] შერჩევა ჯიშია.

1054
01:03:48,950 --> 01:04:03,580
[სწრაფად ელექტრონული beeping]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Merge ჯიშია.

1056
01:04:05,770 --> 01:04:17,270
[ელექტრონული beeping]

1057
01:04:17,270 --> 01:04:20,180
[Beeping ანელებს] [სიცილის]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome ჯიშია.

1059
01:04:22,590 --> 01:04:38,580
[ელექტრონული beeping]

1060
01:04:39,740 --> 01:04:46,150
>> ეს არის CS50. ჩვენ დავინახავთ, თქვენ მომავალ კვირას. [ტაში და cheering]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]