1
00:00:00,000 --> 00:00:04,419
>> [მუსიკის დაკვრა]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, ასე შერწყმა
დალაგების არის კიდევ ერთი ალგორითმი

4
00:00:08,460 --> 00:00:11,200
რომ ჩვენ შეგვიძლია გამოვიყენოთ დასალაგებლად out
ელემენტების მასივი.

5
00:00:11,200 --> 00:00:14,480
მაგრამ, როგორც ვნახავთ, ის მივიღე
ძალიან ფუნდამენტური განსხვავება

6
00:00:14,480 --> 00:00:17,850
საწყისი შერჩევის დალაგების, bubble
დალაგების, და Insertion დალაგების

7
00:00:17,850 --> 00:00:20,280
რომ ეს მართლაც საკმაოდ ჭკვიანი.

8
00:00:20,280 --> 00:00:24,290
>> ძირითადი იდეა უკან შერწყმა
დალაგების დასალაგებლად პატარა კოლექტორები

9
00:00:24,290 --> 00:00:27,430
და შემდეგ გავაერთიანებთ იმ მასივების
ერთად, ან შერწყმა them--

10
00:00:27,430 --> 00:00:31,440
აქედან გამომდინარე, name-- დახარისხებული მიზნით.

11
00:00:31,440 --> 00:00:34,230
ისე, რომ შერწყმა დალაგების აკეთებს
ეს არის ოპერაციული ინსტრუმენტი

12
00:00:34,230 --> 00:00:37,290
მოუწოდა უკან, რაც
ჩვენ ვაპირებთ უნდა ლაპარაკი მალე,

13
00:00:37,290 --> 00:00:39,720
მაგრამ ჩვენ ნამდვილად არ ისაუბრა არავის გაუკეთებია.

14
00:00:39,720 --> 00:00:43,010
>> აი ძირითადი იდეა უკან შერწყმა დალაგების.

15
00:00:43,010 --> 00:00:46,320
Sort მარცხენა ნახევარში მასივი,
თუ, რა თქმა n მეტია 1.

16
00:00:46,320 --> 00:00:49,980
და რას ვგულისხმობ, როცა ვამბობ,
თუ, რა თქმა n მეტია 1,

17
00:00:49,980 --> 00:00:53,970
მე ვფიქრობ, შევთანხმდებით, რომ, თუ მასივი
მხოლოდ შედგება ერთი ელემენტი,

18
00:00:53,970 --> 00:00:54,680
ეს დახარისხებული.

19
00:00:54,680 --> 00:00:56,560
ჩვენ რეალურად არ უნდა
არაფრის გაკეთება მას.

20
00:00:56,560 --> 00:00:58,059
ჩვენ შეგვიძლია მხოლოდ განაცხადოს, უნდა იყოს დახარისხებული.

21
00:00:58,059 --> 00:01:00,110
ეს მხოლოდ ერთ ელემენტს.

22
00:01:00,110 --> 00:01:03,610
>> ასე რომ, pseudocode, კიდევ ერთხელ,
დასალაგებლად მარცხენა ნახევარში მასივი,

23
00:01:03,610 --> 00:01:08,590
მაშინ დასალაგებლად მარჯვენა ნახევარში მასივი,
შემდეგ შერწყმა ორი halves ერთად.

24
00:01:08,590 --> 00:01:11,040
ახლა უკვე თქვენ შეიძლება იყოს
ფიქრობს, რომ ეს ერთგვარი მხოლოდ

25
00:01:11,040 --> 00:01:14,080
ჟღერს თქვენ აყენებს off the--
თქვენ არ რეალურად აკეთებს არაფერს.

26
00:01:14,080 --> 00:01:16,330
თქვენ ამბობთ, რომ დასალაგებლად მარცხენა
ნახევარში, დასალაგებლად მარჯვენა ნახევარში,

27
00:01:16,330 --> 00:01:19,335
მაგრამ თქვენ არ ვეუბნებით
ჩემთვის, როგორ გამოგდის.

28
00:01:19,335 --> 00:01:22,220
>> მაგრამ გახსოვდეთ, რომ მანამ, სანამ
მასივი ერთ ელემენტს,

29
00:01:22,220 --> 00:01:23,705
ჩვენ შეგვიძლია განვაცხადოთ, რომ ეს დახარისხებული.

30
00:01:23,705 --> 00:01:25,330
შემდეგ ჩვენ შეგვიძლია მხოლოდ აერთიანებს მათ ერთად.

