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

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

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

4
00:00:07,000 --> 00:00:09,000
Ni parolos pri merge varon.

5
00:00:09,000 --> 00:00:14,000
Ĝis nun vi vidis bobelo varo, inserción varo, kaj selektado varon.

6
00:00:14,000 --> 00:00:17,000
Kvankam Mi instruos vin speco de ondo mian manon je kio mi aludas per bona,

7
00:00:17,000 --> 00:00:21,000
kunfandi speco ĝenerale plenumas pli bone ol iu el tiuj 3 varoj.

8
00:00:22,000 --> 00:00:27,000
>> Sed antaŭ parolas merge varo, ni parolu pri kunfandi 2 ordo listoj.

9
00:00:27,000 --> 00:00:31,000
Ni vokos la procezo de prenante 2 ordo lertaj, kiel ĉi tiuj,

10
00:00:31,000 --> 00:00:35,000
kaj farante sola ordo listo el ili - kunfandi la listoj.

11
00:00:35,000 --> 00:00:37,750
Kiel ni povas fari ĉi tion?

12
00:00:37,750 --> 00:00:41,290
Nu, unu ideo estas simple resti unu listo sur la fino de la alia listo

13
00:00:41,290 --> 00:00:43,830
kaj poste ordigi la rezultan liston.

14
00:00:43,830 --> 00:00:47,220
>> Dum ĉi tiu funkcias, estas multe da nenecesaj laboro.

15
00:00:47,220 --> 00:00:49,900
Ni povas fari ĝin pli rapide ol nur ordigi.

16
00:00:49,900 --> 00:00:54,100
Rimarku ke unu malĝustan ideo estas simple preni alternaj tasojn el ĉiu listo.

17
00:00:54,100 --> 00:00:56,460
Dum kiu povas simili ke verkoj unue,

18
00:00:56,460 --> 00:01:05,760
faras ke ni finos kun 4, 8, 15, 23, 16 - avertas ke 16 kaj 23 estas maloportune.

19
00:01:05,760 --> 00:01:09,380
Ĉi tiu estas ĉar 2 eroj kiuj devus aperi sinsekvaj en la kunfandita listo

20
00:01:09,380 --> 00:01:11,720
estas en la sama komenca listo.

21
00:01:11,720 --> 00:01:14,850
Ambaŭ 15 kaj 16 estas en la listo maldekstre.

22
00:01:14,850 --> 00:01:19,810
La artifiko estas utiligi la fakton ke ambaŭ listoj jam ordo.

23
00:01:19,810 --> 00:01:23,320
Tio signifas ke se oni nur rigardas la unuajn elementojn de ambaŭ listoj -

24
00:01:23,320 --> 00:01:29,580
tie, 4 kaj 8 - unu el ili devas ankaŭ esti la unua elemento de la kunfandita listo.

25
00:01:29,580 --> 00:01:31,620
Nu, kial estas tio?

26
00:01:31,620 --> 00:01:33,520
Ambaŭ ĉi tiuj listoj jam ordo,

27
00:01:33,520 --> 00:01:38,410
kaj tiel aŭ 4 aŭ 8 devas esti la plej malgranda ero, kiam ni kombini la 2 listojn.

28
00:01:38,410 --> 00:01:41,770
En ĉi tiu kazo, la plej malgranda estas 4,

29
00:01:41,770 --> 00:01:46,370
tiel ni povas preni el 4 kaj faru ĝin la unua elemento de nia kunfandis listo.

30
00:01:46,370 --> 00:01:50,710
Nun ni daŭrigas kunfandi la ceteraj 3 elementoj de la unua listo

31
00:01:50,710 --> 00:01:52,920
kaj 4 eroj de la dua listo.

32
00:01:52,920 --> 00:01:57,150
>> Denove, ni nur bezonas rigardi la unua elemento de ambaŭ listojn.

33
00:01:57,150 --> 00:02:01,060
La plej malgranda el la 2 devas esti la dua elemento de nia kunfandis listo.

34
00:02:01,060 --> 00:02:05,440
Ĉi-foje, inter 8 kaj 15 la plej malgranda estas 8, kaj tial ni enŝovu ke

35
00:02:05,440 --> 00:02:09,240
kiel la dua ero de nia ordo listo.

36
00:02:09,240 --> 00:02:12,180
Ni povas daŭrigi kompari la unua elementoj de ambaŭ listoj

37
00:02:12,180 --> 00:02:14,420
kaj forigante la plej malgranda el la 2.

