1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Inserción Ordigi]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Universitato Harvard]

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

4
00:00:07,290 --> 00:00:13,060
Ni rigardu inserción varo, algoritmo por preni listo de nombroj kaj ordigi ilin.

5
00:00:13,060 --> 00:00:18,300
Algoritmo, memoru, estas simple iom post paŝo proceduro por plenumi taskon.

6
00:00:18,300 --> 00:00:23,640
La baza ideo malantaŭ inserción varo, estas dividi nian liston en du partojn,

7
00:00:23,640 --> 00:00:26,580
a ordo parton kaj unsorted parton.

8
00:00:26,580 --> 00:00:29,290
>> Je ĉiu paŝo de la algoritmo, numero estas movita

9
00:00:29,290 --> 00:00:32,439
de la unsorted porcion al la ordo parto

10
00:00:32,439 --> 00:00:35,680
ĝis fine la tuta listo estas ordigita.

11
00:00:35,680 --> 00:00:43,340
Jen la listo de ses unsorted nombroj - 23, 42, 4, 16, 8, kaj 15.

12
00:00:43,340 --> 00:00:47,680
Ekde ĉi tiuj nombroj estas ne ĉiuj en suprenira ordo, ili estas Unsorted.

13
00:00:47,680 --> 00:00:53,890
Kiel ni ne komencis ordigi tamen, ni konsideras la ses elementoj nia unsorted parton.

14
00:00:53,890 --> 00:00:59,270
>> Iam ni komencu ordigi, ni metos ĉi tiujn ordo numerojn al la maldekstra de tiuj.

15
00:00:59,270 --> 00:01:03,600
Do, ni komencu kun 23, la unua elemento de nia listo.

16
00:01:03,600 --> 00:01:06,930
Ni ne havas elementojn en niaj ordo parto tamen,

17
00:01:06,930 --> 00:01:12,460
do ni simple konsideras 23 al esti la komenco kaj fino de nia ordo parton.

18
00:01:12,460 --> 00:01:16,510
Nun, nia ordo parto havas unu nombro, 23,

19
00:01:16,510 --> 00:01:20,260
kaj nia unsorted parto havas tiuj kvin nombroj.

20
00:01:20,260 --> 00:01:27,320
Ni nun enigi la sekvan numeron de nia unsorted porcion, 42, en la ordo parton.

21
00:01:27,320 --> 00:01:35,930
>> Por tion fari, ni bezonos kompari la 42 al la 23 - la sola elemento en nia ordo parto ĝis nun.

22
00:01:35,930 --> 00:01:41,980
Kvardek du estas pli granda ol 23, do ni povas simple aldonas 42 ĝis la fino

23
00:01:41,980 --> 00:01:45,420
de la ordo parton de la listo. Bonega!

24
00:01:45,420 --> 00:01:51,850
Nun nia ordo parto havas du elementoj, kaj nia unsorted parto havas kvar elementoj.

25
00:01:51,850 --> 00:01:57,200
Do, ni nun movi al la 4, la sekva elemento en la unsorted parton.

26
00:01:57,200 --> 00:02:00,230
Do, kie devus ĉi loki en la ordo parton?

27
00:02:00,230 --> 00:02:04,220
>> Memoru, ni volas meti tiun ciferon en ordo ordo

28
00:02:04,220 --> 00:02:08,680
Tiel niaj ordo parto restas ĝuste ordo en ĉiu momento.

29
00:02:08,680 --> 00:02:14,380
Se ni metas la 4 al la rajto de la 42, tiam nia listo estos el ordo.

30
00:02:14,380 --> 00:02:18,380
Do, ni daŭrigu movas dekstren-al-maldekstra en nia speco parton.

31
00:02:18,380 --> 00:02:23,260
Kiel ni movas, ni ŝanĝi ĉiun numeron malsupren lokon por lasi spacon por la nova numero.

32
00:02:25,440 --> 00:02:31,740
Konsentite, 4 estas ankaŭ malpli ol 23, do ni ne povas meti ĝin ĉi tie ankaŭ ne.

33
00:02:31,740 --> 00:02:34,480
Ni movi la 23 gxustan lokon.

34
00:02:36,500 --> 00:02:43,120
>> Tio signifas ke ni volas meti la 4 en la unua fendo en la ordo parton.

35
00:02:43,120 --> 00:02:46,300
Rimarku kiel ĉi spacon en la listo jam malplena,

36
00:02:46,300 --> 00:02:51,120
ĉar ni estis movanta ordo elementoj suben kiel ni renkontis ilin.

37
00:02:51,120 --> 00:02:52,740
Bone. Do, ni estas duonvoje tie.

38
00:02:52,740 --> 00:02:57,990
Ni daŭrigos nian algoritmon per enmeto de la 16 en la ordo parton.