31
00:01:25,330 --> 00:01:27,788
და ეს არის რეალურად
ძირითადი იდეა უკან შერწყმა დალაგების,

32
00:01:27,788 --> 00:01:31,150
არის შესვენება მას ისე, რომ
თქვენი კოლექტორები არის ზომა ერთი.

33
00:01:31,150 --> 00:01:33,430
და მაშინ აღვადგინოთ იქ.

34
00:01:33,430 --> 00:01:35,910
>> შერწყმა დალაგების არის ნამდვილად
რთული ალგორითმი.

35
00:01:35,910 --> 00:01:38,210
და ეს არის ასევე პატარა
რთული ვიზუალურად.

36
00:01:38,210 --> 00:01:41,870
ასე რომ, იმედია, ვიზუალიზაცია, რომ მე
აქ დაგეხმარებათ დაიცვას გასწვრივ.

37
00:01:41,870 --> 00:01:45,640
და ვეცდები ჩემი საუკეთესო ჰყვებოდა რამ
და გაგრძელება მეშვეობით ამ ცოტა მეტი

38
00:01:45,640 --> 00:01:49,180
ნელა, ვიდრე სხვა პირობა
მხოლოდ იმიტომ, რომ იმედია, თქვენი უფროსი

39
00:01:49,180 --> 00:01:51,800
გარშემო იდეები უკან შერწყმა დალაგების.

40
00:01:51,800 --> 00:01:54,680
>> ასე რომ, ჩვენ იგივე მასივი, როგორც
სხვა დახარისხება ალგორითმი ვიდეოები

41
00:01:54,680 --> 00:01:57,120
თუ ვნახე them--
ექვსი ელემენტს მასივი.

42
00:01:57,120 --> 00:02:02,110
ჩვენი pseudocode კოდი აქ არის ერთგვარი
მარცხენა ნახევარში, დასალაგებლად მარჯვენა ნახევარში,

43
00:02:02,110 --> 00:02:03,890
შერწყმა ორი halves ერთად.

44
00:02:03,890 --> 00:02:09,770
ასე რომ, მოდით ეს ძალიან მუქი წითელი აგურის
array და დასალაგებლად მარცხენა ნახევარი.

45
00:02:09,770 --> 00:02:13,380
>> ასე რომ, ამ დროისათვის, ჩვენ ვაპირებთ
იგნორირება პერსონალის უფლება.

46
00:02:13,380 --> 00:02:15,740
ის არსებობს, მაგრამ ჩვენ
არა, რომ ნაბიჯი არ არის.

47
00:02:15,740 --> 00:02:18,220
ჩვენ არ ვართ დალაგების
მარჯვენა ნახევარში მასივი.

48
00:02:18,220 --> 00:02:21,037
ჩვენ ვართ ერთგვარი მარცხენა
ნახევარში მასივი.

49
00:02:21,037 --> 00:02:22,870
და მხოლოდ გულისთვის
მიმდინარეობს ცოტა მეტი

50
00:02:22,870 --> 00:02:26,480
ნათელია, ასე რომ შემიძლია ეხება
რა ნაბიჯი ჩვენ შესახებ,

51
00:02:26,480 --> 00:02:29,800
მე ვაპირებ გადართოთ
ფერი ეს ნაკრები ფორთოხალი.

52
00:02:29,800 --> 00:02:33,190
ახლა, ჩვენ ჯერ კიდევ ვსაუბრობთ
იგივე მარცხენა ნახევარში ორიგინალური მასივი.

53
00:02:33,190 --> 00:02:38,520
მაგრამ მე იმ იმედით, რომ დგომით შეუძლია
ეხება ფერები სხვადასხვა ნივთები,

54
00:02:38,520 --> 00:02:40,900
ის, რომ მას ცოტა მეტი
გარკვევა, თუ რა ხდება აქ.

55
00:02:40,900 --> 00:02:43,270
>> OK, ასე რომ, ახლა ჩვენ გვაქვს
სამი ელემენტს მასივი.

56
00:02:43,270 --> 00:02:46,420
როგორ უნდა დაალაგოთ მარცხენა ნახევარში
მასივი, რომელიც ჯერ კიდევ ეს ნაბიჯი?

57
00:02:46,420 --> 00:02:49,400
ჩვენ ვცდილობთ, რომ დასალაგებლად მარცხენა
ნახევარი წითელი აგურის მასივი

58
00:02:49,400 --> 00:02:52,410
მარცხენა ნახევარში, რომელიც
მე ახლა ფერადი ფორთოხალი.

