1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Triye ensèrsyon]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Inivèsite Harvard]

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

4
00:00:07,290 --> 00:00:13,060
Se pou nou pran yon gade nan sòt ensèsyon, yon algorithm pou pran yon lis nimewo ak Fouye yo.

5
00:00:13,060 --> 00:00:18,300
Yon algorithm, sonje, se senpleman yon pwosedi etap-pa-etap pou reyalize yon travay.

6
00:00:18,300 --> 00:00:23,640
Lide a debaz dèyè sòt ensèsyon, se divize lis nou an nan de pòsyon,

7
00:00:23,640 --> 00:00:26,580
yon pòsyon klase epi yon pòsyon klase.

8
00:00:26,580 --> 00:00:29,290
>> Nan chak etap nan algorithm la, se yon nimewo te deplase

9
00:00:29,290 --> 00:00:32,439
soti nan pòsyon ki klase pòsyon nan Ranje

10
00:00:32,439 --> 00:00:35,680
jiskaske evantyèlman se lis la tout antye Ranje.

11
00:00:35,680 --> 00:00:43,340
Isit la se lis la nan sis chif klase - 23, 42, 4, 16, 8, ak 15.

12
00:00:43,340 --> 00:00:47,680
Depi nimewo sa yo se pa tout nan Ascending lòd yo, yo ap klase.

13
00:00:47,680 --> 00:00:53,890
Kòm nou pa te kòmanse Fouye ankò, nou pral konsidere tout eleman sis pòsyon klase nou an.

14
00:00:53,890 --> 00:00:59,270
>> Yon fwa nou kòmanse Fouye, nou pral mete nimewo sa yo Ranje a gòch la nan sa yo.

15
00:00:59,270 --> 00:01:03,600
Se konsa, kite la kòmanse avèk 23, eleman an premye nan lis nou an.

16
00:01:03,600 --> 00:01:06,930
Nou pa gen okenn eleman nan Ranje pòsyon nou an ankò,

17
00:01:06,930 --> 00:01:12,460
kidonk kite la tou senpleman konsidere 23 yo dwe nan kòmansman an ak nan fen Ranje pòsyon nou an.

18
00:01:12,460 --> 00:01:16,510
Koulye a, pòsyon Ranje nou an ki gen yon sèl nimewo, 23,

19
00:01:16,510 --> 00:01:20,260
ansanm ak pòsyon klase nou an ki gen nimewo sa yo senk.

20
00:01:20,260 --> 00:01:27,320
Se pou nou kounye a insert pwochen nonb nan pòsyon klase nou an, 42, nan pòsyon nan Klase.

21
00:01:27,320 --> 00:01:35,930
>> Pou fè sa, nou pral bezwen konpare salè 42 a 23 an - eleman nan sèlman nan Ranje pòsyon nou byen lwen tèlman.

22
00:01:35,930 --> 00:01:41,980
Karant-de se pi gwo pase 23, pou nou ka tou senpleman ajoute 42 nan fen a

23
00:01:41,980 --> 00:01:45,420
nan pòsyon an Ranje nan lis la. Gwo!

24
00:01:45,420 --> 00:01:51,850
Koulye a, pòsyon Ranje nou an ki gen de eleman, ansanm ak pòsyon klase nou an ki gen kat eleman.

25
00:01:51,850 --> 00:01:57,200
Se konsa, kite a kounye a deplase a 4 an, eleman nan pwochen nan pòsyon klase.

26
00:01:57,200 --> 00:02:00,230
Se konsa, kote yo ta dwe sa a dwe mete nan pòsyon Ranje?

27
00:02:00,230 --> 00:02:04,220
>> Sonje byen, nou vle mete nan nimewo sa a nan Ranje lòd

28
00:02:04,220 --> 00:02:08,680
Se konsa pòsyon Ranje nou rete kòrèkteman Klase nan tout fwa.

29
00:02:08,680 --> 00:02:14,380
Si nou mete 4 an a dwat a 42 an, Lè sa a, lis nou an pral soti nan lòd.

30
00:02:14,380 --> 00:02:18,380
Se konsa, kite a kontinye deplase dwa-a-gòch nan pòsyon sòt nou an.

31
00:02:18,380 --> 00:02:23,260
Kòm nou deplase, kite la chanje chak nimewo desann yon kote ki pou fè plas pou nimewo a nouvo.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 se tou pi piti pase 23, se konsa nou pa ka mete l 'isit la swa.

33
00:02:31,740 --> 00:02:34,480
Kite yo deplase 23 dwa yon sèl kote a.

34
00:02:36,500 --> 00:02:43,120
>> Sa vle di nou ta renmen yo mete 4 an nan plas an premye nan pòsyon Ranje.

35
00:02:43,120 --> 00:02:46,300
Avi sou jan espas sa a nan lis la te deja vid,

36
00:02:46,300 --> 00:02:51,120
paske nou ve yo te deplase Ranje eleman desann kòm nou te rankontre yo.

