1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [შერწყმა დალაგების]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - ჰარვარდის უნივერსიტეტი]

3
00:00:04,000 --> 00:00:07,000
[ეს არის CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
ვისაუბროთ იმაზე შერწყმა ჯიშია.

5
00:00:09,000 --> 00:00:14,000
ჯერჯერობით თქვენ ვხედავთ bubble sort, Insertion დალაგების, და შერჩევის ჯიშია.

6
00:00:14,000 --> 00:00:17,000
მიუხედავად იმისა, რომ მე სახის ტალღა ჩემი ხელი რას ვგულისხმობ მიერ უკეთესი,

7
00:00:17,000 --> 00:00:21,000
შერწყმა დალაგების ზოგადად ასრულებს უკეთესი, ვიდრე ნებისმიერი ამ 3 სახეობის.

8
00:00:22,000 --> 00:00:27,000
>> მაგრამ სანამ საუბარს შერწყმა დახარისხების, ვისაუბროთ იმაზე შერწყმის 2 დახარისხებული სიები.

9
00:00:27,000 --> 00:00:31,000
ჩვენ მოვუწოდებთ პროცესში აღების 2 დახარისხებული სიები, ისევე როგორც ეს,

10
00:00:31,000 --> 00:00:35,000
და მიღების ერთჯერადი დახარისხებული სიის აქედან - შერწყმის სიები.

11
00:00:35,000 --> 00:00:37,750
როგორ შეგვიძლია ამის გაკეთება?

12
00:00:37,750 --> 00:00:41,290
ისე, ერთი იდეა არის ის, რომ მხოლოდ გამყარებაში ერთი სიაში გადატანა ბოლომდე სხვა სიაში

13
00:00:41,290 --> 00:00:43,830
და შემდეგ დასალაგებლად შედეგად სიაში.

14
00:00:43,830 --> 00:00:47,220
>> თუმცა ეს სამუშაოები, ეს ბევრი ზედმეტი მუშაობა.

15
00:00:47,220 --> 00:00:49,900
ჩვენ შეგვიძლია ამის გაკეთება სწრაფად, ვიდრე უბრალოდ დახარისხება.

16
00:00:49,900 --> 00:00:54,100
გაითვალისწინეთ, რომ ერთი არასწორი იდეა, რომ მხოლოდ მიიღოს ალტერნატიული თასები თითოეული სიაში.

17
00:00:54,100 --> 00:00:56,460
მიუხედავად იმისა, რომ ჩანდეს, როგორიცაა, რომ სამუშაოების პირველი,

18
00:00:56,460 --> 00:01:05,760
აკეთებს, რომ ჩვენ დასრულდება მდე მქონე 4, 8, 15, 23, 16 - ცნობა 16 და 23 გამოსულია ადგილი.

19
00:01:05,760 --> 00:01:09,380
ეს იმიტომ რომ 2 ელემენტს, რომლებიც უნდა გამოჩნდეს თანმიმდევრული შერწყმული სია

20
00:01:09,380 --> 00:01:11,720
რომლებიც არიან იგივე საწყის სიაში.

21
00:01:11,720 --> 00:01:14,850
ორივე 15 და 16 არიან სიაში მარცხენა.

22
00:01:14,850 --> 00:01:19,810
ხრიკი არის ისარგებლოს იმ ფაქტს, რომ ორივე სიები უკვე დახარისხებული.

23
00:01:19,810 --> 00:01:23,320
ეს ნიშნავს, რომ თუ ჩვენ შევჩერდეთ პირველი ელემენტები ორივე სიები -

24
00:01:23,320 --> 00:01:29,580
აქ, 4 და 8 - ერთი მათგანი უნდა იყოს პირველ ელემენტს შერწყმული სიაში.

25
00:01:29,580 --> 00:01:31,620
ისე, რატომ არის, რომ?

26
00:01:31,620 --> 00:01:33,520
ორივე ეს სიები უკვე დახარისხებული,

27
00:01:33,520 --> 00:01:38,410
და ა.შ. ან 4 ან 8 უნდა იყოს პატარა ელემენტს, როდესაც ჩვენ დააკავშიროთ 2 სიები.

28
00:01:38,410 --> 00:01:41,770
ამ შემთხვევაში, ყველაზე პატარა არის 4,

29
00:01:41,770 --> 00:01:46,370
ამიტომ ჩვენ შეგვიძლია აიღოს 4 და გახდეს პირველი ელემენტს ჩვენი შერწყმული სიაში.

30
00:01:46,370 --> 00:01:50,710
ახლა ჩვენ გავაგრძელებთ შერწყმის დარჩენილი 3 ელემენტები პირველი სიაში

31
00:01:50,710 --> 00:01:52,920
და 4 ელემენტები მეორე სიაში.

32
00:01:52,920 --> 00:01:57,150
>> კიდევ ერთხელ, ჩვენ მხოლოდ უნდა შევხედოთ პირველი ელემენტს ორივე სიები.

33
00:01:57,150 --> 00:02:01,060
პატარა საქართველოს 2 უნდა იყოს მეორე ელემენტს ჩვენი შერწყმული სიაში.

34
00:02:01,060 --> 00:02:05,440
ამჯერად შორის 8 და 15 პატარა არის 8, და ამიტომ ჩვენ ჩადეთ რომ

35
00:02:05,440 --> 00:02:09,240
როგორც მეორე ელემენტს ჩვენი დახარისხებული სია.

36
00:02:09,240 --> 00:02:12,180
ჩვენ შეგვიძლია გავაგრძელოთ შედარებით პირველი ელემენტები ორივე სიები

37
00:02:12,180 --> 00:02:14,420
და მოხსნის პატარა of 2.

38
00:02:14,420 --> 00:02:19,460
შედარება 15 და 23, 15 პატარაა და ისე, რომ ჩვენი მესამე ელემენტს.

39
00:02:21,000 --> 00:02:23,910
ახლა შედარებით 16 და 23, 16 პატარაა.

40
00:02:23,910 --> 00:02:26,820
ასე რომ მეოთხე ელემენტს.

41
00:02:26,820 --> 00:02:30,390
>> გაითვალისწინეთ, რომ 2 ელემენტები მოვიდა იმავე სიაში in a row.

42
00:02:30,390 --> 00:02:34,400
ამიტომ გაერთიანებული სიაში არ შეუძლიათ უბრალოდ ალტერნატიული ელემენტების 2 სიები.

43
00:02:34,400 --> 00:02:40,020
შედარება 50 და 23, 23 პატარაა, ამიტომ ვირჩევთ რომ.

44
00:02:40,770 --> 00:02:44,070
შორის 50 და 42, 42 პატარაა.

45
00:02:44,070 --> 00:02:48,290
შორის 50 და 108, 50 პატარაა.

46
00:02:48,290 --> 00:02:52,330
და ბოლოს, ჩვენ უბრალოდ უნდა 108, ასე რომ უნდა წავიდეს წლის ბოლომდე ჩვენს სიაში.

47
00:02:53,750 --> 00:02:56,180
გაითვალისწინეთ, რომ ჩვენ გვაქვს ლამაზი, დახარისხებული სია.

48
00:02:56,180 --> 00:02:59,040
ყოველ ჯერზე ჩვენ შედარებით პირველი 2 ელემენტები 2 სიები

49
00:02:59,040 --> 00:03:02,730
ჩვენ შევძელით, რათა დადგინდეს შემდეგი ელემენტს შერწყმული სიაში.

50
00:03:02,730 --> 00:03:08,070
ეს ნიშნავს, რომ თუ საბოლოო სია შეიცავს N ნომრები, სადაც n აქ არის 8,

51
00:03:08,070 --> 00:03:12,610
მაშინ ჩვენ გვჭირდება საუკეთესო N შედარებები მისაღებად ყველა იმ ნომრები სწორი ადგილი.

52
00:03:13,230 --> 00:03:16,230
ასეთი ალგორითმი განაცხადა გასაშვებად წელს ხაზოვანი დროს,

53
00:03:16,230 --> 00:03:18,090
მაგრამ არ ინერვიულოთ შესახებ, რომ აქ.

54
00:03:18,570 --> 00:03:22,810
>> ჩვენი ალგორითმი შერწყმის, შეიძლება გავაკეთოთ სწრაფი შერწყმა დახარისხების ალგორითმი.

55
00:03:22,810 --> 00:03:25,170
ასე რომ, მოდით აღადგინოთ ჩვენი სიები.

56
00:03:35,210 --> 00:03:37,750
არის 2 დიდი ნაბიჯები პროცესში შერწყმა ჯიშია.

57
00:03:37,750 --> 00:03:41,500
პირველი, განუწყვეტლივ გაყოფილი სიაში შევიდა თასები halves

58
00:03:41,500 --> 00:03:44,860
სანამ ჩვენ გვაქვს bunch of სიები მხოლოდ 1 ჭიქა მათში.

59
00:03:44,860 --> 00:03:47,350
არ ინერვიულოთ, თუ სია შეიცავს კენტი ნომერი

60
00:03:47,350 --> 00:03:49,880
და ვერ მიიღოს შესანიშნავად სუფთა cut მათ შორის.

61
00:03:49,880 --> 00:03:53,750
უბრალოდ თვითნებურად აირჩიოთ რომელიც სიაში შედის ზედმეტი თასი სისტემაში

62
00:03:53,750 --> 00:03:56,240
ასე რომ, მოდით, გაყოფილი ამ სიებში.

63
00:03:58,140 --> 00:04:01,310
ახლა ჩვენ გვაქვს 2 სიები.

64
00:04:04,120 --> 00:04:06,570
ახლა ჩვენ გვაქვს 4 სიები.

65
00:04:10,350 --> 00:04:13,870
>> და ახლა ჩვენ გვაქვს 8 სიები ერთი ჭიქა ყოველ სიაში.

66
00:04:13,870 --> 00:04:16,630
ასე რომ ეს ნაბიჯი 1.

67
00:04:16,630 --> 00:04:22,230
ამისთვის ნაბიჯი 2, ჩვენ არაერთხელ შერწყმა წყვილი სიები გამოყენებით შერწყმა ალგორითმი გავიგეთ ადრე.

68
00:04:22,230 --> 00:04:29,160
შერწყმა 108 და 15, ჩვენ დასრულდება up ერთად სიაში 15, 108.

69
00:04:30,330 --> 00:04:36,250
შერწყმა და 50 4, ჩვენ დასრულდება up ერთად 4, 50.

70
00:04:36,960 --> 00:04:41,400
შერწყმა 8 და 42 ჩვენ დასრულდება მდე, 8, 42.

71
00:04:42,790 --> 00:04:48,130
და შერწყმის 23 და 16, ჩვენ დასრულდება მდე, 16, 23.

72
00:04:49,740 --> 00:04:52,450
ახლა ყველა ჩვენი სიები არის ზომა 2.

73
00:04:53,020 --> 00:04:56,180
გაითვალისწინეთ, რომ ყოველი 4 სიები დალაგებულია.

74
00:04:56,180 --> 00:04:59,160
>> ასე რომ ჩვენ შეგვიძლია დავიწყოთ შერწყმის წყვილი სიები კიდევ ერთხელ.

75
00:04:59,160 --> 00:05:03,240
შერწყმა 15 და 108 და 4 და 50 -

76
00:05:03,240 --> 00:05:11,170
პირველი მიიღოს 4, შემდეგ 15, მაშინ 50, მაშინ 108.

77
00:05:11,170 --> 00:05:15,120
შერწყმა 8, 42 და 16, 23,

78
00:05:15,120 --> 00:05:22,440
ჩვენ პირველი მიიღოს 8, შემდეგ 16, მაშინ 23, მაშინ 42.

79
00:05:22,440 --> 00:05:27,370
ახლა ჩვენ გვაქვს მხოლოდ 2 სიები ზომა 4, რომელთაგან თითოეული დალაგებულია.

80
00:05:27,370 --> 00:05:30,980
ახლა ჩვენ შევაერთებთ ამ 2 სიები.

81
00:05:30,980 --> 00:05:33,440
პირველი ჩვენ ვიღებთ 4.

82
00:05:33,440 --> 00:05:36,580
მაშინ ჩვენ ვიღებთ 8.

83
00:05:36,580 --> 00:05:50,700
მაშინ ჩვენ ვიღებთ 15 და 16, მერე 23, მერე 42, მერე 50, მერე 108.

84
00:05:50,700 --> 00:05:52,220
და ჩვენ გავაკეთეთ.

85
00:05:52,220 --> 00:05:54,900
ჩვენ ახლა აქვს დახარისხებული სია.

86
00:05:54,900 --> 00:05:57,890
ასე რომ რამდენად სწრაფად იყო ეს ზუსტად?

87
00:05:57,890 --> 00:06:02,000
ტექნიკური თვალსაზრისით, შერწყმა დალაგების არის O (N შესვლა N),

88
00:06:02,000 --> 00:06:07,380
ხოლო ყველა bubble sort, Insertion დალაგების, და შერჩევის დალაგების are O (N ²).

89
00:06:07,380 --> 00:06:11,120
სინამდვილეში, როგორც თქვენ შეიტყობს, თქვენ ვერ შეძლებთ ამუშავება დალაგება

90
00:06:11,120 --> 00:06:14,820
რომელიც ახორციელებს უკეთესად O (N შესვლა N) ზოგად შემთხვევაში.

91
00:06:14,820 --> 00:06:19,120
ერთხელ, არ ინერვიულოთ შესახებ დიდი O ნოტაცია თუ არ მინახავს ეს არავის გაუკეთებია.

92
00:06:19,120 --> 00:06:23,490
>> უბრალოდ ვიცი, რომ ეს იმას ნიშნავს, თუ გვინდოდა დასალაგებლად მართლაც დიდი სია

93
00:06:23,490 --> 00:06:26,820
bubble sort, Insertion დალაგების, და შერჩევის დალაგების შესაძლოა მიიღოს

94
00:06:26,820 --> 00:06:29,500
მნიშვნელოვნად აღემატება შერწყმა ჯიშია.

95
00:06:29,500 --> 00:06:33,210
ეს არ ნიშნავს, რომ შერწყმა დალაგების იქნება უფრო სწრაფად ყველა სიები

96
00:06:33,210 --> 00:06:36,220
ან თუნდაც ნებისმიერი ერთიანი სია ქვეშ გარკვეული ზომით.

97
00:06:36,220 --> 00:06:41,950
მაგალითად, Insertion დალაგება შეიძლება იყოს უსწრაფესი დალაგების ყველა სიები ნაკლებია 5 ელემენტებს.

98
00:06:41,950 --> 00:06:47,360
პრაქტიკაში, შერწყმა დალაგების ჩვეულებრივ სწრაფად ამისთვის სიები როგორც პატარა, როგორც 50 ელემენტებს.

99
00:06:47,360 --> 00:06:51,120
>> მაგრამ ეს ზედმეტი სიჩქარე არ მოდის გარეშე ფასი.

100
00:06:51,120 --> 00:06:54,770
განსხვავებით ჩვენი სხვა სახის, რომლებიც სიაში და ცვლილებები სიაში ადგილი

101
00:06:54,770 --> 00:06:58,740
სანამ არ მივიღებთ დახარისხებული სია, შერწყმა დალაგების საჭიროებს დამატებით სივრცეში

102
00:06:58,740 --> 00:07:00,900
შერწყმა 2 სიების ერთად.

103
00:07:00,900 --> 00:07:04,690
ჩვენ არ შეგვიძლია დაუყოვნებლივ გამოიყენოთ სიები, რომლებიც გაერთიანდა შესანახად გაერთიანებული სიაში

104
00:07:04,690 --> 00:07:08,880
რადგან ჩვენ შეიძლება override ელემენტს, რომლებიც ჯერ კიდევ გაერთიანდა.

105
00:07:08,880 --> 00:07:13,540
ეს სივრცე ცოტა ფასი, მაგრამ ეს, როგორც წესი, არ არის დაუსაბუთებელი.

106
00:07:13,540 --> 00:07:15,330
სწორედ ეს შერწყმა ჯიშია.

107
00:07:15,330 --> 00:07:18,490
>> ჩემი სახელი არის რობ Bowden, და ეს არის CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- და შერჩევის ჯიშია.

110
00:07:24,000 --> 00:07:25,880
[იცინის]

111
00:07:25,880 --> 00:07:31,480
ოჰ, მივიღე მიიღოს, რომ რადგან მე გადაირთვება როგორ ვიყავი წარდგენა.

112
00:07:31,480 --> 00:07:35,680
სია მარცხენა. ეს იყო typo.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] მე ბრალია -

114
00:07:39,290 --> 00:07:41,190
[იცინის]

115
00:07:41,190 --> 00:07:44,190
მე არ ვიცი, რა -