59
00:02:52,410 --> 00:02:54,840
>> ისე, ჩვენ შეგვიძლია ვცადოთ და
ვიმეორებ ეს პროცესი კიდევ ერთხელ.

60
00:02:54,840 --> 00:02:56,756
ასე რომ, ჩვენ ჯერ კიდევ
შუა ცდილობს დასალაგებლად

61
00:02:56,756 --> 00:02:58,700
მარცხენა ნახევარში სრული მასივი.

62
00:02:58,700 --> 00:03:00,450
მარცხენა ნახევარში
მასივი, მე უბრალოდ აპირებს

63
00:03:00,450 --> 00:03:03,910
თვითნებურად გადაწყვიტოს, რომ მარცხენა ნახევარში
იქნება ნაკლები მარჯვენა ნახევარში,

64
00:03:03,910 --> 00:03:06,550
იმიტომ, რომ ეს მოხდება
შედგება სამი ელემენტისაგან.

65
00:03:06,550 --> 00:03:11,260
>> ასე რომ, მე ვაპირებ ვთქვა, რომ
მარცხენა ნახევარში მარცხენა ნახევარში მასივი

66
00:03:11,260 --> 00:03:14,050
მხოლოდ ელემენტს ხუთ.

67
00:03:14,050 --> 00:03:18,360
ხუთი, რომ არც ერთი ელემენტი
მასივი, ჩვენ ვიცით, როგორ დასალაგებლად ის.

68
00:03:18,360 --> 00:03:21,615
ასე რომ, ხუთ დალაგებულია.

69
00:03:21,615 --> 00:03:22,990
ჩვენ უბრალოდ აპირებს განაცხადოს, რომ.

70
00:03:22,990 --> 00:03:24,890
ეს არის ერთ ელემენტს მასივი.

71
00:03:24,890 --> 00:03:29,015
>> ასე რომ, ჩვენ ახლა დახარისხებული
მარცხენა ნახევარში მარცხენა half--

72
00:03:29,015 --> 00:03:33,190
უფრო სწორად, ჩვენ დახარისხებული
მარცხენა ნახევარში ფორთოხალი.

73
00:03:33,190 --> 00:03:37,970
ასე რომ, ახლა, იმისათვის, რომ ჯერ კიდევ სრული
საერთო მასივი მარცხენა ნახევარში,

74
00:03:37,970 --> 00:03:43,481
ჩვენ უნდა დასალაგებლად მარჯვენა ნახევარში
ფორთოხალი, ან ამ პერსონალი.

75
00:03:43,481 --> 00:03:44,230
როგორ უნდა გავაკეთოთ, რომ?

76
00:03:44,230 --> 00:03:45,930
ისე, ჩვენ გვაქვს ორი ელემენტს მასივი.

77
00:03:45,930 --> 00:03:50,470
ასე რომ, ჩვენ შეგვიძლია დასალაგებლად მარცხენა ნახევარში
მასივი, რომელიც ორი.

78
00:03:50,470 --> 00:03:52,090
ორი არის ერთ ელემენტს.

79
00:03:52,090 --> 00:03:55,890
ასე რომ, ეს გადანაწილებული იყოს.
ამის შემდეგ ჩვენ შეგვიძლია დასალაგებლად მარჯვენა ნახევარში

80
00:03:55,890 --> 00:03:58,530
რომ ნაწილი მასივი, ერთი.

81
00:03:58,530 --> 00:04:00,210
სწორედ ერთგვარი იყოს.

82
00:04:00,210 --> 00:04:03,610
>> ეს არის პირველი შემთხვევა,
ჩვენ მიაღწია შერწყმა ნაბიჯი.

83
00:04:03,610 --> 00:04:06,135
ჩვენ დავასრულეთ, თუმცა
ჩვენ ახლა სახის წყობილი დანგრევა

84
00:04:06,135 --> 00:04:08,420
და რომ ერთგვარი სახიფათო
რამ უკან არის,

85
00:04:08,420 --> 00:04:10,930
თქვენ უნდა შეინახოთ თქვენი
უხელმძღვანელებს სადაც ჩვენ ვართ.

86
00:04:10,930 --> 00:04:15,560
ასე რომ, ჩვენ გვაქვს ერთგვარი მარცხენა
ნახევარი ფორთოხალი ნაწილი.

87
00:04:15,560 --> 00:04:21,280
>> და ახლა, ჩვენ შუა დახარისხება
მარჯვენა ნახევარში ფორთოხალი ნაწილი.

