1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Bashkojë Rendit]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Universiteti i Harvardit]

3
00:00:04,000 --> 00:00:07,000
[Kjo është CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Le të flasim për lloj bashkohen.

5
00:00:09,000 --> 00:00:14,000
Deri tani ju kam parë lloj flluskë, lloj lloj futje, dhe përzgjedhjes.

6
00:00:14,000 --> 00:00:17,000
Edhe pse unë do lloj vale dorën time në atë që dua të them me të mirë,

7
00:00:17,000 --> 00:00:21,000
bashkojë lloj përgjithësi kryen më mirë se ndonjë nga këto 3 terezi.

8
00:00:22,000 --> 00:00:27,000
>> Por, para se të flasim për lloj bashkojë, le të flasim për bashkimin 2 listat e renditura.

9
00:00:27,000 --> 00:00:31,000
Ne do të thërrasë në procesin e marrjes së 2 lista të renditura, si këto,

10
00:00:31,000 --> 00:00:35,000
dhe duke e bërë një listë të vetme zgjidhet prej tyre - bashkimin e listave.

11
00:00:35,000 --> 00:00:37,750
Si mund ta bëjë këtë?

12
00:00:37,750 --> 00:00:41,290
E pra, një ide është që të rrinë vetëm një listë të mbyllet në fund të listës të tjera

13
00:00:41,290 --> 00:00:43,830
dhe pastaj lloj listën rezulton.

14
00:00:43,830 --> 00:00:47,220
>> Ndërsa kjo punon, kjo është një punë shumë e panevojshme.

15
00:00:47,220 --> 00:00:49,900
Ne mund të bëjmë atë më shpejt se vetëm zgjidhja.

16
00:00:49,900 --> 00:00:54,100
Vini re se një ide e gabuar është që të marrë vetëm gota alternuara nga çdo listë.

17
00:00:54,100 --> 00:00:56,460
Ndërkohë që mund të duket si që punon në fillim,

18
00:00:56,460 --> 00:01:05,760
duke bërë që ne të përfundojnë me 4, 8, 15, 23, 16 - njoftim se 16 dhe 23 janë jashtë vendit.

19
00:01:05,760 --> 00:01:09,380
Kjo është për shkak se 2 elemente që duhet të paraqiten njëpasnjëshëm në listën e bashkuar

20
00:01:09,380 --> 00:01:11,720
janë në të njëjtën listë fillestare.

21
00:01:11,720 --> 00:01:14,850
Të dyja 15 dhe 16 janë në lista në të majtë.

22
00:01:14,850 --> 00:01:19,810
Qëllimi është që të përfitojnë nga fakti se të dyja janë të renditura listat tashmë.

23
00:01:19,810 --> 00:01:23,320
Kjo do të thotë se në qoftë se ne vetëm shikojmë në elementet e para të dy listat -

24
00:01:23,320 --> 00:01:29,580
këtu, 4 dhe 8 - një prej tyre duhet të jetë gjithashtu elementi i parë i lista bashkuar.

25
00:01:29,580 --> 00:01:31,620
E pra, pse është kjo?

26
00:01:31,620 --> 00:01:33,520
Të dyja këto lista janë të renditura tashmë,

27
00:01:33,520 --> 00:01:38,410
dhe kështu ose 4 ose 8 duhet të jetë elementi më i vogël, kur ne kombinojnë 2 listat.

28
00:01:38,410 --> 00:01:41,770
Në këtë rast, më i vogli është 4,

29
00:01:41,770 --> 00:01:46,370
kështu që ne mund të merrni nga 4 dhe të bëjë atë elementi i parë i listës sonë bashkuar.

30
00:01:46,370 --> 00:01:50,710
Tani ne vazhdojmë bashkimin e mbetura 3 elementet e listës parë

31
00:01:50,710 --> 00:01:52,920
dhe 4 elementet e listës së dytë.

32
00:01:52,920 --> 00:01:57,150
>> Edhe njëherë, ne vetëm duhet të shikoni në elementin e parë të dyja listat.

33
00:01:57,150 --> 00:02:01,060
Sa më i vogël i 2 duhet të jetë elementi i dytë i listës sonë bashkuar.

34
00:02:01,060 --> 00:02:05,440
Këtë herë, në mes 8 dhe 15 më i vogli është 8, dhe kështu që ne të futur që

35
00:02:05,440 --> 00:02:09,240
si elementin e dytë të listës sonë renditura.

36
00:02:09,240 --> 00:02:12,180
Ne mund të vazhdojmë duke krahasuar elementet e para të të dyja listat

37
00:02:12,180 --> 00:02:14,420
dhe largimin e vogël e 2.

38
00:02:14,420 --> 00:02:19,460
Krahasimi 15 dhe 23, 15 është më i vogël dhe kështu kjo është elementi ynë i tretë.

39
00:02:21,000 --> 00:02:23,910
Tani duke krahasuar 16 dhe 23, 16 është më i vogël.

40
00:02:23,910 --> 00:02:26,820
Pra, kjo është elementi i katërt.

41
00:02:26,820 --> 00:02:30,390
>> Vini re se 2 elemente erdhi nga lista njëjtë në një rresht.

42
00:02:30,390 --> 00:02:34,400
Kjo është arsyeja pse lista bashkuar nuk mund vetëm elemente alternative nga 2 listave.

43
00:02:34,400 --> 00:02:40,020
Krahasimi 50 dhe 23, 23 është më i vogël, kështu që ne të zgjedhin atë.

44
00:02:40,770 --> 00:02:44,070
Midis 50 dhe 42, 42 është më i vogël.

45
00:02:44,070 --> 00:02:48,290
Midis 50 dhe 108, 50 është më i vogël.

46
00:02:48,290 --> 00:02:52,330
Dhe, së fundi, ne vetëm kemi 108, kështu që ajo duhet të shkojë në fund të listës sonë.

47
00:02:53,750 --> 00:02:56,180
Vini re se ne kemi një listë të bukur, të renditura.

48
00:02:56,180 --> 00:02:59,040
Çdo herë kemi krahasuar para 2 elementet e listave 2

49
00:02:59,040 --> 00:03:02,730
ne ishim në gjendje për të përcaktuar elementin tjetër të listës bashkuar.

50
00:03:02,730 --> 00:03:08,070
Kjo do të thotë se në qoftë se lista përfundimtare përmban numrat n, ku n këtu është 8,

51
00:03:08,070 --> 00:03:12,610
atëherë ne kemi nevojë më në krahasimet n të marrë të gjitha ato numra në vendin e duhur.

52
00:03:13,230 --> 00:03:16,230
Tillë një algoritmi është thënë për të kandiduar në kohë lineare,

53
00:03:16,230 --> 00:03:18,090
por mos u bëni merak për këtë këtu.

54
00:03:18,570 --> 00:03:22,810
>> Duke përdorur algorithm tonë për bashkimin, ne mund të bëjë një algoritmi të shpejtë bashkojë renditjes.

55
00:03:22,810 --> 00:03:25,170
Pra, le të rivendosur listat tona.

56
00:03:35,210 --> 00:03:37,750
Ka 2 hapa të mëdha në procesin e lloj bashkohen.

57
00:03:37,750 --> 00:03:41,500
Së pari, vazhdimisht ndarë listën e gota në gjysmave

58
00:03:41,500 --> 00:03:44,860
deri sa ne kemi një bandë e listave me vetëm 1 filxhan në to.

59
00:03:44,860 --> 00:03:47,350
Mos u shqetësoni nëse një listë përmban një numër të rastësishëm

60
00:03:47,350 --> 00:03:49,880
dhe ju nuk mund të bëjë një prerje të përkryer të pastër në mes tyre.

61
00:03:49,880 --> 00:03:53,750
Vetëm arbitrare të vini të cilën listë të përfshijë kupën ekstra in

62
00:03:53,750 --> 00:03:56,240
Pra, le të ndahen këto lista.

63
00:03:58,140 --> 00:04:01,310
Tani ne kemi 2 listat.

64
00:04:04,120 --> 00:04:06,570
Tani ne kemi 4 listat.

65
00:04:10,350 --> 00:04:13,870
>> Dhe tani ne kemi 8 listat me një filxhan të vetëm në çdo listë.

66
00:04:13,870 --> 00:04:16,630
Pra, kjo është ajo për hapin 1.

67
00:04:16,630 --> 00:04:22,230
Për hapin e 2, ne vazhdimisht bashkojë palë e listave duke përdorur algoritmin bashkojë kemi mësuar më parë.

68
00:04:22,230 --> 00:04:29,160
Bashkimi i 108 dhe 15, deri ne fund me listën e 15, 108.

69
00:04:30,330 --> 00:04:36,250
Bashkimi 50 dhe 4, ne fund me 4, 50.

70
00:04:36,960 --> 00:04:41,400
Bashkimi 8 dhe 42, deri ne fund me 8, 42.

71
00:04:42,790 --> 00:04:48,130
Dhe bashkimin 23 dhe 16, ne fund me 16, 23.

72
00:04:49,740 --> 00:04:52,450
Tani të gjitha listat tona janë të madhësisë 2.

73
00:04:53,020 --> 00:04:56,180
Njoftim që secili prej 4 listave është renditura.

74
00:04:56,180 --> 00:04:59,160
>> Kështu që ne mund të fillojë bashkimin palë e listave përsëri.

75
00:04:59,160 --> 00:05:03,240
Bashkimi 15 dhe 108 dhe 4 dhe 50 -

76
00:05:03,240 --> 00:05:11,170
së pari të marrë 4, pastaj 15, pastaj 50, pastaj 108.

77
00:05:11,170 --> 00:05:15,120
Bashkimin 8, 42 dhe 16, 23,

78
00:05:15,120 --> 00:05:22,440
ne së pari të marrë 8, pastaj 16, pastaj 23, pastaj 42.

79
00:05:22,440 --> 00:05:27,370
Deri tani ne kemi vetëm 2 listat e madhësisë 4, secila prej të cilave është renditura.

80
00:05:27,370 --> 00:05:30,980
Deri tani ne bashkojë këto 2 listat.

81
00:05:30,980 --> 00:05:33,440
Së pari ne kemi marrë 4.

82
00:05:33,440 --> 00:05:36,580
Pastaj kemi marrë 8.

83
00:05:36,580 --> 00:05:50,700
Pastaj ne kemi marrë 15 dhe 16, pastaj 23, pastaj 42, pastaj 50, pastaj 108.

84
00:05:50,700 --> 00:05:52,220
Dhe ne jemi duke bërë.

85
00:05:52,220 --> 00:05:54,900
Ne tani kemi një listë të renditura.

86
00:05:54,900 --> 00:05:57,890
Pra, se sa shpejt ishte ky, saktësisht?

87
00:05:57,890 --> 00:06:02,000
Në terma teknike, lloj bashkojë është O (n log n),

88
00:06:02,000 --> 00:06:07,380
ndërsa të gjitha lloj flluskë, lloj lloj futje, dhe përzgjedhjes janë të O (n ²).

89
00:06:07,380 --> 00:06:11,120
Në fakt, si ju do të mësoni shpejt, ju nuk do të jetë në gjendje për të dalë me një lloj

90
00:06:11,120 --> 00:06:14,820
që kryen më mirë se O (n log n) në rastin e përgjithshëm.

91
00:06:14,820 --> 00:06:19,120
Përsëri, mos u bëni merak për këtë simbol Big O qoftë se ju nuk e keni parë atë ende.

92
00:06:19,120 --> 00:06:23,490
>> Vetëm e di se kjo do të thotë në qoftë se ne të kërkuar për të zgjidhur një listë me të vërtetë e madhe

93
00:06:23,490 --> 00:06:26,820
lloj flluskë, lloj futje, dhe përzgjedhja lloj potencialisht mund të marrë

94
00:06:26,820 --> 00:06:29,500
dukshëm më shumë se bashkohen lloj.

95
00:06:29,500 --> 00:06:33,210
Kjo nuk do të thotë se do të jetë lloj bashkojë të shpejtë për të gjitha listat

96
00:06:33,210 --> 00:06:36,220
apo edhe për ndonjë listë të vetme nën një madhësi të caktuar.

97
00:06:36,220 --> 00:06:41,950
Për shembull, mund të jetë lloj futje lloj shpejtë për të gjitha listat e më të vogla se 5 elementeve.

98
00:06:41,950 --> 00:06:47,360
Në praktikë, lloj bashkojë është zakonisht më të shpejtë për listat si të vogla si 50 elemente.

99
00:06:47,360 --> 00:06:51,120
>> Por kjo shpejtësi ekstra nuk ka ardhur pa një çmim.

100
00:06:51,120 --> 00:06:54,770
Ndryshe nga llojet tona të tjera, të cilat marrin një listë dhe modifikojë listën në vend

101
00:06:54,770 --> 00:06:58,740
deri sa të kemi një listë të renditura, lloj bashkojë nevojë për një hapësirë ​​shtesë

102
00:06:58,740 --> 00:07:00,900
të bashkojë 2 listat së bashku.

103
00:07:00,900 --> 00:07:04,690
Ne nuk mund të përdorni menjëherë listat që janë duke u bashkuar për të ruajtur listën e shkrirë

104
00:07:04,690 --> 00:07:08,880
që ne mund të pranoj elementet që ende duhet të bashkohen.

105
00:07:08,880 --> 00:07:13,540
Kjo hapësirë ​​është pak e një çmim, por kjo zakonisht nuk është e paarsyeshme.

106
00:07:13,540 --> 00:07:15,330
Dhe kjo është ajo për lloj bashkohen.

107
00:07:15,330 --> 00:07:18,490
>> Emri im është Rob Bowden, dhe kjo është CS50.

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

109
00:07:20,500 --> 00:07:24,000
- Dhe zgjedhja lloj.

110
00:07:24,000 --> 00:07:25,880
[Qesh]

111
00:07:25,880 --> 00:07:31,480
Oh, marrë për të marrë atë jashtë shumë, sepse unë kaloi si unë u paraqitur atë.

112
00:07:31,480 --> 00:07:35,680
Lista në të majtë. Kjo ishte një typo.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] I dehur -

114
00:07:39,290 --> 00:07:41,190
[Qesh]

115
00:07:41,190 --> 00:07:44,190
Unë nuk e di se çfarë -