39
00:02:59,260 --> 00:03:03,820
Dek ses estas malpli ol 42, do ni ŝanĝi la 42 al la rajto.

40
00:03:05,700 --> 00:03:10,190
Dek ses estas ankaŭ malpli ol 23, do ni ankaŭ ŝanĝi tiu elemento.

41
00:03:11,790 --> 00:03:20,820
>> Nun, 16 estas pli granda ol 4. Do, ĝi aspektas kiel ni ŝatus enmeti la 16 inter la 4 kaj la 23.

42
00:03:20,820 --> 00:03:24,620
Dum movante tra la ordo parton de la listo de dekstra al maldekstra,

43
00:03:24,620 --> 00:03:29,160
4 estas la unua numero ni vidis, ke estas pli malgranda ol la nombro

44
00:03:29,160 --> 00:03:31,540
ni provas enmeti.

45
00:03:31,540 --> 00:03:35,820
Do, nun ni povas enigi la 16 en tiun malplenan fendo,

46
00:03:35,820 --> 00:03:40,520
kiu, memoru, ni kreis per movanta elementoj en la varo parton super

47
00:03:40,520 --> 00:03:43,340
kiel ni renkontis ilin.

48
00:03:43,340 --> 00:03:47,900
>> Bone. Nun, ni havas kvar ordo elementoj kaj du unsorted elementoj.

49
00:03:47,900 --> 00:03:51,600
Do, ni movos la 8 en la ordo parton.

50
00:03:51,600 --> 00:03:55,010
Ok estas malpli ol 42.

51
00:03:55,010 --> 00:03:56,940
Ok estas malpli ol 23.

52
00:03:56,940 --> 00:04:00,230
Kaj 8 estas malpli ol 16.

53
00:04:00,230 --> 00:04:03,110
Sed 8 estas pli granda ol 4.

54
00:04:03,110 --> 00:04:07,280
Do, ni ŝatus enmeti la 8 inter la 4 kaj la 16.

55
00:04:09,070 --> 00:04:13,650
Kaj nun ni nur havas unu malpli ero lasis ordigi - la 15.

56
00:04:13,950 --> 00:04:16,589
Dek kvin estas malpli ol 42,

57
00:04:16,589 --> 00:04:19,130
Dek kvin estas malpli ol 23.

58
00:04:19,130 --> 00:04:21,750
Kaj 15 estas malpli ol 16.

59
00:04:21,750 --> 00:04:24,810
Sed 15 estas pli granda ol 8.

60
00:04:24,810 --> 00:04:27,440
>> Do, jen kie ni volas fari nia fina inserción.

61
00:04:28,770 --> 00:04:30,330
Kaj ni faris.

62
00:04:30,330 --> 00:04:33,540
Ni havas ne pli elementoj en la unsorted parton,

63
00:04:33,540 --> 00:04:36,670
kaj nia ordo parto estas en la korekta ordo.

64
00:04:36,670 --> 00:04:40,270
La nombroj estas ordigitaj de plej malgranda al granda.

65
00:04:40,270 --> 00:04:44,330
Do, ni rigardu iujn _pseudocode_ kiu priskribas la paŝojn ni simple ludado.

66
00:04:46,760 --> 00:04:51,740
>> Sur la linio 1, oni povas vidi, ke ni bezonos ankaŭ persisti super ĉiu elemento en la listo

67
00:04:51,740 --> 00:04:57,060
krom la unua, ĉar la unua elemento en la unsorted parton simple fariĝis

68
00:04:57,060 --> 00:05:00,220
la unua elemento en la ordo parton.

69
00:05:00,220 --> 00:05:06,320
Sur linioj 2 kaj 3, ni konservanta trako de nia nuna loko en la unsorted parton.

70
00:05:06,320 --> 00:05:10,450
Elemento reprezentas la numeron ni aktuale movante en la ordo parton,

71
00:05:10,450 --> 00:05:15,600
kaj j reprezentas nian indekson en la unsorted parton.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, ni ripetanta tra la ordo parton de dekstra al maldekstra.

73
00:05:20,980 --> 00:05:26,010
Ni volas halti ripetanta fojon la elemento al la maldekstra de nia aktuala pozicio

74
00:05:26,010 --> 00:05:30,050
estas malpli ol la elemento ni provas enmeti.

75
00:05:30,050 --> 00:05:35,600
Sur la linio 5, ni sxangxigxantaj ĉiu elemento, ni renkontas unu spacon por la rajto.

76
00:05:35,600 --> 00:05:40,950
Tiel, ni havos klaran spacon por enmeti en kiam ni trovas la unuan elementon

77
00:05:40,950 --> 00:05:44,080
malpli ol la elemento ni moviĝas.