37
00:02:51,120 --> 00:02:52,740
Tout dwa. Se konsa, nou ap mwatye a.

38
00:02:52,740 --> 00:02:57,990
Se pou nou kontinye algorithm nou yo lè nou mete 16 a nan pòsyon nan Klase.

39
00:02:59,260 --> 00:03:03,820
Sèz se mwens pase 42, kidonk kite nan chanjman 42 la a dwat la.

40
00:03:05,700 --> 00:03:10,190
Sèz tou se mwens pase 23, kidonk kite a tou chanjman ki eleman.

41
00:03:11,790 --> 00:03:20,820
>> Koulye a, 16 se pi gran pase 4. Se konsa, li sanble nou ta renmen insert 16 ki genyen ant 4 an ak 23 an.

42
00:03:20,820 --> 00:03:24,620
Pandan ke mouvman atravè pòsyon nan Ranje nan lis la de dwat a gòch,

43
00:03:24,620 --> 00:03:29,160
4 se nimewo a premye nou te wè ki se pi piti pase kantite

44
00:03:29,160 --> 00:03:31,540
nou ap eseye insert.

45
00:03:31,540 --> 00:03:35,820
Se konsa, kounye a nou ka insert 16 la nan sa a plas vid,

46
00:03:35,820 --> 00:03:40,520
ki, sonje, nou te kreye pa eleman deplase nan pòsyon sòt sou

47
00:03:40,520 --> 00:03:43,340
kòm nou te rankontre yo.

48
00:03:43,340 --> 00:03:47,900
>> Tout dwa. Koulye a, nou gen kat Ranje eleman ak de eleman klase.

49
00:03:47,900 --> 00:03:51,600
Se konsa, kite yo deplase 8 la nan pòsyon nan Klase.

50
00:03:51,600 --> 00:03:55,010
Uit se mwens pase 42.

51
00:03:55,010 --> 00:03:56,940
Uit se mwens pase 23.

52
00:03:56,940 --> 00:04:00,230
Ak 8 gen mwens pase 16.

53
00:04:00,230 --> 00:04:03,110
Men, 8 se pi gran pase 4.

54
00:04:03,110 --> 00:04:07,280
Se konsa, nou ta renmen insert 8 ki genyen ant 4 an ak 16 an.

55
00:04:09,070 --> 00:04:13,650
Epi, koulye a nou jis gen yon sèl plis eleman goch a sòt - 15 la.

56
00:04:13,950 --> 00:04:16,589
Kenz se mwens pase 42,

57
00:04:16,589 --> 00:04:19,130
Kenz se mwens pase 23.

58
00:04:19,130 --> 00:04:21,750
Ak 15 gen mwens pase 16.

59
00:04:21,750 --> 00:04:24,810
Men, 15 se pi plis pase 8.

60
00:04:24,810 --> 00:04:27,440
>> Se konsa, isit la se kote nou vle fè ensèsyon final nou an.

61
00:04:28,770 --> 00:04:30,330
Ak nou ap fè.

62
00:04:30,330 --> 00:04:33,540
Nou pa gen okenn eleman plis nan pòsyon klase,

63
00:04:33,540 --> 00:04:36,670
ansanm ak pòsyon Ranje nou an se yo nan lòd ki kòrèk la.

64
00:04:36,670 --> 00:04:40,270
Nimewo sa yo yo te bay lòd soti nan pi piti pi gwo.

65
00:04:40,270 --> 00:04:44,330
Se konsa, kite a pran yon gade nan kèk pseudocode ki dekri etap sa yo nou jis fèt.

66
00:04:46,760 --> 00:04:51,740
>> Sou liy 1, nou ka wè ke nou pral bezwen repekte sou chak eleman nan lis la

67
00:04:51,740 --> 00:04:57,060
eksepte premye a, depi nan premye eleman nan pòsyon klase pwal tou senpleman vin

68
00:04:57,060 --> 00:05:00,220
eleman nan premye nan pòsyon nan Klase.

69
00:05:00,220 --> 00:05:06,320
Sou liy 2 ak 3, n ap kenbe tras de kote nou an ki ajou nan pòsyon klase.

70
00:05:06,320 --> 00:05:10,450
Eleman reprezante kantite a nou yo kounye a paralize nan pòsyon nan Ranje,

71
00:05:10,450 --> 00:05:15,600
ak j reprezante endèks nou an, nan pòsyon ki klase.

72
00:05:15,600 --> 00:05:20,980
>> Sou liy 4, nou ap iteration nan pòsyon nan Ranje soti nan dwa a goch.

73
00:05:20,980 --> 00:05:26,010
Nou vle sispann iteration yon fwa eleman ki nan kite nan pozisyon nou an ki ajou

74
00:05:26,010 --> 00:05:30,050
se mwens pase eleman nan nou ap eseye insert.

75
00:05:30,050 --> 00:05:35,600
Sou liy 5, nou ap déplacement chak eleman nou kontre yon sèl espas a dwat la.

76
00:05:35,600 --> 00:05:40,950
Nan fason sa a, nou pral gen yon espas klè insert nan lè nou jwenn eleman nan premye