38
00:02:14,420 --> 00:02:19,460
Komparante 15 kaj 23, 15 estas pli malgranda kaj por ke la nia tria elemento.

39
00:02:21,000 --> 00:02:23,910
Nun kompari 16 kaj 23, 16 estas pli malgranda.

40
00:02:23,910 --> 00:02:26,820
Do jen la kvara elemento.

41
00:02:26,820 --> 00:02:30,390
>> Rimarku ke 2 eroj venis de la sama listo en vico.

42
00:02:30,390 --> 00:02:34,400
Jen kial la kunfandita listo ne povas simple alternaj elementoj de la 2-listoj.

43
00:02:34,400 --> 00:02:40,020
Komparante 50 kaj 23, 23 estas pli malgranda, do ni elektu kiun.

44
00:02:40,770 --> 00:02:44,070
Inter 50 kaj 42, 42 estas pli malgranda.

45
00:02:44,070 --> 00:02:48,290
Inter 50 kaj 108, 50 estas pli malgranda.

46
00:02:48,290 --> 00:02:52,330
Kaj, fine, ni nur devas 108, do ĝi devas iri en la fino de nia listo.

47
00:02:53,750 --> 00:02:56,180
Rimarku ke ni havas belan, ordo listo.

48
00:02:56,180 --> 00:02:59,040
Ĉiufoje ni komparis la unuaj 2 eroj de la 2 listojn

49
00:02:59,040 --> 00:03:02,730
ni povis determini la sekvanta elemento de la kunfandita listo.

50
00:03:02,730 --> 00:03:08,070
Tio signifas, ke se la fina listo enhavas n nombroj, kie n tie estas 8,

51
00:03:08,070 --> 00:03:12,610
tiam ni bezonas maksimume n komparoj preni ĉiun el tiuj nombroj en la ĝustan lokon.

52
00:03:13,230 --> 00:03:16,230
Tia algoritmo estas dirita por kuri en lineara tempo,

53
00:03:16,230 --> 00:03:18,090
sed ne maltrankviliĝu pri tio ĉi tie.

54
00:03:18,570 --> 00:03:22,810
>> Uzanta nia algoritmo por kunfandi, ni povas fari rapidan merge speco algoritmo.

55
00:03:22,810 --> 00:03:25,170
Do, ni retrovu niaj listoj.

56
00:03:35,210 --> 00:03:37,750
Estas 2 grandaj paŝoj en la procezo de merge varon.

57
00:03:37,750 --> 00:03:41,500
Unue, senĉese fendi la listo de tasojn en duonoj

58
00:03:41,500 --> 00:03:44,860
gxis ni havas amason da listoj kun nur 1 taso en ili.

59
00:03:44,860 --> 00:03:47,350
Ne maltrankviliĝu, se listo enhavas nepara nombro

60
00:03:47,350 --> 00:03:49,880
kaj vi ne povas fari perfekte pura kortego inter ili.

61
00:03:49,880 --> 00:03:53,750
Nur arbitre elekti kio listo por inkludi la ekstra tason in

62
00:03:53,750 --> 00:03:56,240
Do, ni fendi tiuj listoj.

63
00:03:58,140 --> 00:04:01,310
Nun ni havas 2 listojn.

64
00:04:04,120 --> 00:04:06,570
Nun ni havas 4 listoj.

65
00:04:10,350 --> 00:04:13,870
>> Kaj nun ni havas 8 lertaj kun sola tason en ĉiu listo.

66
00:04:13,870 --> 00:04:16,630
Do jen ĝi por paŝo 1.

67
00:04:16,630 --> 00:04:22,230
Por paŝo 2, ni ree kunfandi paroj de lertaj uzanta la merge algoritmo ni lernis antaŭe.

68
00:04:22,230 --> 00:04:29,160
Kunfandi 108 kaj 15, ni finos kun la listo 15, 108.

69
00:04:30,330 --> 00:04:36,250
Kunfandi 50 kaj 4, ni finos kun 4, 50.

70
00:04:36,960 --> 00:04:41,400
Kunfandi 8 kaj 42, ni finos kun 8, 42.

71
00:04:42,790 --> 00:04:48,130
Kaj kunfandi 23 kaj 16, ni finos kun 16, 23.

72
00:04:49,740 --> 00:04:52,450
Nun ĉiuj niaj listoj estas de amplekso 2.

73
00:04:53,020 --> 00:04:56,180
Rimarki, ke ĉiu el la 4 listoj estas ordigitaj.

74
00:04:56,180 --> 00:04:59,160
>> Do ni povas starti kunfandi paroj de lertaj denove.

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