88
00:04:21,280 --> 00:04:25,320
და ამ პროცესში, ჩვენ ვართ
ახლა უნდა იყოს ნაბიჯი,

89
00:04:25,320 --> 00:04:27,850
შერწყმა ორი halves ერთად.

90
00:04:27,850 --> 00:04:31,700
როდესაც ჩვენ შევხედოთ ორი halves
მასივი, ჩვენ ვხედავთ, ორი და ერთი.

91
00:04:31,700 --> 00:04:33,880
რომელი ელემენტი პატარა?

92
00:04:33,880 --> 00:04:35,160
ერთ-ერთი.

93
00:04:35,160 --> 00:04:36,760
>> მაშინ რომელიც ელემენტს არის პატარა?

94
00:04:36,760 --> 00:04:38,300
ისე, ეს ორი ან არაფერი.

95
00:04:38,300 --> 00:04:39,910
ასე რომ, ეს ორი.

96
00:04:39,910 --> 00:04:43,690
ასე რომ, ახლა, უბრალოდ ერთხელ ვიზრუნოთ
სადაც ჩვენ ვართ კონტექსტში,

97
00:04:43,690 --> 00:04:48,230
ჩვენ დახარისხებული
მარცხენა ნახევარში ფორთოხალი

98
00:04:48,230 --> 00:04:49,886
და მარჯვენა ნახევარში წარმოშობის.

99
00:04:49,886 --> 00:04:52,510
მე ვიცი, მე შეცვალა ფერები
კიდევ ერთხელ, მაგრამ ეს არის ის, სადაც ჩვენ ვიყავით.

100
00:04:52,510 --> 00:04:54,676
და მიზეზი მე ეს
იმიტომ, რომ ეს პროცესი

101
00:04:54,676 --> 00:04:57,870
შენარჩუნება აპირებს, iterating ქვემოთ.

102
00:04:57,870 --> 00:05:00,500
ჩვენ დახარისხებული მარცხენა
ნახევარი ყოფილი ფორთოხალი

103
00:05:00,500 --> 00:05:02,590
და მარჯვენა ნახევარში ყოფილი ფორთოხალი.

104
00:05:02,590 --> 00:05:05,620
>> ახლა, ჩვენ უნდა შერწყმა იმ
ორი halves ერთად ძალიან.

105
00:05:05,620 --> 00:05:07,730
ეს არის ნაბიჯი ჩვენ შესახებ.

106
00:05:07,730 --> 00:05:11,440
ასე რომ, ჩვენ მიგვაჩნია, რომ ყველა
ელემენტები, რომლებიც ახლა მწვანე,

107
00:05:11,440 --> 00:05:12,972
მარცხენა ნახევარში ორიგინალური მასივი.

108
00:05:12,972 --> 00:05:14,680
და ჩვენ შერწყმა იმ
გამოყენებით იგივე პროცესი

109
00:05:14,680 --> 00:05:18,660
ჩვენ გავაკეთეთ შერწყმის ორი
და ერთი მხოლოდ ერთი წუთით წინ.

110
00:05:18,660 --> 00:05:23,080
>> მარცხენა ნახევარში, პატარა
ელემენტს მარცხენა ნახევარი ხუთ.

111
00:05:23,080 --> 00:05:25,620
პატარა ელემენტს
მარჯვენა ნახევარში ერთ-ერთი.

112
00:05:25,620 --> 00:05:27,370
რომელიც იმ არის პატარა?

113
00:05:27,370 --> 00:05:29,260
ერთ-ერთი.

114
00:05:29,260 --> 00:05:32,250
>> პატარა ელემენტს
მარცხენა ნახევარში არის ხუთ.

115
00:05:32,250 --> 00:05:35,540
პატარა ელემენტს
მარჯვენა ნახევარში ორი.

116
00:05:35,540 --> 00:05:36,970
რა არის ყველაზე პატარა?

117
00:05:36,970 --> 00:05:38,160
ორი.

118
00:05:38,160 --> 00:05:41,540
და მერე ბოლოს და ხუთ
არაფერი, ჩვენ შეგვიძლია ვთქვათ, ხუთი.

119
00:05:41,540 --> 00:05:43,935
>> OK, ასე რომ დიდი სურათი, მოდით
მიიღოს შესვენების მეორე

120
00:05:43,935 --> 00:05:46,080
და გაერკვნენ, სადაც ჩვენ ვართ.

121
00:05:46,080 --> 00:05:48,580
თუ ჩვენ დავიწყეთ
თავიდანვე, ჩვენ

122
00:05:48,580 --> 00:05:51,640
ახლა დასრულდა
საერთო მასივი მხოლოდ

