1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Infogande Panga]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Chuo Kikuu cha Harvard]

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

4
00:00:07,290 --> 00:00:13,060
Hebu tuangalie aina insertion, algorithm kwa ajili ya kuchukua orodha ya namba na kuchagua yao.

5
00:00:13,060 --> 00:00:18,300
algorithm, kumbuka, ni tu utaratibu wa hatua kwa hatua kwa ajili ya kukamilisha kazi.

6
00:00:18,300 --> 00:00:23,640
wazo la msingi nyuma ya aina insertion, ni kugawanya orodha yetu katika sehemu mbili,

7
00:00:23,640 --> 00:00:26,580
sehemu sorted na sehemu zisizochambuliwa.

8
00:00:26,580 --> 00:00:29,290
>> Katika kila hatua ya algorithm, idadi ni wakiongozwa

9
00:00:29,290 --> 00:00:32,439
kutoka sehemu zisizochambuliwa kwa sehemu sorted

10
00:00:32,439 --> 00:00:35,680
mpaka hatimaye orodha nzima ni Iliyopangwa.

11
00:00:35,680 --> 00:00:43,340
Hapa ni orodha ya namba sita zisizochambuliwa - 23, 42, 4, 16, 8, na 15.

12
00:00:43,340 --> 00:00:47,680
Tangu hizi namba ni si wote katika wakipanda ili, wao ni zisizochambuliwa.

13
00:00:47,680 --> 00:00:53,890
Tangu sisi si kuanza kuchagua bado, tutaweza kufikiria yote vipengele sita sehemu yetu zisizochambuliwa.

14
00:00:53,890 --> 00:00:59,270
>> Mara sisi kuanza kuchagua, tutaweza kuweka namba hizi sorted ya kushoto ya haya.

15
00:00:59,270 --> 00:01:03,600
Hivyo, hebu kuanza na 23, kipengele kwanza katika orodha yetu.

16
00:01:03,600 --> 00:01:06,930
Hatuna mambo yoyote katika sehemu yetu ya sorted bado,

17
00:01:06,930 --> 00:01:12,460
hivyo hebu fikiria tu 23 kuwa mwanzo na mwisho wa sehemu yetu ya Iliyopangwa.

18
00:01:12,460 --> 00:01:16,510
Sasa, sehemu yetu ina Iliyopangwa namba moja, 23,

19
00:01:16,510 --> 00:01:20,260
na sehemu yetu zisizochambuliwa ina namba hizi tano.

20
00:01:20,260 --> 00:01:27,320
Hebu sasa Insert namba inayofuata katika sehemu yetu ya zisizochambuliwa, 42, katika sehemu Iliyopangwa.

21
00:01:27,320 --> 00:01:35,930
>> Kwa kufanya hivyo, tutaweza haja ya kulinganisha 42-23 - kipengele tu katika sehemu yetu ya sorted hivyo mbali.

22
00:01:35,930 --> 00:01:41,980
Arobaini na mbili ni kubwa kuliko 23, ili tuweze tu append 42 hadi mwisho

23
00:01:41,980 --> 00:01:45,420
ya fungu sorted ya orodha. Mkuu!

24
00:01:45,420 --> 00:01:51,850
Sasa sehemu yetu sorted ina mambo mawili, na sehemu yetu zisizochambuliwa una mambo manne.

25
00:01:51,850 --> 00:01:57,200
Hivyo, hebu sasa hoja ya 4, kipengele ijayo katika sehemu zisizochambuliwa.

26
00:01:57,200 --> 00:02:00,230
Hivyo, ambapo lazima hii kuwekwa katika fungu sorted?

27
00:02:00,230 --> 00:02:04,220
>> Kumbuka, tunataka kuweka namba hii ili sorted

28
00:02:04,220 --> 00:02:08,680
hivyo sehemu yetu sorted bado usahihi sorted wakati wote.

