1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [இணை வரிசை]

2
00:00:02,000 --> 00:00:04,000
[ராப் 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
இதுவரை நீங்கள் குமிழி வரிசையாக்கம், செருகும் வரிசையாக்கம், மற்றும் தேர்வு வகையான பார்த்திருக்கிறேன்.

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
16 மற்றும் 23 இடத்தில் இல்லை என்று அறிவிப்பு - நாம் 4, 8, 15, 23, 16 முடிவடையும் என்று செய்து.

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
நாங்கள் 2 பட்டியலை இணைத்து போது மற்றும் 4 அல்லது 8 அல்லது சிறிய உறுப்பு இருக்க வேண்டும்.

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
மற்றும் 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 கூறுகள் ஒரு வரிசையில் அதே பட்டியலில் இருந்து வந்தது என்பதை கவனியுங்கள்.

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 இங்கே 8 எங்கே n எண்கள், கொண்டுள்ளது என்று அர்த்தம்

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
முதல், தொடர்ந்து பகுதிகளாக கப் பட்டியலில் பிரிந்தது

58
00:03:41,500 --> 00:03:44,860
நாம் வெறும் 1 கப் கொண்ட பட்டியல்கள் ஒரு கொத்து வரை.

59
00:03:44,860 --> 00:03:47,350
ஒரு பட்டியல் ஒரு ஒற்றைப்படை எண் கொண்ட என்றால் கவலை வேண்டாம்

60
00:03:47,350 --> 00:03:49,880
நீங்கள் அவர்களுக்கு இடையில் ஒரு செய்தபின் சுத்தமான வெட்டு செய்ய முடியாது.

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 இணைத்தல், நாம் பட்டியலில் 15, 108 முடிவடையும்.

69
00:04:30,330 --> 00:04:36,250
50 மற்றும் 4 இணைத்தல், நாங்கள் 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
முதலில் 108, பின்னர் 50, பிறகு 15, 4 எடுத்து.

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
எனவே இப்போது நாம் அளவு 4 வெறும் 2 பட்டியல்கள் உள்ளன, ஒவ்வொன்றும் பிரிக்கப்பட்டுள்ளது.

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
தொழில்நுட்ப அடிப்படையில், ஒன்றிணைப்பு வகையான, ஓ (n log n) ஆகும்

88
00:06:02,000 --> 00:06:07,380
குமிழி வரிசையாக்கம், செருகும் வரிசையாக்கம், மற்றும் தேர்ந்தெடுக்கப்பட்ட வரிசையாக்க அனைத்து ஓ என்பவை (n ²).

89
00:06:07,380 --> 00:06:11,120
நீங்கள் விரைவில் அறியலாம் என உண்மையில், நீங்கள் ஒரு வகையான கொண்டு வர முடியாது

90
00:06:11,120 --> 00:06:14,820
என்று பொது வழக்கில் ஓ (n log n) விட சிறப்பாக செயல்படுகிறது.

91
00:06:14,820 --> 00:06:19,120
நீங்கள் இன்னும் அதை பார்க்கவில்லை என்றால், மீண்டும், இந்த பெரிய ஓ குறிமானம் பற்றி கவலைப்பட வேண்டாம்.

92
00:06:19,120 --> 00:06:23,490
>> நாங்கள் ஒரு பெரிய பட்டியல் வரிசைப்படுத்த வேண்டும் என்றால் இந்த பொருள் என்று

93
00:06:23,490 --> 00:06:26,820
குமிழி வரிசையாக்கம், செருகும் வரிசையாக்கம், மற்றும் தேர்வு வகையான திறன் ஆகலாம்

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
எடுத்துக்காட்டாக, செருகும் வரிசையாக்கம் 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
நாம் இன்னும் இணைக்கப்பட்டது வேண்டும் என்று கூறுகள் புறக்கணிக்க என்பதால்.

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
இடது பட்டியல். ஒரு எழுத்துப்பிழையா இருந்தது.

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
நான் என்ன தெரியாது -