1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [విలీనం క్రమీకరించు]

2
00:00:02,000 --> 00:00:04,000
[రాబ్ బౌడెన్ - హార్వర్డ్ యూనివర్శిటీ]

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
ఒక తప్పు ఆలోచన కేవలం ప్రతి జాబితా నుండి ప్రత్యామ్నాయ cups తీసుకోవాలని అని గమనించండి.

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
Well, ఎందుకు అని?

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
మొదటి, నిరంతరం భాగాలుగా విడదీస్తుంది cups జాబితా విభజించబడింది

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
సాంకేతిక పరంగా, విలీనం విధమైన, O (N log N) ఉంది

88
00:06:02,000 --> 00:06:07,380
బబుల్ సార్ట్, చొప్పించడం విధమైన, మరియు ఎంపిక విధమైన అన్ని O కాగా (n ²).

89
00:06:07,380 --> 00:06:11,120
మీరు వెంటనే నేర్చుకోవచ్చు నిజానికి,, మీరు ఒక విధమైన పైకి రావటానికి చెయ్యలేరు

90
00:06:11,120 --> 00:06:14,820
సాధారణ కేసులో O (N log 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
బబుల్ సార్ట్, చొప్పించడం విధమైన, మరియు ఎంపిక విధమైన సమర్థవంతంగా పడుతుంది

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
>> నా పేరు రాబ్ బౌడెన్, మరియు ఈ 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
నేను ఏమి లేదు -