29
00:02:08,680 --> 00:02:14,380
Tukiweka 4 na haki ya 42, basi orodha yetu itakuwa nje ya utaratibu.

30
00:02:14,380 --> 00:02:18,380
Hivyo, hebu kuendelea kusonga kulia-hadi-kushoto katika aina sehemu yetu.

31
00:02:18,380 --> 00:02:23,260
Kama sisi hoja, hebu kuhama kila idadi chini mahali kufanya chumba kwa idadi mpya.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 pia ni chini ya 23, hivyo hatuwezi kuiweka hapa aidha.

33
00:02:31,740 --> 00:02:34,480
Hebu hoja 23 haki ya mtu mahali.

34
00:02:36,500 --> 00:02:43,120
>> Hiyo ina maana tunatarajia kuweka 4 katika yanayopangwa kwanza katika sehemu Iliyopangwa.

35
00:02:43,120 --> 00:02:46,300
Angalia jinsi hii nafasi katika orodha ilikuwa tayari tupu,

36
00:02:46,300 --> 00:02:51,120
kwa sababu tumekuwa kusonga vipengele sorted chini kama tumekuwa wamekutana yao.

37
00:02:51,120 --> 00:02:52,740
Wote haki. Hivyo, sisi ni nusu ya huko.

38
00:02:52,740 --> 00:02:57,990
Wacha tuendelee algorithm yetu kwa kuingiza 16 katika sehemu Iliyopangwa.

39
00:02:59,260 --> 00:03:03,820
Kumi na sita ni chini ya 42, hivyo hebu kuhama 42 ya kulia.

40
00:03:05,700 --> 00:03:10,190
Kumi na sita pia ni chini ya 23, hivyo hebu pia kuhama kwamba kipengele.

41
00:03:11,790 --> 00:03:20,820
>> Sasa, 16, ni mkubwa kuliko 4. Hivyo, inaonekana kama tunatarajia kuingiza 16 kati ya 4 na 23.

42
00:03:20,820 --> 00:03:24,620
Wakati kusonga kupitia sehemu ya orodha Iliyopangwa kutoka kulia kwenda kushoto,

43
00:03:24,620 --> 00:03:29,160
4 ni idadi ya kwanza tumeona kwamba ni ndogo kuliko idadi ya

44
00:03:29,160 --> 00:03:31,540
sisi ni kujaribu kuingiza.

45
00:03:31,540 --> 00:03:35,820
Hivyo, sasa tunaweza Insert 16 katika yanayopangwa hii tupu,

46
00:03:35,820 --> 00:03:40,520
ambayo, kumbuka, tumekuwa umba na mambo kusonga katika sehemu aina zaidi ya

47
00:03:40,520 --> 00:03:43,340
kama tumekuwa wamekutana yao.

48
00:03:43,340 --> 00:03:47,900
>> Wote haki. Sasa, tuna nne vipengele sorted na mbili vipengele zisizochambuliwa.

49
00:03:47,900 --> 00:03:51,600
Hivyo, hebu hoja 8 katika sehemu Iliyopangwa.

50
00:03:51,600 --> 00:03:55,010
Nane ni chini ya 42.

51
00:03:55,010 --> 00:03:56,940
Nane ni chini ya 23.

52
00:03:56,940 --> 00:04:00,230
Na 8 ni chini ya 16.

53
00:04:00,230 --> 00:04:03,110
Lakini 8, ni mkubwa kuliko 4.

54
00:04:03,110 --> 00:04:07,280
Hivyo, tunatarajia kuingiza 8 kati ya 4 na 16.

55
00:04:09,070 --> 00:04:13,650
Na sasa sisi tu moja zaidi ya kipengele kushoto kutatua - 15.

56
00:04:13,950 --> 00:04:16,589
Kumi na tano ni chini ya 42,

57
00:04:16,589 --> 00:04:19,130
Kumi na tano ni chini ya 23.