123
00:05:51,640 --> 00:05:53,810
ერთი ნაბიჯი pseudocode კოდი აქ.

124
00:05:53,810 --> 00:05:56,645
ჩვენ დახარისხებული
მარცხენა ნახევარში მასივი.

125
00:05:56,645 --> 00:05:59,490
>> შეგახსენებთ, რომ ორიგინალური
იმისათვის, ხუთ, ორი, ერთი.

126
00:05:59,490 --> 00:06:02,570
გადის ეს პროცესი
და მობუდარი ქვემოთ და იმეორებს,

127
00:06:02,570 --> 00:06:05,990
გრძელდება შესვენება პრობლემა
ქვემოთ პატარა და მცირე ნაწილები,

128
00:06:05,990 --> 00:06:09,670
ჩვენ დავასრულეთ
ნაბიჯი ერთი pseudocode

129
00:06:09,670 --> 00:06:13,940
მთელი ამოსავალი მასივი.

130
00:06:13,940 --> 00:06:16,670
მოვაგვარეთ მისი მარცხენა ნახევარში.

131
00:06:16,670 --> 00:06:18,670
>> ახლა მოდით გაყინვას არსებობს.

132
00:06:18,670 --> 00:06:23,087
და ახლა მოდით დასალაგებლად მარჯვენა
ნახევარი ორიგინალური მასივი.

133
00:06:23,087 --> 00:06:25,670
ჩვენ ვაპირებთ, რომ გავაკეთოთ, რომ
გადის იგივე განმეორებითი

134
00:06:25,670 --> 00:06:30,630
პროცესის დარღვევის რამ down
და შემდეგ შერწყმის მათ ერთად.

135
00:06:30,630 --> 00:06:34,290
>> ასე რომ მარცხენა ნახევარში
წითელი, ან მარცხენა ნახევარში

136
00:06:34,290 --> 00:06:38,830
მარჯვენა ნახევარში ორიგინალური
მასივი, მე ვაპირებ ვთქვა სამი.

137
00:06:38,830 --> 00:06:40,312
ისევ და ისევ, მე, როგორც თანმიმდევრული აქ.

138
00:06:40,312 --> 00:06:42,020
თუ თქვენ გაქვთ უცნაური
რიგი ელემენტები, ის

139
00:06:42,020 --> 00:06:44,478
ნამდვილად არ აქვს მნიშვნელობა თუ არა
თქვენ მიიღოს დარჩა ერთი პატარა

140
00:06:44,478 --> 00:06:45,620
ან უფლება ერთი პატარა.

141
00:06:45,620 --> 00:06:49,230
>> ის არის, რომ, როცა
ექმნებათ ამ პრობლემის ჩატარების

142
00:06:49,230 --> 00:06:51,422
შერწყმა, თქვენ უნდა იყოს თანმიმდევრული.

143
00:06:51,422 --> 00:06:53,505
თქვენ ან ყოველთვის უნდა
მიიღოს მარცხენა მხარეს პატარა

144
00:06:53,505 --> 00:06:55,421
და ყოველთვის უნდა მიიღოს
მარჯვენა მხარეს პატარა.

145
00:06:55,421 --> 00:06:57,720
აქ, მე აირჩია, რომ ყოველთვის
რათა მარცხენა მხარეს პატარა

146
00:06:57,720 --> 00:07:04,380
როდესაც ჩემი მასივი, ან ჩემი
ქვე-მასივი, უცნაური ზომა.

147
00:07:04,380 --> 00:07:07,420
>> სამი არის ერთ ელემენტს,
და ასე რომ დალაგებულია.

148
00:07:07,420 --> 00:07:10,860
ჩვენ ჩავატარეთ, რომ ვარაუდი
მთელი ჩვენი მთელი პროცესი ჯერჯერობით.

149
00:07:10,860 --> 00:07:15,020
ახლა მოდით დასალაგებლად მარჯვენა
ნახევარი მარჯვენა ნახევარში,

150
00:07:15,020 --> 00:07:18,210
ან მარჯვენა ნახევარში წითელი.

151
00:07:18,210 --> 00:07:20,390
>> კიდევ ერთხელ, ჩვენ უნდა გაყოფილი ქვემოთ.

152
00:07:20,390 --> 00:07:21,910
ეს არ არის ერთ ელემენტს მასივი.

153
00:07:21,910 --> 00:07:23,970
ჩვენ ვერ გამოაცხადოს ის გადანაწილებული.