77
00:05:40,950 --> 00:05:44,080
mwens pase eleman an ke nou ap deplase.

78
00:05:44,080 --> 00:05:50,800
Sou liy, 6, nou ap mete ajou kontwa nou kontinye pou avanse pou pi kite nan pòsyon nan Klase.

79
00:05:50,800 --> 00:05:56,860
Finalman, sou liy 7, n ap mete eleman an nan pòsyon nan Ranje nan lis la.

80
00:05:56,860 --> 00:06:00,020
>> Nou konnen ke li oke insert nan j pozisyon,

81
00:06:00,020 --> 00:06:05,360
paske nou te deja te deplase eleman a ki itilize yo dwe gen yon espas a dwat la.

82
00:06:05,360 --> 00:06:09,460
Sonje byen, nou ap mouvman atravè pòsyon nan Ranje soti nan dwa a goch,

83
00:06:09,460 --> 00:06:13,960
men nou ap mouvman atravè pòsyon nan klase de gòch a dwat.

84
00:06:13,960 --> 00:06:19,090
Tout dwa. Se pou nou kounye a pran yon gade nan konbyen tan kouri ki algorithm te pran.

85
00:06:19,090 --> 00:06:25,300
Nou pral premye mande kesyon an konbyen tan li pran pou sa a algorithm nan kouri nan ka ki pi mal la.

86
00:06:25,300 --> 00:06:29,040
Sonje ke nou reprezante tan sa a ap kouri avèk notasyon Big O.

87
00:06:32,530 --> 00:06:38,500
Yo nan lòd yo klase lis nou an, nou te repekte sou eleman yo nan pòsyon ki klase,

88
00:06:38,500 --> 00:06:43,430
epi pou chak moun sa yo eleman, potansyèlman sou tout eleman nan pòsyon nan Klase.

89
00:06:43,430 --> 00:06:47,950
Intuitivement, sa a son tankou yon operasyon O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> Gade nan pseudocode nou an, nou gen yon riban pare solèy andedan yon lòt bouk,

91
00:06:51,840 --> 00:06:55,290
ki, tout bon, son tankou yon operasyon O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
Sepandan, pòsyon nan Ranje nan lis pa t 'gen ladan lis la tout antye jouk nan fen an trè.

93
00:07:01,590 --> 00:07:06,920
Toujou, nou te kapab potansyèlman insert yon eleman nouvo nan kòmansman la anpil nan pòsyon nan Ranje

94
00:07:06,920 --> 00:07:09,320
sou chak iterasyon nan algorithm a,

95
00:07:09,320 --> 00:07:14,500
ki vle di ke nou ta gen fè yon gade nan chak eleman kounye a nan pòsyon Ranje.

96
00:07:14,500 --> 00:07:20,090
Se konsa, sa vle di nou te kapab potansyèlman fè yon sèl konparezon pou eleman, dezyèm lan,

97
00:07:20,090 --> 00:07:24,660
de konparezon pou eleman nan twazyèm, ak sou sa.

98
00:07:24,660 --> 00:07:32,480
Se konsa, kantite total etap a se sòm total nonm antye relatif yo nan 1 rive nan longè nan lis la mwens 1.

99
00:07:32,480 --> 00:07:35,240
Nou ka reprezante sa a ak yon somasyon.

100
00:07:41,170 --> 00:07:47,270
>> Nou pa pral antre summations isit la, men li sanble ke sa a somasyon ki egal a

101
00:07:47,270 --> 00:07:57,900
n (n - 1) plis pase 2, ki se ekivalan n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Lè w ap pale sou ègzekutabl asenptotik,

103
00:08:00,800 --> 00:08:05,170
sa a n ^ 2 tèm ki pral domine tèm sa a n.

104
00:08:05,170 --> 00:08:11,430
Se konsa, sòt ensèsyon se Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
E si nou kouri sòt ensèsyon sou yon lis deja klase.

106
00:08:16,150 --> 00:08:20,960
Nan ka sa a, nou ta tou senpleman bati pòsyon nan Ranje soti nan gòch a dwat.

107
00:08:20,960 --> 00:08:25,050
Se konsa,, nou pral bezwen sèlman sou lòd la n etap.

108
00:08:25,050 --> 00:08:29,740
>> Sa vle di ke sòt ensèsyon an gen yon pèfòmans pi bon-ka nan n,

109
00:08:29,740 --> 00:08:34,130
ki nou reprezante ak Ω (n).

110
00:08:34,130 --> 00:08:36,190
Epi sa a, li pou sòt ensèsyon,

111
00:08:36,190 --> 00:08:40,429
jis youn nan algoritm yo anpil nou ka itilize yo sòt yon lis.

112
00:08:40,429 --> 00:08:43,210
Non mwen se Tommy, e sa se CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, ou jis pa ka sispann ke yon fwa li kòmanse.

115
00:09:01,620 --> 00:09:04,760
Oh, nou te fè sa - Boom >>!