58
00:04:19,130 --> 00:04:21,750
Na 15 ni chini ya 16.

59
00:04:21,750 --> 00:04:24,810
Lakini 15 ni mkuu zaidi kuliko 8.

60
00:04:24,810 --> 00:04:27,440
>> Kwa hiyo, hapa ni mahali ambapo tunataka kufanya insertion yetu ya mwisho.

61
00:04:28,770 --> 00:04:30,330
Na sisi ni kosa.

62
00:04:30,330 --> 00:04:33,540
Tuna mambo tena katika sehemu zisizochambuliwa,

63
00:04:33,540 --> 00:04:36,670
na sehemu yetu ni Iliyopangwa katika mpangilio sahihi.

64
00:04:36,670 --> 00:04:40,270
idadi ni amri kutoka wadogo na ukubwa.

65
00:04:40,270 --> 00:04:44,330
Hivyo, hebu tuangalie baadhi pseudocode kwamba inaelezea hatua sisi tu kutumbuiza.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, tunaweza kuona kwamba tutaweza haja ya iterate juu ya kila kipengele katika orodha

67
00:04:51,740 --> 00:04:57,060
ila kwanza, tangu kipengele kwanza katika sehemu zisizochambuliwa mapenzi tu kuwa

68
00:04:57,060 --> 00:05:00,220
kipengele kwanza katika sehemu Iliyopangwa.

69
00:05:00,220 --> 00:05:06,320
Juu ya mistari 2 na 3, sisi ni kuweka wimbo wa nafasi yetu ya sasa katika sehemu zisizochambuliwa.

70
00:05:06,320 --> 00:05:10,450
Kipengele inawakilisha idadi sisi sasa kuhamia katika sehemu Iliyopangwa,

71
00:05:10,450 --> 00:05:15,600
na j inawakilisha index yetu katika sehemu zisizochambuliwa.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, tuko iterating kupitia sehemu sorted kutoka kulia kwenda kushoto.

73
00:05:20,980 --> 00:05:26,010
Tunataka kukomesha iterating mara moja kipengele upande wa kushoto wa msimamo wetu wa sasa

74
00:05:26,010 --> 00:05:30,050
ni chini ya kipengele sisi ni kujaribu kuingiza.

75
00:05:30,050 --> 00:05:35,600
On line 5, sisi ni shifting kila kipengele sisi kukutana moja nafasi ya kulia.

76
00:05:35,600 --> 00:05:40,950
Kwa njia hiyo, tutaweza kuwa na nafasi ya wazi ya kuingiza katika wakati sisi kupata kipengele kwanza

77
00:05:40,950 --> 00:05:44,080
chini ya kipengele tuko kusonga mbele.

78
00:05:44,080 --> 00:05:50,800
On line 6, sisi ni uppdatering counter yetu kuendelea kwa hoja kushoto kupitia sehemu Iliyopangwa.

79
00:05:50,800 --> 00:05:56,860
Hatimaye, katika mstari wa 7, sisi ni kuingiza kipengele katika sehemu sorted ya orodha.

80
00:05:56,860 --> 00:06:00,020
>> Tunajua kwamba ni sawa na kuingiza ndani ya j nafasi,

81
00:06:00,020 --> 00:06:05,360
kwa sababu tumekuwa tayari wakiongozwa kipengele kwamba kutumika kuwa kuna nafasi moja ya kulia.

82
00:06:05,360 --> 00:06:09,460
Kumbuka, sisi ni kusonga kupitia sehemu sorted kutoka kulia kwenda kushoto,

83
00:06:09,460 --> 00:06:13,960
lakini sisi ni kusonga kupitia sehemu zisizochambuliwa kutoka kushoto kwenda kulia.

84
00:06:13,960 --> 00:06:19,090
Wote haki. Hebu sasa tuangalie jinsi ya muda mrefu mbio kwamba alichukua algorithm.