154
00:07:23,970 --> 00:07:27,060
ასე რომ, პირველი, ჩვენ ვაპირებთ
დასალაგებლად მარცხენა ნახევარში.

155
00:07:27,060 --> 00:07:31,620
>> მარცხენა ნახევარში არის ერთ ელემენტს,
ასე რომ, ეს არის ერთგვარი იყოს.

156
00:07:31,620 --> 00:07:34,840
მაშინ ჩვენ ვაპირებთ დასალაგებლად მარჯვენა
ნახევარი, რომელიც არის ერთ ელემენტს.

157
00:07:34,840 --> 00:07:41,250
ეს დალაგებულია იყოს. და ახლა,
ჩვენ შეგვიძლია შერწყმა ამ ორი ერთად.

158
00:07:41,250 --> 00:07:45,820
ოთხი არის პატარა და
მაშინ ექვსი პატარაა.

159
00:07:45,820 --> 00:07:48,870
>> ისევ და ისევ, რა გავაკეთეთ ამ ეტაპზე?

160
00:07:48,870 --> 00:07:52,512
ჩვენ დახარისხებული მარცხენა
ნახევარი მარჯვენა ნახევარში.

161
00:07:52,512 --> 00:07:54,720
ან ბრუნდება ორიგინალური
ფერები, რომ იქ,

162
00:07:54,720 --> 00:07:57,875
ჩვენ დახარისხებული მარცხენა
ნახევარი რბილი წითელი.

163
00:07:57,875 --> 00:08:00,416
თავდაპირველად ეს იყო მუქი აგურის
წითელი და ახლა ეს რბილი წითელი,

164
00:08:00,416 --> 00:08:02,350
თუ ეს იყო რბილი წითელი.

165
00:08:02,350 --> 00:08:05,145
>> და მაშინ ჩვენ დახარისხებული
მარჯვენა ნახევარში რბილი წითელი.

166
00:08:05,145 --> 00:08:08,270
ახლა, კარგად, ისინი მწვანე ერთხელ, მხოლოდ
იმიტომ, რომ ჩვენ ვაპირებთ მეშვეობით პროცესში.

167
00:08:08,270 --> 00:08:10,720
და ჩვენ უნდა გავიმეოროთ
მეტი და მეტი.

168
00:08:10,720 --> 00:08:14,695
>> ასე რომ, ახლა ჩვენ შეგვიძლია შერწყმა ამ
ორი halves ერთად.

169
00:08:14,695 --> 00:08:15,820
და რომ ის, რასაც ჩვენ ვაკეთებთ აქ.

170
00:08:15,820 --> 00:08:17,653
ასე რომ, შავი ხაზი მხოლოდ
იყოფა მარცხენა ნახევარში

171
00:08:17,653 --> 00:08:19,690
და მარჯვენა ნახევარში ამ სახის ნაწილი.

172
00:08:19,690 --> 00:08:24,310
>> შევადარებთ პატარა ღირებულება
მარცხენა მხარეს მასივი

173
00:08:24,310 --> 00:08:26,710
ან მაპატიეთ, პატარა
მნიშვნელობა მარცხენა ნახევარში

174
00:08:26,710 --> 00:08:30,790
რომ მცირე ღირებულების მარჯვენა
ნახევარი და ნახავთ, რომ სამი პატარა.

175
00:08:30,790 --> 00:08:32,530
ახლა ცოტა ოპტიმიზაცია, არა?

176
00:08:32,530 --> 00:08:35,175
არსებობს რეალურად არაფერი
მარცხენა მარცხენა მხარეს.

177
00:08:35,175 --> 00:08:37,440
>> არაფერია დარჩენილი
მარცხენა მხარეს,

178
00:08:37,440 --> 00:08:40,877
ასე რომ ჩვენ შეგვიძლია ეფექტურად
უბრალოდ move-- ჩვენ შეგვიძლია განვაცხადოთ,

179
00:08:40,877 --> 00:08:42,960
დანარჩენი ეს არის რეალურად
დახარისხებული და მხოლოდ Tack ეს

180
00:08:42,960 --> 00:08:45,126
, იმიტომ, რომ იქ არაფერი
სხვა შედარების წინააღმდეგ.

181
00:08:45,126 --> 00:08:49,140
ჩვენ ვიცით, რომ მარჯვენა მხარეს
მარჯვენა მხარეს არის გადანაწილებული.

182
00:08:49,140 --> 00:08:52,770
>> OK, ასე რომ, ახლა მოდით გაყინვას ერთხელ და
გაერკვნენ, სადაც ჩვენ ვართ ამბავი.

