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

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[To je CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Pogovorimo se o datumu spajanja.

5
00:00:09,000 --> 00:00:14,000
Do sedaj ste videli mehurček razvrščanje, razvrščanje in vstavljanje izbiro vrste.

6
00:00:14,000 --> 00:00:17,000
Čeprav bom nekako val mojo roko na kaj mislim s bolje,

7
00:00:17,000 --> 00:00:21,000
združiti sortiranje na splošno opravlja bolje kot kateri koli od teh 3 vrst.

8
00:00:22,000 --> 00:00:27,000
>> Toda preden govorimo o neke spajanja, kaj je govoril o združitvi 2 razvrščena seznamov.

9
00:00:27,000 --> 00:00:31,000
Poklicali bomo proces sprejemanja 2 razvrščena seznamov, kot so te,

10
00:00:31,000 --> 00:00:35,000
in kar sam urejen seznam iz njih - združitev seznamov.

11
00:00:35,000 --> 00:00:37,750
Kako lahko to storimo?

12
00:00:37,750 --> 00:00:41,290
No, ena ideja je, da ostanemo en seznam na koncu drugega seznama

13
00:00:41,290 --> 00:00:43,830
nato pa razvrstite izhaja seznam.

14
00:00:43,830 --> 00:00:47,220
>> Medtem ko ta deluje, je veliko nepotrebnega dela.

15
00:00:47,220 --> 00:00:49,900
Mi lahko to storite hitreje kot le usmerjanje.

16
00:00:49,900 --> 00:00:54,100
Obvestilo, da ena napačna ideja je, da vzemite izmenično skodelic iz vsakega seznama.

17
00:00:54,100 --> 00:00:56,460
Čeprav se lahko zdi, da deluje na prvi pogled,

18
00:00:56,460 --> 00:01:05,760
tem, da smo na koncu s 4, 8, 15, 23, 16 - obvestilo, da 16 in 23 so na pravem mestu.

19
00:01:05,760 --> 00:01:09,380
To je zato, ker 2 elementi, ki se navedejo zaporedno v združenega seznama

20
00:01:09,380 --> 00:01:11,720
v istem prvotnega seznama.

21
00:01:11,720 --> 00:01:14,850
Oba 15 in 16 so na seznamu na levi strani.

22
00:01:14,850 --> 00:01:19,810
Trik je v tem, da izkoristijo dejstvo, da se oba seznama že sortirane.

23
00:01:19,810 --> 00:01:23,320
To pomeni, da če bomo le pogled na prvih elementov obeh seznamov -

24
00:01:23,320 --> 00:01:29,580
Tukaj, 4 in 8 - mora biti eden izmed njih je tudi prvi element novega seznama.

25
00:01:29,580 --> 00:01:31,620
Torej, zakaj je to?

26
00:01:31,620 --> 00:01:33,520
Oba od teh seznamov so že razporejene,

27
00:01:33,520 --> 00:01:38,410
in zato morajo bodisi 4 ali 8 je najmanjši element, ko združimo 2 seznamov.

28
00:01:38,410 --> 00:01:41,770
V tem primeru je najmanjša 4,

29
00:01:41,770 --> 00:01:46,370
da bomo lahko ven 4 in da je prvi element našega novega seznama.

30
00:01:46,370 --> 00:01:50,710
Zdaj bomo še naprej združuje preostale 3 dele prvega seznama

31
00:01:50,710 --> 00:01:52,920
in 4 elementi drugem seznamu.

32
00:01:52,920 --> 00:01:57,150
>> Še enkrat, potrebujemo le, da pogled na prvi element obeh seznamov.

33
00:01:57,150 --> 00:02:01,060
Manjše od 2 mora biti drugi element našega novega seznama.

34
00:02:01,060 --> 00:02:05,440
Tokrat je med 8 in 15 najmanjših je 8, zato smo vstaviti, da

35
00:02:05,440 --> 00:02:09,240
kot drugi element našega razvrščene seznama.

36
00:02:09,240 --> 00:02:12,180
Lahko nadaljujemo primerjavo prve elemente obeh seznamih

37
00:02:12,180 --> 00:02:14,420
in odpravo manjši od 2.

38
00:02:14,420 --> 00:02:19,460
Primerjava 15 in 23, 15, je manjša in da je naš tretji element.

39
00:02:21,000 --> 00:02:23,910
Zdaj primerjavo 16 in 23, 16, je manjša.

40
00:02:23,910 --> 00:02:26,820
Torej, to je četrti element.

41
00:02:26,820 --> 00:02:30,390
>> Obvestilo, da 2 elementi izvirajo iz istega seznama zapored.

42
00:02:30,390 --> 00:02:34,400
To je razlog, zakaj združeni seznam ne more samo nadomestne elemente iz 2 seznamov.

43
00:02:34,400 --> 00:02:40,020
Primerjava 50 in 23, 23, je manjša, zato smo se odločili, da.

44
00:02:40,770 --> 00:02:44,070
Med 50 in 42, 42, je manjša.

45
00:02:44,070 --> 00:02:48,290
Med 50 in 108, 50 pa je manjša.

46
00:02:48,290 --> 00:02:52,330
In končno, imamo samo 108, tako da mora iti na koncu našega seznama.

47
00:02:53,750 --> 00:02:56,180
Obvestilo, da imamo lepo, razvrščen seznam.

48
00:02:56,180 --> 00:02:59,040
Vsakič, ko smo primerjali 1. 2 elemente 2 seznamov

49
00:02:59,040 --> 00:03:02,730
smo lahko določili naslednji element združenega seznama.

50
00:03:02,730 --> 00:03:08,070
To pomeni, da če je končni seznam vsebuje n številk, pri čemer je n tukaj je 8,

51
00:03:08,070 --> 00:03:12,610
potem moramo v večini n primerjav, da bi dobili vse te številke na pravem mestu.

52
00:03:13,230 --> 00:03:16,230
Tak algoritem je dejal, da deluje v linearnem času,

53
00:03:16,230 --> 00:03:18,090
vendar ne skrbite o tem tukaj.

54
00:03:18,570 --> 00:03:22,810
>> Z uporabo našega algoritma za združitev, lahko naredimo hiter razvrščanja algoritem za spajanje.

55
00:03:22,810 --> 00:03:25,170
Torej, kaj je prikrivati ​​svoje sezname.

56
00:03:35,210 --> 00:03:37,750
Obstajata 2 velik korak v procesu vrste spajanja.

57
00:03:37,750 --> 00:03:41,500
Prvič, ves čas po delih seznam skodelic na polovici

58
00:03:41,500 --> 00:03:44,860
dokler ne bomo imeli kup seznamov s samo 1 skodelico v njih.

59
00:03:44,860 --> 00:03:47,350
Ne skrbite, če seznam vsebuje liho število

60
00:03:47,350 --> 00:03:49,880
in ne moreš narediti popolnoma čisti rez med njimi.

61
00:03:49,880 --> 00:03:53,750
Samo samovoljno izbirati, katere seznam vključiti dodatno skodelico noter

62
00:03:53,750 --> 00:03:56,240
Torej, kaj je razdeljen teh seznamov.

63
00:03:58,140 --> 00:04:01,310
Zdaj imamo 2 seznamov.

64
00:04:04,120 --> 00:04:06,570
Zdaj imamo 4 seznamov.

65
00:04:10,350 --> 00:04:13,870
>> In zdaj imamo 8 sezname z eno skodelico na vsakega seznama.

66
00:04:13,870 --> 00:04:16,630
Tako da je za 1. koraku.

67
00:04:16,630 --> 00:04:22,230
Za 2. koraku, smo večkrat združi pare seznamov s pomočjo algoritma za spajanje smo se naučili prej.

68
00:04:22,230 --> 00:04:29,160
Združitev 108 in 15, smo na koncu s seznama 15, 108.

69
00:04:30,330 --> 00:04:36,250
Združitev 50 in 4, smo na koncu s 4, 50.

70
00:04:36,960 --> 00:04:41,400
Združitev 8 in 42, smo na koncu z 8, 42.

71
00:04:42,790 --> 00:04:48,130
In združuje 23 in 16, smo na koncu z 16, 23.

72
00:04:49,740 --> 00:04:52,450
Zdaj so vsi naši seznami velikosti 2.

73
00:04:53,020 --> 00:04:56,180
Obvestilo, da je razvrščena vsaka od 4 seznamov.

74
00:04:56,180 --> 00:04:59,160
>> Torej, lahko začnemo združuje parov seznamov znova.

75
00:04:59,160 --> 00:05:03,240
Združitev 15 in 108 ter 4 in 50 -

76
00:05:03,240 --> 00:05:11,170
1. sprejme 4, nato 15, nato 50, nato 108.

77
00:05:11,170 --> 00:05:15,120
Združitev 8, 42 in 16, 23,

78
00:05:15,120 --> 00:05:22,440
najprej sprejme 8, nato 16, nato 23, nato 42.

79
00:05:22,440 --> 00:05:27,370
Torej, zdaj imamo samo 2 seznamov velikosti 4, so razvrščeni od katerih vsaka.

80
00:05:27,370 --> 00:05:30,980
Zdaj smo združiti teh 2 seznamov.

81
00:05:30,980 --> 00:05:33,440
Najprej vzamemo 4.

82
00:05:33,440 --> 00:05:36,580
Nato vzamemo 8.

83
00:05:36,580 --> 00:05:50,700
Nato vzamemo 15 in 16, nato 23, nato 42, nato 50, nato 108.

84
00:05:50,700 --> 00:05:52,220
In končamo.

85
00:05:52,220 --> 00:05:54,900
Zdaj imamo urejen seznam.

86
00:05:54,900 --> 00:05:57,890
Torej, kako hitro je to točno?

87
00:05:57,890 --> 00:06:02,000
V tehničnem smislu zlivanjem je O (n log n)

88
00:06:02,000 --> 00:06:07,380
ker vse vrste mehurčkov, vstavljanja vrste in izbor razvrstite so O (n ²).

89
00:06:07,380 --> 00:06:11,120
V bistvu, kot boste izvedeli kmalu ne boste mogli prišli do neke

90
00:06:11,120 --> 00:06:14,820
ki opravlja bolje kot O (n log n) V splošnem primeru.

91
00:06:14,820 --> 00:06:19,120
Še enkrat, ne skrbi, ta velik zapis o Če še niste videli.

92
00:06:19,120 --> 00:06:23,490
>> Samo vem, da to pomeni, da če bi želeli rešiti res velik seznam

93
00:06:23,490 --> 00:06:26,820
bubble sort, vstavljanje sortiranje, izbira sort, lahko potencialno lahko

94
00:06:26,820 --> 00:06:29,500
bistveno daljši od zlivanjem.

95
00:06:29,500 --> 00:06:33,210
To ne pomeni, da bo z zlivanjem hitrejši za vse sezname

96
00:06:33,210 --> 00:06:36,220
ali celo za posamezno seznamu pod določeno velikostjo.

97
00:06:36,220 --> 00:06:41,950
Na primer, vključitev neke vrste bil najhitrejši na vseh seznamih, manjših od 5 elementov.

98
00:06:41,950 --> 00:06:47,360
V praksi zlivanjem je ponavadi hitrejši za sezname kot majhne kot 50 elementov.

99
00:06:47,360 --> 00:06:51,120
>> Vendar pa to dodatno hitrost ne prihaja brez ceno.

100
00:06:51,120 --> 00:06:54,770
Za razliko od naših drugih vrst, ki sprejme seznam in spremeni seznam na mestu

101
00:06:54,770 --> 00:06:58,740
dokler ne bomo dobili urejen seznam, zlivanjem potrebuje nekaj dodatnega prostora

102
00:06:58,740 --> 00:07:00,900
združiti 2 seznamov skupaj.

103
00:07:00,900 --> 00:07:04,690
Mi ne more takoj uporabi sezname, ki se združila za shranjevanje združeno seznam

104
00:07:04,690 --> 00:07:08,880
saj bomo morda prednost elemente, ki jih je še treba združiti.

105
00:07:08,880 --> 00:07:13,540
Ta prostor je malo ceni, vendar običajno ni nerazumna.

106
00:07:13,540 --> 00:07:15,330
In to je to za razvrščanje spajanja.

107
00:07:15,330 --> 00:07:18,490
>> Moje ime je Rob Bowden, in to je CS50.

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

109
00:07:20,500 --> 00:07:24,000
- Izbor in razvrščanje.

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

111
00:07:25,880 --> 00:07:31,480
Oh, moram vzeti ven, da tudi zato, ker sem zamenjal, kako sem jo predstavlja.

112
00:07:31,480 --> 00:07:35,680
Seznam na levi strani. To je bila tipkarska napaka.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] sem zamočil -

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

115
00:07:41,190 --> 00:07:44,190
Ne vem kaj -