85
00:06:19,090 --> 00:06:25,300
Tutaweza kwanza kuuliza swali jinsi gani kuchukua muda mrefu kwa algorithm hii na kukimbia katika hali mbaya.

86
00:06:25,300 --> 00:06:29,040
Kumbuka kwamba sisi kuwakilisha hii wakati mbio na nukuu Kubwa O.

87
00:06:32,530 --> 00:06:38,500
Ili aina orodha yetu, tulikuwa na iterate juu ya vipengele katika sehemu zisizochambuliwa,

88
00:06:38,500 --> 00:06:43,430
na kwa kila moja ya mambo hayo, uwezekano juu ya mambo yote katika sehemu Iliyopangwa.

89
00:06:43,430 --> 00:06:47,950
Intuitively, hii inaonekana kama operesheni O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> Kuangalia pseudocode yetu, tuna kitanzi nested ndani ya kitanzi mwingine,

91
00:06:51,840 --> 00:06:55,290
ambayo, kwa hakika, inaonekana kama operesheni O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
Hata hivyo, sehemu ya orodha Iliyopangwa hakuwa vyenye orodha nzima mpaka mwisho sana.

93
00:07:01,590 --> 00:07:06,920
Hata hivyo, sisi inaweza uwezekano Insert kipengele mpya mwanzoni mwa sehemu sorted

94
00:07:06,920 --> 00:07:09,320
juu ya kila iteration ya algorithm,

95
00:07:09,320 --> 00:07:14,500
ambayo ina maana kwamba tunatarajia kuwa na kuangalia kila kipengele sasa katika sehemu Iliyopangwa.

96
00:07:14,500 --> 00:07:20,090
Hivyo, hiyo ina maana sisi inaweza uwezekano kufanya moja kulinganisha kwa kipengele cha pili,

97
00:07:20,090 --> 00:07:24,660
mbili kulinganisha kwa kipengele cha tatu, na kadhalika.

98
00:07:24,660 --> 00:07:32,480
Hivyo, idadi ya jumla ya hatua ni jumla ya integers kutoka 1 kwa urefu wa orodha minus 1.

99
00:07:32,480 --> 00:07:35,240
Tunaweza kuwakilisha jambo hili kwa summation.

100
00:07:41,170 --> 00:07:47,270
>> Sisi si kwenda katika summations hapa, lakini zinageuka kuwa summation hii ni sawa na

101
00:07:47,270 --> 00:07:57,900
n (n - 1) zaidi ya 2, ambayo ni sawa n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Tunapozungumzia Runtime asymptotic,

103
00:08:00,800 --> 00:08:05,170
n ^ 2 mrefu ni kwenda kutawala muda huu n.

104
00:08:05,170 --> 00:08:11,430
Hivyo, insertion aina ni Kubwa O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Nini kama sisi mbio insertion aina katika orodha tayari Iliyopangwa.

106
00:08:16,150 --> 00:08:20,960
Katika kesi hiyo, tunatarajia tu kujenga sehemu sorted kutoka kushoto kwenda kulia.

107
00:08:20,960 --> 00:08:25,050
Hivyo, tutaweza tu haja juu ya utaratibu wa hatua n.

108
00:08:25,050 --> 00:08:29,740
>> Hiyo ina maana kwamba insertion aina ina utendaji bora-kesi ya n,

109
00:08:29,740 --> 00:08:34,130
ambayo sisi kuwakilisha kwa Ω (n).

110
00:08:34,130 --> 00:08:36,190
Na hiyo ni kwa ajili ya aina insertion,

111
00:08:36,190 --> 00:08:40,429
moja tu ya algorithms wengi tunaweza kutumia aina orodha.

112
00:08:40,429 --> 00:08:43,210
Jina langu ni Tommy, na hii ni CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, wewe tu hawezi kuacha kuwa mara kinapoanza.

115
00:09:01,620 --> 00:09:04,760
Oh, sisi gani kwamba - >> Boom!