183
00:08:52,770 --> 00:08:56,120
საერთო მასივი,
რა ჩვენ დასრულებულა?

184
00:08:56,120 --> 00:08:58,790
ჩვენ რეალურად განახორციელოს
ახლა ნაბიჯები ერთი და ნაბიჯი ორი.

185
00:08:58,790 --> 00:09:03,300
ჩვენ დახარისხებული მარცხენა ნახევარში, და
ჩვენ დახარისხებული მარჯვენა ნახევარში.

186
00:09:03,300 --> 00:09:08,210
>> ახლა, ყველა რომ რჩება ჩვენთვის
შერწყმა ამ ორი halves ერთად.

187
00:09:08,210 --> 00:09:11,670
ასე რომ, ჩვენ შევადარებთ ყველაზე დაბალი ღირებულება
ელემენტის თითოეულ ნახევარში მასივი

188
00:09:11,670 --> 00:09:13,510
თავის მხრივ, და გაგრძელება.

189
00:09:13,510 --> 00:09:16,535
ერთი ნაკლებია, ვიდრე სამი, ასე რომ ერთი მიდის.

190
00:09:16,535 --> 00:09:19,770
>> ორი ნაკლებია, ვიდრე სამი, ასე ორი მიდის.

191
00:09:19,770 --> 00:09:22,740
სამი ნაკლებია, ვიდრე 5, ამიტომ სამი მიდის.

192
00:09:22,740 --> 00:09:25,820
ოთხი ნაკლებია, ვიდრე 5, ამიტომ ოთხი მიდის.

193
00:09:25,820 --> 00:09:30,210
ხუთ ნაკლებია, ვიდრე ექვსი,
და ექვსი არის ყველა, რომ რჩება.

194
00:09:30,210 --> 00:09:31,820
>> ახლა, მე ვიცი, რომ იყო ბევრი ნაბიჯები.

195
00:09:31,820 --> 00:09:33,636
და ჩვენ დაუტოვებიათ ბევრი
მეხსიერების ჩვენს გოლი.

196
00:09:33,636 --> 00:09:35,260
და რომ ის, რაც იმ ნაცრისფერი მოედნებზე.

197
00:09:35,260 --> 00:09:40,540
და ეს, ალბათ იგრძნო, როგორიცაა, რომ აიღო
ბევრი უმეტეს Insertion დალაგების, bubble

198
00:09:40,540 --> 00:09:42,660
დალაგების, ან შერჩევა ერთგვარი.

199
00:09:42,660 --> 00:09:45,330
>> მაგრამ რეალურად, იმიტომ, რომ
ბევრი ამ პროცესებში

200
00:09:45,330 --> 00:09:48,260
ხდება ამავე time--
რასაც ჩვენ გამოგიგზავნით, კიდევ ერთხელ,

201
00:09:48,260 --> 00:09:51,100
ლაპარაკი, როდესაც ჩვენ ვსაუბრობთ
უკან მომავალში ვიდეოში

202
00:09:51,100 --> 00:09:53,799
ეს ალგორითმი რეალურად
ნათლად არის ფუნდამენტურად

203
00:09:53,799 --> 00:09:55,590
განსხვავებული, ვიდრე არაფერი
ჩვენ ვნახეთ ადრე

204
00:09:55,590 --> 00:09:58,820
მაგრამ ასევე მნიშვნელოვნად
უფრო ეფექტური.

205
00:09:58,820 --> 00:09:59,532
>> რატომ არის, რომ?

206
00:09:59,532 --> 00:10:01,240
ისე, ყველაზე ცუდი
შემთხვევაში, ჩვენ გვაქვს

207
00:10:01,240 --> 00:10:04,830
გაყოფილი n ელემენტებით
და შემდეგ recombine მათ.

208
00:10:04,830 --> 00:10:06,680
მაგრამ, როდესაც ჩვენ recombine
მათ, თუ რას ვაკეთებთ

209
00:10:06,680 --> 00:10:11,110
ძირითადად გაორმაგდა
ზომა პატარა მასივები.

210
00:10:11,110 --> 00:10:14,260
ჩვენ გვყავს bunch ერთ ელემენტს
კოლექტორები რომ ჩვენ ეფექტურად

211
00:10:14,260 --> 00:10:16,290
აერთიანებს ორ ელემენტს მასივები.

212
00:10:16,290 --> 00:10:18,590
და მაშინ ჩვენ მიიღოს იმ
ორი ელემენტი კოლექტორები