78
00:05:44,080 --> 00:05:50,800
Sur la linio 6, ni ĝisdatigi nian nombrilo daŭrigi movi lasis tra la ordo parton.

79
00:05:50,800 --> 00:05:56,860
Fine, la linio 7, ni enmeto de la elemento en la ordo parton de la listo.

80
00:05:56,860 --> 00:06:00,020
>> Ni scias ke ĝi estas bone por enmeti en pozicio j,

81
00:06:00,020 --> 00:06:05,360
ĉar ni jam movis la elemento kiu kutimis esti tie unu spacon por la rajto.

82
00:06:05,360 --> 00:06:09,460
Memoru, ni movi tra la ordo parton de dekstra al maldekstra,

83
00:06:09,460 --> 00:06:13,960
sed ni movi tra la unsorted parton de maldekstre al dekstre.

84
00:06:13,960 --> 00:06:19,090
Bone. Ni nun rigardu kiel longe kurante ke algoritmo prenita.

85
00:06:19,090 --> 00:06:25,300
Ni unue demandi la demandon kiom da tempo necesas por ĉi tiu algoritmo por kuri en la plej malbona kazo.

86
00:06:25,300 --> 00:06:29,040
Memori, ke ni reprezentas ĉi rula tempo kun Granda a skribmaniero.

87
00:06:32,530 --> 00:06:38,500
Por ordigi nian liston, ni havis ankaŭ persisti super la elementoj en la unsorted parton,

88
00:06:38,500 --> 00:06:43,430
kaj por ĉiu el tiuj elementoj, potenciale super ĉiuj elementoj en la ordo parton.

89
00:06:43,430 --> 00:06:47,950
Intuicie, ĉi sonojn kiel O (n ^ 2) operacio.

90
00:06:47,950 --> 00:06:51,840
>> Rigardante nian _pseudocode_, ni havas buklo anidado ene alia buklo,

91
00:06:51,840 --> 00:06:55,290
kiuj ja sonas kiel O (n ^ 2) operacio.

92
00:06:55,290 --> 00:07:01,590
Tamen, la ordo porcion de listo ne enhavis la tutan liston ĝis la fino.

93
00:07:01,590 --> 00:07:06,920
Tamen ni povus potenciale enigi novan elementon al la komenco de la ordo parto

94
00:07:06,920 --> 00:07:09,320
sur ĉiu ripeto de la algoritmo,

95
00:07:09,320 --> 00:07:14,500
kio signifas, ke ni devus rigardi ĉiu ero aktuale en la ordo parton.

96
00:07:14,500 --> 00:07:20,090
Do, tio signifas ke ni povus potenciale fari komparon por la dua ero,

97
00:07:20,090 --> 00:07:24,660
du komparoj por tria elemento, kaj tiel plu.

98
00:07:24,660 --> 00:07:32,480
Do, la tuta kvanto de paŝoj estas la sumo de la entjeroj de 1 al la longo de la listo minus 1.

99
00:07:32,480 --> 00:07:35,240
Ni povas reprezenti ĉi kun sumado.

100
00:07:41,170 --> 00:07:47,270
>> Ni ne iros al sumadoj, sumadas tie, sed ĝi rezultas ke tiu sumado estas egala al

101
00:07:47,270 --> 00:07:57,900
n (n - 1) super 2, kiu estas ekvivalenta n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Kiam parolante pri asimptota runtime,

103
00:08:00,800 --> 00:08:05,170
ĉi n ^ 2 terminon tuj regi tiun n termino.

104
00:08:05,170 --> 00:08:11,430
Do, inserción varo estas Granda O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Kio se ni kuris inserción speco sur jam ordo listo.

106
00:08:16,150 --> 00:08:20,960
En tiu kazo, ni havus simple konstrui la ordo parton de maldekstre al dekstre.

107
00:08:20,960 --> 00:08:25,050
Do, ni nur bezonas de la ordo de n paŝoj.

108
00:08:25,050 --> 00:08:29,740
>> Tio signifas ke inserción speco havas pli okazo agado de n,

109
00:08:29,740 --> 00:08:34,130
kiuj ni reprezentas kun Ω (n).

110
00:08:34,130 --> 00:08:36,190
Kaj tio estas por inserción varo,

111
00:08:36,190 --> 00:08:40,429
nur unu el la multaj algoritmoj povas uzi por ordigi liston.

112
00:08:40,429 --> 00:08:43,210
Mia nomo estas Tommy, kaj ĉi tiu estas CS50.

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

114
00:08:46,110 --> 00:08:49,230
Ho, vi simple ne povas ĉesi, ke iam ĝi komenciĝas.

115
00:09:01,620 --> 00:09:04,760
Ho, ni faris tion - >> Eksplodo!