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

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Inivèsite Harvard]

3
00:00:04,000 --> 00:00:07,000
[Sa a se CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Se pou nou pale sou sòt unifye.

5
00:00:09,000 --> 00:00:14,000
Se konsa, lwen ou te wè sòt bil, sòt ensèsyon, ak sòt seleksyon.

6
00:00:14,000 --> 00:00:17,000
Malgre ke m'a kalite vag men m 'nan sa ki mwen vle di yo pa pi bon,

7
00:00:17,000 --> 00:00:21,000
rantre sòt jeneralman fè pi bon pase nenpòt nan 3 sa yo kalite.

8
00:00:22,000 --> 00:00:27,000
>> Men, anvan ap pale de sòt fizyone, kite nan pale sou Fusion 2 Ranje lis.

9
00:00:27,000 --> 00:00:31,000
Nou pral rele pwosesis la nan pran 2 Ranje lis, tankou sa yo,

10
00:00:31,000 --> 00:00:35,000
ak fè yon sèl lis Ranje soti nan yo - Fusion bay lis yo.

11
00:00:35,000 --> 00:00:37,750
Ki jan nou ka fè sa?

12
00:00:37,750 --> 00:00:41,290
Oke, yon sèl lide se jis bwa yon sèl lis sou nan fen lis la lòt

13
00:00:41,290 --> 00:00:43,830
ak Lè sa a, klase lis la ki kapab lakòz.

14
00:00:43,830 --> 00:00:47,220
>> Pandan ke sa a ap travay, li nan yon anpil nan travay nesesè.

15
00:00:47,220 --> 00:00:49,900
Nou ka fè li pi vit pase jis Fouye.

16
00:00:49,900 --> 00:00:54,100
Remake yon ide sa ki mal se jis pran altène tas ki soti nan chak lis.

17
00:00:54,100 --> 00:00:56,460
Pandan ke sa ka parèt tankou yon ki travay an premye,

18
00:00:56,460 --> 00:01:05,760
fè ke nou fini ak 4, 8, 15, 23, 16 - avi ke 16 ak 23 yo soti nan plas li.

19
00:01:05,760 --> 00:01:09,380
Sa a se paske 2 eleman ki ta dwe parèt youn apre lòt nan lis la uni

20
00:01:09,380 --> 00:01:11,720
yo se nan lis la menm inisyal.

21
00:01:11,720 --> 00:01:14,850
Tou de 15 ak 16 yo nan lis la sou bò gòch la.

22
00:01:14,850 --> 00:01:19,810
Jwe fent la se pran avantaj de lefèt ke tou de lis yo deja klase.

23
00:01:19,810 --> 00:01:23,320
Sa vle di ke si nou jis gade nan eleman yo an premye nan tou de bay lis -

24
00:01:23,320 --> 00:01:29,580
isit la, 4 ak 8 - youn nan yo dwe tou pou eleman an premye nan lis la uni.

25
00:01:29,580 --> 00:01:31,620
Byen, poukisa se sa?

26
00:01:31,620 --> 00:01:33,520
Tou de sa yo bay lis yo deja klase,

27
00:01:33,520 --> 00:01:38,410
ak sa swa 4 oswa 8 dwe eleman ki pi piti a, lè nou konbine lis la 2.

28
00:01:38,410 --> 00:01:41,770
Nan ka sa a, pi piti a se 4,

29
00:01:41,770 --> 00:01:46,370
pou nou ka pran soti 4, epi fè li eleman an premye nan lis uni nou an.

30
00:01:46,370 --> 00:01:50,710
Koulye a, nou kontinye Fusion rès 3 eleman ki nan lis nan premye

31
00:01:50,710 --> 00:01:52,920
ak 4 eleman nan lis la dezyèm fwa.

32
00:01:52,920 --> 00:01:57,150
>> Yon fwa ankò, nou sèlman bezwen gade eleman an premye nan tou de lis.

33
00:01:57,150 --> 00:02:01,060
Ki pi piti a nan 2 a dwe eleman an dezyèm nan lis uni nou an.

34
00:02:01,060 --> 00:02:05,440
Tan sa a, ant 8 ak 15 pi piti a se 8, epi pou nou insert ki

35
00:02:05,440 --> 00:02:09,240
kòm eleman an dezyèm nan Ranje lis nou an.

36
00:02:09,240 --> 00:02:12,180
Nou ka kontinye konpare eleman yo an premye nan tou de lis

37
00:02:12,180 --> 00:02:14,420
epi yo retire pi piti a nan 2 a.

38
00:02:14,420 --> 00:02:19,460
Konparezon 15 ak 23, 15 se pi piti ak pou ke nan eleman twazyèm nou an.

39
00:02:21,000 --> 00:02:23,910
Koulye a, konpare 16 ak 23, 16 se pi piti.

40
00:02:23,910 --> 00:02:26,820
Se konsa, sa a, se eleman nan katriyèm.

41
00:02:26,820 --> 00:02:30,390
>> Remake 2 eleman te soti nan lis la menm nan yon ranje.

42
00:02:30,390 --> 00:02:34,400
Sa a se poukisa lis la uni pa kapab jis eleman altène soti nan 2 bay lis yo.

43
00:02:34,400 --> 00:02:40,020
Konparezon 50 ak 23, 23 se pi piti, se konsa nou chwazi sa.

44
00:02:40,770 --> 00:02:44,070
Ant 50 ak 42, 42 se pi piti.

45
00:02:44,070 --> 00:02:48,290
Ant 50 ak 108, 50 se pi piti.

46
00:02:48,290 --> 00:02:52,330
Epi, finalman, nou jis gen 108, se konsa li dwe ale sou fen a nan lis nou an.

47
00:02:53,750 --> 00:02:56,180
Remake ke nou gen yon bèl, Ranje lis la.

48
00:02:56,180 --> 00:02:59,040
Chak fwa nou konpare premye 2 eleman ki nan lis nan 2

49
00:02:59,040 --> 00:03:02,730
nou te kapab detèmine eleman nan pwochen nan lis la uni.

50
00:03:02,730 --> 00:03:08,070
Sa vle di ke si lis la final gen nimewo n, kote n isit la se 8,

51
00:03:08,070 --> 00:03:12,610
Lè sa a, nou bezwen nan pifò konparezon n jwenn tout moun ki nimewo nan plas la dwat.

52
00:03:13,230 --> 00:03:16,230
Tankou yon algorithm te di se kouri nan tan lineyè,

53
00:03:16,230 --> 00:03:18,090
men pa enkyete w sou sa isit la.

54
00:03:18,570 --> 00:03:22,810
>> Lè l sèvi avèk algorithm nou an pou Fusion, nou ka fè yon sèvis jèn algorithm sòt unifye.

55
00:03:22,810 --> 00:03:25,170
Se konsa, kite a Reyajiste lis nou an.

56
00:03:35,210 --> 00:03:37,750
Gen 2 gwo etap nan pwosesis pou yo sòt unifye.

57
00:03:37,750 --> 00:03:41,500
Premyèman, kontinyèlman fann lis la nan tas nan mwatye

58
00:03:41,500 --> 00:03:44,860
jiskaske nou gen yon pakèt moun sou lis ak jis tas 1 nan yo.

59
00:03:44,860 --> 00:03:47,350
Pa enkyete w si yon lis gen yon nimewo enpè

60
00:03:47,350 --> 00:03:49,880
epi ou pa kapab fè yon koupe parfe pwòp ant yo.

61
00:03:49,880 --> 00:03:53,750
Jis abitrèman chwazi ki lis yo mete gode a siplemantè pous

62
00:03:53,750 --> 00:03:56,240
Se konsa, kite a fann sa yo lis.

63
00:03:58,140 --> 00:04:01,310
Koulye a, nou gen 2 lis.

64
00:04:04,120 --> 00:04:06,570
Koulye a, nou gen 4 lis.

65
00:04:10,350 --> 00:04:13,870
>> Epi, koulye a nou gen 8 lis ak yon tas sèl nan chak lis.

66
00:04:13,870 --> 00:04:16,630
Se konsa, sa a, se li pou etap 1.

67
00:04:16,630 --> 00:04:22,230
Pou etap 2, nou repete rantre pè lis lè l sèvi avèk algoritm la unifye nou te aprann anvan.

68
00:04:22,230 --> 00:04:29,160
Machin rantre 108 ak 15, nou fini ak lis la 15, 108.

69
00:04:30,330 --> 00:04:36,250
Machin rantre 50 ak 4, nou fini ak 4 50,.

70
00:04:36,960 --> 00:04:41,400
Machin rantre 8 ak 42, nou fini ak 8, 42.

71
00:04:42,790 --> 00:04:48,130
Ak fusion 23 ak 16, nou fini ak 16, 23.

72
00:04:49,740 --> 00:04:52,450
Koulye a, tout lis nou yo se nan gwosè 2.

73
00:04:53,020 --> 00:04:56,180
Remake chak nan 4 lis la se Klase.

74
00:04:56,180 --> 00:04:59,160
>> Se konsa, nou kapab kòmanse Fusion pè lis ankò.

75
00:04:59,160 --> 00:05:03,240
Machin rantre 15 ak 108 ak 4 ak 50 -

76
00:05:03,240 --> 00:05:11,170
premye pran 4 a, Lè sa a, 15 an, Lè sa a, 50 an, Lè sa a, 108 la.

77
00:05:11,170 --> 00:05:15,120
Machin rantre 8, 42 ak 16, 23,

78
00:05:15,120 --> 00:05:22,440
nou premye pran 8 a, Lè sa a, 16 an, Lè sa a, 23 an, Lè sa a, 42 la.

79
00:05:22,440 --> 00:05:27,370
Se konsa, kounye a nou gen jis 2 bay lis gwosè 4, chak nan yo ki se Klase.

80
00:05:27,370 --> 00:05:30,980
Se konsa, kounye a nou rantre sa yo bay lis 2.

81
00:05:30,980 --> 00:05:33,440
Premye nou pran 4 a.

82
00:05:33,440 --> 00:05:36,580
Lè sa a, nou pran 8 la.

83
00:05:36,580 --> 00:05:50,700
Lè sa a, nou pran 15 an ak 16 an, Lè sa a, 23, Lè sa a, 42, Lè sa a, 50, Lè sa a, 108.

84
00:05:50,700 --> 00:05:52,220
Ak nou ap fè.

85
00:05:52,220 --> 00:05:54,900
Nou kounye a gen yon lis Ranje.

86
00:05:54,900 --> 00:05:57,890
Se konsa, kouman vit te sa a, egzakteman?

87
00:05:57,890 --> 00:06:02,000
An tèm teknik, rantre sòt se O (n boutèy demi lit n),

88
00:06:02,000 --> 00:06:07,380
Lè nou konsidere ke tout sòt bil, sòt ensèsyon, ak sòt seleksyon yo se O (n ²).

89
00:06:07,380 --> 00:06:11,120
An reyalite, kòm ou pral aprann vit, ou pa yo pral kapab vini ak yon sòt

90
00:06:11,120 --> 00:06:14,820
ki fè pi bon pase O (n boutèy demi lit n) nan ka jeneral la.

91
00:06:14,820 --> 00:06:19,120
Yon fwa ankò, pa enkyete sou sa a notasyon gwo O, si ou pa fin wè li ankò.

92
00:06:19,120 --> 00:06:23,490
>> Jis konnen ke sa a vle di si nou te vle sòt yon lis reyèlman gwo

93
00:06:23,490 --> 00:06:26,820
sòt bil, sòt ensèsyon, ak seleksyon sòt te kapab potansyèlman pran

94
00:06:26,820 --> 00:06:29,500
siyifikativman pi long pase rantre zèl.

95
00:06:29,500 --> 00:06:33,210
Li pa vle di ke unifye sòt yo ap pi vit pou tout lis

96
00:06:33,210 --> 00:06:36,220
oswa menm pou nenpòt ki lis sèl anba yon gwosè a sèten.

97
00:06:36,220 --> 00:06:41,950
Pou egzanp, sòt ensèsyon ta ka sòt nan pi rapid pou tout lis ki pi piti pase 5 eleman.

98
00:06:41,950 --> 00:06:47,360
Nan pratik, rantre sòt se nòmalman pi vit pou bay lis tankou ti jan 50 eleman.

99
00:06:47,360 --> 00:06:51,120
>> Men, sa a vitès siplemantè pa vini san yon pri.

100
00:06:51,120 --> 00:06:54,770
Kontrèman ak kalite lòt nou an, ki pran yon lis epi modifye lis la nan plas

101
00:06:54,770 --> 00:06:58,740
jiskaske nou jwenn yon lis Ranje, rantre sòt bezwen kèk espas anplis

102
00:06:58,740 --> 00:07:00,900
rantre 2 bay lis yo ansanm.

103
00:07:00,900 --> 00:07:04,690
Nou pa kapab imedyatman sèvi ak lis la sa ki te fizyone nan magazen lis la uni

104
00:07:04,690 --> 00:07:08,880
depi nou ta ka pase sou desizyon eleman ki toujou bezwen yo dwe fizyone.

105
00:07:08,880 --> 00:07:13,540
Espas sa a se yon ti jan nan yon pri, men li anjeneral se pa rezonab.

106
00:07:13,540 --> 00:07:15,330
Epi sa a, li pou sòt unifye.

107
00:07:15,330 --> 00:07:18,490
>> Non mwen se Rob Bowden, ak sa a se CS50.

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

109
00:07:20,500 --> 00:07:24,000
- Ak seleksyon zèl.

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

111
00:07:25,880 --> 00:07:31,480
Oh, te rive nan pran ki soti tou paske mwen chanje ki jan mwen te prezante li.

112
00:07:31,480 --> 00:07:35,680
Lis sou bò gòch la. Sa se te yon Typo.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] mwen vise moute -

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

115
00:07:41,190 --> 00:07:44,190
Mwen pa konnen sa -