213
00:10:18,590 --> 00:10:21,890
და აერთიანებს მათ ერთად
ოთხი ელემენტი მასივები, და ასე შემდეგ,

214
00:10:21,890 --> 00:10:26,130
და ასე შემდეგ, და ასე შემდეგ, სანამ ჩვენ
აქვს ერთი n ელემენტს მასივი.

215
00:10:26,130 --> 00:10:29,910
>> მაგრამ რამდენი გამეორებებები
სჭირდება მისაღებად N?

216
00:10:29,910 --> 00:10:31,460
გაიხსენეთ სატელეფონო წიგნი მაგალითად.

217
00:10:31,460 --> 00:10:34,490
რამდენჯერ ჩვენ უნდა გაანადგურეს
სატელეფონო წიგნი ნახევარი, კიდევ რამდენი

218
00:10:34,490 --> 00:10:38,370
ჯერ ჩვენ უნდა გაანადგურეს სატელეფონო წიგნი
ნახევარი, თუ ზომის სატელეფონო წიგნი

219
00:10:38,370 --> 00:10:39,680
გაორმაგდა?

220
00:10:39,680 --> 00:10:41,960
არსებობს მხოლოდ ერთი, არა?

221
00:10:41,960 --> 00:10:45,360
>> ასე რომ, არსებობს გარკვეული
ლოგარითმული ელემენტი აქ.

222
00:10:45,360 --> 00:10:48,590
მაგრამ ჩვენ ასევე ჯერ კიდევ აქვს მინიმუმ
შევხედოთ ყველა n ელემენტებს.

223
00:10:48,590 --> 00:10:53,860
ასე რომ, უარეს შემთხვევაში,
შერწყმა დალაგების ეშვება ო ჟურნალი ო.

224
00:10:53,860 --> 00:10:56,160
ჩვენ უნდა შევხედოთ
ყველა ო ელემენტები,

225
00:10:56,160 --> 00:11:02,915
და ჩვენ უნდა დააკავშიროთ მათ
ერთად log n კომპლექტი ნაბიჯები.

226
00:11:02,915 --> 00:11:05,290
საუკეთესო შემთხვევაში,
მასივი კარგად გადანაწილებული.

227
00:11:05,290 --> 00:11:06,300
სწორედ დიდი.

228
00:11:06,300 --> 00:11:09,980
მაგრამ საფუძველზე ალგორითმი გვაქვს აქ,
ჩვენ ჯერ კიდევ გვაქვს გაყოფილი და recombine.

229
00:11:09,980 --> 00:11:13,290
მიუხედავად იმისა, რომ ამ შემთხვევაში,
recombining სახის არაეფექტური.

230
00:11:13,290 --> 00:11:14,720
ეს არ არის საჭირო.

231
00:11:14,720 --> 00:11:17,580
მაგრამ ჩვენ მაინც გაიაროს
მთელი პროცესი მაინც.

232
00:11:17,580 --> 00:11:21,290
>> ასე რომ, საუკეთესო შემთხვევაში
და უარეს შემთხვევაში,

233
00:11:21,290 --> 00:11:24,970
ეს ალგორითმი ეშვება N შესვლა N დრო.

234
00:11:24,970 --> 00:11:29,130
შერწყმა დალაგების ნამდვილად ცოტა უფრო რთული
ვიდრე სხვა ძირითადი დახარისხება ალგორითმები

235
00:11:29,130 --> 00:11:33,470
ჩვენ ვისაუბრეთ CS50, მაგრამ
არსებითად უფრო ძლიერი.

236
00:11:33,470 --> 00:11:35,400
>> ასე რომ, თუ თქვენ ოდესმე
შემთხვევა სჭირდება

237
00:11:35,400 --> 00:11:38,480
ან გამოიყენოს იგი დასალაგებლად
დიდი მონაცემები კომპლექტი, მიღების

238
00:11:38,480 --> 00:11:41,940
თქვენი უფროსი გარშემო იდეა უკან
იქნება მართლაც ძლიერი.

239
00:11:41,940 --> 00:11:45,270
და ის აპირებს, რომ თქვენი
პროგრამები ნამდვილად ბევრად უფრო ეფექტური

240
00:11:45,270 --> 00:11:48,700
გამოყენებით შერწყმა დალაგების წინააღმდეგ არაფერი.

241
00:11:48,700 --> 00:11:49,640
მე Doug Lloyd.

242
00:11:49,640 --> 00:11:51,970
ეს არის CS50.

243
00:11:51,970 --> 00:11:53,826