76
00:05:03,240 --> 00:05:11,170
eligu unue la 4, tiam la 15, tiam la 50, tiam la 108.

77
00:05:11,170 --> 00:05:15,120
Kunfandi 8, 42 kaj 16, 23,

78
00:05:15,120 --> 00:05:22,440
ni unue prenas la 8, tiam la 16, tiam la 23, tiam la 42.

79
00:05:22,440 --> 00:05:27,370
Do nun ni havas nur 2 listojn de grandeco 4, ĉiu el kiuj estas ordo.

80
00:05:27,370 --> 00:05:30,980
Do nun ni kunfandi tiuj 2 listojn.

81
00:05:30,980 --> 00:05:33,440
Unue ni prenas la 4.

82
00:05:33,440 --> 00:05:36,580
Tiam ni prenos la 8.

83
00:05:36,580 --> 00:05:50,700
Tiam ni prenos la 15 kaj 16, tiam 23, do 42, tiam 50, do 108.

84
00:05:50,700 --> 00:05:52,220
Kaj ni faris.

85
00:05:52,220 --> 00:05:54,900
Ni nun havas ordo listo.

86
00:05:54,900 --> 00:05:57,890
Do kiom rapide estis jena ĝuste?

87
00:05:57,890 --> 00:06:02,000
En teknika terminoj, merge varo estas O (n log n),

88
00:06:02,000 --> 00:06:07,380
dum kiu ĉiuj de bobelo varo, inserción varo, kaj selektado varo estas O (n ²).

89
00:06:07,380 --> 00:06:11,120
Fakte, kiel vi lernos baldaŭ, vi ne povos veni supren kun ia

90
00:06:11,120 --> 00:06:14,820
kiu realigas bona ol O (n logo n) en la ĝenerala kazo.

91
00:06:14,820 --> 00:06:19,120
Denove, ne zorgu pri tiu granda a skribmaniero se vi ne vidis ĝin ankoraŭ.

92
00:06:19,120 --> 00:06:23,490
>> Nur scias, ke ĉi tio signifas se ni volis ordigi vere granda listo

93
00:06:23,490 --> 00:06:26,820
bobelo varo, inserción varo, kaj selektado speco povus potenciale preni

94
00:06:26,820 --> 00:06:29,500
signife pli longa ol kunfandi varon.

95
00:06:29,500 --> 00:06:33,210
Ĝi ne signifas ke merge speco estos pli rapida por ĉiuj listoj

96
00:06:33,210 --> 00:06:36,220
aŭ eĉ iun ajn simpla listo sub certa grandeco.

97
00:06:36,220 --> 00:06:41,950
Ekzemple, inserción speco povus esti la plej rapida varo por ĉiuj listoj malgranda ol 5 elementoj.

98
00:06:41,950 --> 00:06:47,360
En praktiko, merge varo estas kutime rapida por lertaj kiel malgranda kiel 50 eroj.

99
00:06:47,360 --> 00:06:51,120
>> Sed ĉi tiu ekstra rapido ne venas sen prezo.

100
00:06:51,120 --> 00:06:54,770
Kontraste niaj aliaj varoj, kiujn prenas listo kaj modifi la liston en loko

101
00:06:54,770 --> 00:06:58,740
ĝis ni preni ordo listo, merge speco bezonas plian spacon

102
00:06:58,740 --> 00:07:00,900
kunfandi 2 listojn kune.

103
00:07:00,900 --> 00:07:04,690
Ni ne povas tuj uzi la listojn kiuj estas kunfandita por stoki la kunfandita listo

104
00:07:04,690 --> 00:07:08,880
ĉar ni povus nuligi elementoj kiuj ankoraŭ bezonas esti kunfandita.

105
00:07:08,880 --> 00:07:13,540
Ĉi tiu spaco estas iom el la prezo, sed kutime ne estas senkaŭza.

106
00:07:13,540 --> 00:07:15,330
Kaj tio estas por merge varon.

107
00:07:15,330 --> 00:07:18,490
>> Mia nomo estas Rob Bowden, kaj ĉi tiu estas CS50.

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

109
00:07:20,500 --> 00:07:24,000
- Kaj selektado varon.

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

111
00:07:25,880 --> 00:07:31,480
Ho, alvenis al tiu el tro ĉar mi ŝanĝis kiom mi prezenti gxin.

112
00:07:31,480 --> 00:07:35,680
Listo maldekstre. Tio estis eraro.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] Mi ŝraŭbita supren -

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

115
00:07:41,190 --> 00:07:44,190
Mi ne scias, kion -