1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Tarkvaraprojekteerimise]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvardi Ülikool]

3
00:00:04,000 --> 00:00:07,000
[See on CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Räägime ühendamise omamoodi.

5
00:00:09,000 --> 00:00:14,000
Siiani olete näinud mull sorteerida, sisestamise sorteerida ning valik omamoodi.

6
00:00:14,000 --> 00:00:17,000
Kuigi ma tulen mingi laine mu kätt, mida ma mõtlen parem,

7
00:00:17,000 --> 00:00:21,000
liita omamoodi üldiselt toimib paremini kui ükski neist 3 kehvasti.

8
00:00:22,000 --> 00:00:27,000
>> Aga enne räägi ühendamise sorteerida, räägime ühineva 2 järjestatud loendid.

9
00:00:27,000 --> 00:00:31,000
Me helistame käigus võetakse 2 järjestatud loendid, nagu need,

10
00:00:31,000 --> 00:00:35,000
ja teeb ühe järjestatud nimekirja läbi neist - ühineva nimekirju.

11
00:00:35,000 --> 00:00:37,750
Kuidas me saame seda teha?

12
00:00:37,750 --> 00:00:41,290
Noh, üks idee on lihtsalt kinni ühes nimekirjas koridori lõpus muu nimekiri

13
00:00:41,290 --> 00:00:43,830
ja seejärel sortida saadud nimekirja.

14
00:00:43,830 --> 00:00:47,220
>> Kuigi see toimib, see on palju asjatut tööd.

15
00:00:47,220 --> 00:00:49,900
Me ei saa teha seda kiiremini kui lihtsalt sorteerimine.

16
00:00:49,900 --> 00:00:54,100
Pange tähele, et üks vale idee on lihtsalt võtta vaheldumisi tassi igast loetelust.

17
00:00:54,100 --> 00:00:56,460
Kuigi see võib tunduda, et tööde alguses,

18
00:00:56,460 --> 00:01:05,760
teeme, et me lõpetame 4, 8, 15, 23, 16 - teade, et 16 ja 23 on kohatu.

19
00:01:05,760 --> 00:01:09,380
Seda seetõttu, et 2 elementi, mis peaks ilmuma järjestikusel aastal ühinenud nimekiri

20
00:01:09,380 --> 00:01:11,720
on samas esialgsest nimekirjast.

21
00:01:11,720 --> 00:01:14,850
Mõlemad 15 ja 16 on vasakul olevast nimekirjast.

22
00:01:14,850 --> 00:01:19,810
Trikk on ära asjaolu, et mõlemad nimekirjad on juba järjestatud.

23
00:01:19,810 --> 00:01:23,320
See tähendab, et kui me lihtsalt vaatame esimest elementi mõlemad nimekirjad -

24
00:01:23,320 --> 00:01:29,580
siin, 4 ja 8 - üks neist peab olema ka esimene osa ühinenud nimekirja.

25
00:01:29,580 --> 00:01:31,620
Noh, miks see nii on?

26
00:01:31,620 --> 00:01:33,520
Mõlemad nimekirjad on juba sorteeritud,

27
00:01:33,520 --> 00:01:38,410
ja seda kas 4 või 8 peab olema väikseim element, kui me ühendame 2 on loetletud.

28
00:01:38,410 --> 00:01:41,770
Sel juhul väikseim 4,

29
00:01:41,770 --> 00:01:46,370
et saaksime välja 4 ja teha see esimene osa meie ühinenud nimekirja.

30
00:01:46,370 --> 00:01:50,710
Nüüd jätkame ühinevad ülejäänud 3 elemendid esimese nimekirja

31
00:01:50,710 --> 00:01:52,920
ja 4 elementi teise nimekirja.

32
00:01:52,920 --> 00:01:57,150
>> Veelkord, meil on vaja ainult vaadata esimene osa mõlemas nimekirjas.

33
00:01:57,150 --> 00:02:01,060
Väiksem 2 peab olema teine ​​osa meie ühinenud nimekirja.

34
00:02:01,060 --> 00:02:05,440
Seekord vahemikus 8 ja 15. väikseim on 8, ja nii me lisada, et

35
00:02:05,440 --> 00:02:09,240
kui teine ​​osa meie järjestatud nimekirja.

36
00:02:09,240 --> 00:02:12,180
Me ei saa jätkata võrdle esimest elementi mõlema nimekirja

37
00:02:12,180 --> 00:02:14,420
ja eemaldades väiksem 2.

38
00:02:14,420 --> 00:02:19,460
Võrreldes 15 ja 23, 15 on väiksem ja et see on meie kolmas element.

39
00:02:21,000 --> 00:02:23,910
Nüüd võrreldi 16 ja 23, 16 on väiksem.

40
00:02:23,910 --> 00:02:26,820
Nii et neljas element.

41
00:02:26,820 --> 00:02:30,390
>> Pange tähele, et 2 elementi tuli samas nimekirjas järjest.

42
00:02:30,390 --> 00:02:34,400
See on põhjus, miks ühinenud nimekiri ei saa lihtsalt asendusliikme elemente 2 on loetletud.

43
00:02:34,400 --> 00:02:40,020
Võrreldes 50 ja 23, 23 on väiksem, nii et me valime seda.

44
00:02:40,770 --> 00:02:44,070
50 kuni 42, 42 on väiksem.

45
00:02:44,070 --> 00:02:48,290
Vahemikus 50 ja 108, 50 on väiksem.

46
00:02:48,290 --> 00:02:52,330
Ja lõpuks, me lihtsalt peame 108, nii et see peab minema lõpuni meie nimekirjas.

47
00:02:53,750 --> 00:02:56,180
Pange tähele, et meil on kena, järjestatud nimekirja.

48
00:02:56,180 --> 00:02:59,040
Iga kord, kui me võrreldes esimese 2 elemendid 2 on loetletud

49
00:02:59,040 --> 00:03:02,730
suutsime kindlaks järgmise elemendi ühinemisel tekkinud nimekirja.

50
00:03:02,730 --> 00:03:08,070
See tähendab, et kui lõplik nimekiri sisaldab n numbrid, kus n on siin 8,

51
00:03:08,070 --> 00:03:12,610
siis peame ülimalt n võrdlusi saada kõik need numbrid õigesse kohta.

52
00:03:13,230 --> 00:03:16,230
Selline algoritm on öelnud, et sõidetud lineaarset aega

53
00:03:16,230 --> 00:03:18,090
kuid ärge muretsege, et siin.

54
00:03:18,570 --> 00:03:22,810
>> Kasutades meie algoritm ühinevad, saame teha kiire ühendamise omamoodi algoritm.

55
00:03:22,810 --> 00:03:25,170
Niisiis, oletame, reset meie nimekirju.

56
00:03:35,210 --> 00:03:37,750
Seal on 2 suurt sammu protsessis ühendamise omamoodi.

57
00:03:37,750 --> 00:03:41,500
Esiteks, pidevalt jagada nimekirja tassi pooleks

58
00:03:41,500 --> 00:03:44,860
kuni meil on hunnik nimekirjad vaid 1 tass neid.

59
00:03:44,860 --> 00:03:47,350
Ärge muretsege, kui loend sisaldab paaritu arv

60
00:03:47,350 --> 00:03:49,880
ja te ei saa teha täiesti selgepiiriline nende vahel.

61
00:03:49,880 --> 00:03:53,750
Lihtsalt suvaliselt valida, millist nimekirja lisada pildi tassi sisse

62
00:03:53,750 --> 00:03:56,240
Niisiis, oletame, jagada neid nimekirju.

63
00:03:58,140 --> 00:04:01,310
Nüüd meil on 2 nimekirju.

64
00:04:04,120 --> 00:04:06,570
Nüüd on 4 nimekirju.

65
00:04:10,350 --> 00:04:13,870
>> Ja nüüd meil on 8 nimekirjad ühe tassi iga nimekirja.

66
00:04:13,870 --> 00:04:16,630
Nii et see on mu 1. etapp.

67
00:04:16,630 --> 00:04:22,230
Sest 2.etapp, me korduvalt ühendada paari nimekirjad kasutades ühendamise algoritm oleme õppinud varem.

68
00:04:22,230 --> 00:04:29,160
Ühinevad 108 ja 15, me lõpetame nimekiri 15, 108.

69
00:04:30,330 --> 00:04:36,250
Ühinevad 50 ja 4, me lõpetame 4, 50.

70
00:04:36,960 --> 00:04:41,400
Ühinevad 8 ja 42, me lõpetame 8, 42.

71
00:04:42,790 --> 00:04:48,130
Ja ühineva 23 ja 16, me lõpetame 16, 23.

72
00:04:49,740 --> 00:04:52,450
Nüüd kõik meie nimekirjad on suurusega 2.

73
00:04:53,020 --> 00:04:56,180
Pange tähele, et iga 4 nimekirjad on sorteeritud.

74
00:04:56,180 --> 00:04:59,160
>> Nii saame alustada ühinevad paari nimekirjad uuesti.

75
00:04:59,160 --> 00:05:03,240
Ühinevad 15 ja 108 ja 4 ja 50 -

76
00:05:03,240 --> 00:05:11,170
kõigepealt 4, siis 15, siis 50, siis 108.

77
00:05:11,170 --> 00:05:15,120
Ühinevad 8, 42 ja 16, 23,

78
00:05:15,120 --> 00:05:22,440
me esimest korda võtma 8, siis 16, siis 23, siis 42.

79
00:05:22,440 --> 00:05:27,370
Nii et nüüd on meil vaid 2 nimekirjad suurus 4, millest igaüks on järjestatud.

80
00:05:27,370 --> 00:05:30,980
Nii et nüüd me koondada need 2 on loetletud.

81
00:05:30,980 --> 00:05:33,440
Esiteks võtame 4.

82
00:05:33,440 --> 00:05:36,580
Siis võtame 8.

83
00:05:36,580 --> 00:05:50,700
Siis võtame 15 ja 16, siis 23, siis 42, siis 50, siis 108.

84
00:05:50,700 --> 00:05:52,220
Ja me oleme valmis.

85
00:05:52,220 --> 00:05:54,900
Meil on nüüd järjestatud nimekirja.

86
00:05:54,900 --> 00:05:57,890
Nii et kui kiiresti oli see täpselt?

87
00:05:57,890 --> 00:06:02,000
Tehnilises mõttes ühendamise sorteerida on O (n log n),

88
00:06:02,000 --> 00:06:07,380
arvestades, et kogu mull sorteerida, sisestamise sorteerida ning valik omamoodi on O (n ²).

89
00:06:07,380 --> 00:06:11,120
Tegelikult, nagu te õpite kiiresti, sa ei saa tulla mingi

90
00:06:11,120 --> 00:06:14,820
mis täidab paremini kui O (n log n) üldiselt juhul.

91
00:06:14,820 --> 00:06:19,120
Jällegi, ärge muretsege see suur O notatsiooni kui sa ei ole näinud seda veel.

92
00:06:19,120 --> 00:06:23,490
>> Lihtsalt tean, et see tähendab, kui me tahtsime sortida tõesti suur nimekiri

93
00:06:23,490 --> 00:06:26,820
mull sorteerida, sisestamise sorteerida ning valik omamoodi võiks võtta

94
00:06:26,820 --> 00:06:29,500
oluliselt pikem kui liita omamoodi.

95
00:06:29,500 --> 00:06:33,210
See ei tähenda, et ühendamise omamoodi muutub kiiremaks kõigi nimekirjad

96
00:06:33,210 --> 00:06:36,220
või isegi mõni üksik nimekirja teatud suurusest.

97
00:06:36,220 --> 00:06:41,950
Näiteks sisestamise omamoodi olla kiireim omamoodi kõigi nimekirjade väiksem kui 5 elementi.

98
00:06:41,950 --> 00:06:47,360
Praktikas ühendamise sorteerida on tavaliselt kiirem nimekirjad nii väike kui 50 elementi.

99
00:06:47,360 --> 00:06:51,120
>> Aga see ekstra kiirust ei tule ilma hinnaga.

100
00:06:51,120 --> 00:06:54,770
Erinevalt meie teistest kehvasti, mis võtavad nimekiri ja loetelu muutmiseks paigas

101
00:06:54,770 --> 00:06:58,740
kuni saame järjestatud nimekirja, liita omamoodi vajab lisaruumi

102
00:06:58,740 --> 00:07:00,900
ühendada 2 loetletakse koos.

103
00:07:00,900 --> 00:07:04,690
Me ei saa kohe kasutada nimekirjad on ühendada salvestada ühinenud nimekiri

104
00:07:04,690 --> 00:07:08,880
kuna me võiksime alistada elemente, mis tuleb veel liita.

105
00:07:08,880 --> 00:07:13,540
See ala on natuke hind, kuid tavaliselt ei ole mõistlik.

106
00:07:13,540 --> 00:07:15,330
Ja ongi kõik MERGE omamoodi.

107
00:07:15,330 --> 00:07:18,490
>> Minu nimi on Rob Bowden, ja see on CS50.

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

109
00:07:20,500 --> 00:07:24,000
- Ja valik omamoodi.

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

111
00:07:25,880 --> 00:07:31,480
Oh, sain võtta, et liiga, sest ma vahetasin kuidas ma selle esitamine.

112
00:07:31,480 --> 00:07:35,680
Nimekiri vasakul. See oli kirjaviga.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] Ma silmamunad -

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

115
00:07:41,190 --> 00:07:44,190
Ma ei tea, mida -