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

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Chuo Kikuu cha Harvard]

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

4
00:00:07,000 --> 00:00:09,000
Hebu majadiliano kuhusu aina kuunganisha.

5
00:00:09,000 --> 00:00:14,000
Hadi sasa wewe ve kuonekana Bubble aina, aina insertion, na aina ya uteuzi.

6
00:00:14,000 --> 00:00:17,000
Ingawa mimi itabidi aina ya wimbi mkono wangu katika nini maana na bora zaidi,

7
00:00:17,000 --> 00:00:21,000
kuchanganya aina ujumla hufanya bora kuliko yoyote ya aina hizi 3.

8
00:00:22,000 --> 00:00:27,000
>> Lakini kabla ya kuzungumza juu ya aina kuunganisha, hebu majadiliano juu ya kuunganisha 2 orodha Iliyopangwa.

9
00:00:27,000 --> 00:00:31,000
Tutamwita mchakato wa kuchukua 2 orodha Iliyopangwa, kama haya,

10
00:00:31,000 --> 00:00:35,000
na kufanya moja sorted orodha nje ya yao - kuunganisha orodha.

11
00:00:35,000 --> 00:00:37,750
Tunawezaje kufanya hivyo?

12
00:00:37,750 --> 00:00:41,290
Naam, wazo moja ni moja tu fimbo orodha kwenye mwisho wa orodha nyingine

13
00:00:41,290 --> 00:00:43,830
na kisha kusababisha aina orodha.

14
00:00:43,830 --> 00:00:47,220
>> Wakati kazi hii, ni mengi ya kazi ya lazima.

15
00:00:47,220 --> 00:00:49,900
Tunaweza kufanya hivyo kwa kasi zaidi kuliko tu kuchagua.

16
00:00:49,900 --> 00:00:54,100
Ona kwamba wazo moja ni makosa kuchukua tu vikombe alternating kutoka orodha ya kila.

17
00:00:54,100 --> 00:00:56,460
Wakati kwamba inaweza kuonekana kama kazi ya kwanza,

18
00:00:56,460 --> 00:01:05,760
kufanya kwamba sisi kuishia na 4, 8, 15, 23, 16 - ona kwamba 16 na 23 ni nje ya mahali.

19
00:01:05,760 --> 00:01:09,380
Hii ni kwa sababu 2 vipengele kwamba inapaswa kuonekana mfululizo katika orodha enheten

20
00:01:09,380 --> 00:01:11,720
ni katika orodha hiyo ya awali.

21
00:01:11,720 --> 00:01:14,850
Wote 15 na 16 ni katika orodha upande wa kushoto.

22
00:01:14,850 --> 00:01:19,810
hila ni kuchukua faida ya ukweli kwamba orodha zote mbili tayari Iliyopangwa.

23
00:01:19,810 --> 00:01:23,320
Hii ina maana kwamba kama sisi tu kuangalia mambo ya kwanza ya orodha zote mbili -

24
00:01:23,320 --> 00:01:29,580
hapa, 4 na 8 - mmoja wao lazima pia kuwa kipengele kwanza ya orodha enheten.

25
00:01:29,580 --> 00:01:31,620
Naam, kwa nini ni hivyo?

26
00:01:31,620 --> 00:01:33,520
Wote wa orodha hizi tayari Iliyopangwa,

27
00:01:33,520 --> 00:01:38,410
na hivyo aidha 4 au 8 lazima kipengele ndogo wakati sisi kuchanganya orodha 2.

28
00:01:38,410 --> 00:01:41,770
Katika kesi hiyo, ndogo ni 4,

29
00:01:41,770 --> 00:01:46,370
ili tuweze kuchukua nje 4 na kufanya ni kipengele kwanza ya orodha yetu ya enheten.

30
00:01:46,370 --> 00:01:50,710
Sasa tutaendelea kuunganisha iliyobaki vipengele 3 ya orodha ya kwanza

31
00:01:50,710 --> 00:01:52,920
na 4 mambo ya orodha ya pili.

32
00:01:52,920 --> 00:01:57,150
>> Mara nyingine tena, sisi tu haja ya kuangalia kipengele kwanza ya orodha zote mbili.

33
00:01:57,150 --> 00:02:01,060
ndogo ya 2 lazima kipengele pili ya orodha yetu ya enheten.

34
00:02:01,060 --> 00:02:05,440
Wakati huu, kati ya 8 na 15 ni ndogo 8, na hivyo sisi Insert kwamba

35
00:02:05,440 --> 00:02:09,240
kama kipengele pili ya orodha yetu ya Iliyopangwa.

36
00:02:09,240 --> 00:02:12,180
Tunaweza kuendelea kulinganisha mambo ya kwanza ya orodha zote mbili

37
00:02:12,180 --> 00:02:14,420
na kuondoa ndogo ya 2.

38
00:02:14,420 --> 00:02:19,460
Kulinganisha 15 na 23, 15 ni ndogo na hivyo kuwa wa tatu kipengele yetu.

39
00:02:21,000 --> 00:02:23,910
Sasa kulinganisha 16 na 23, 16 ni ndogo.

40
00:02:23,910 --> 00:02:26,820
Basi hiyo ni kipengele cha nne.

41
00:02:26,820 --> 00:02:30,390
>> Ona kwamba vipengele 2 alikuja kutoka orodha hiyo katika mstari.

42
00:02:30,390 --> 00:02:34,400
Hii ni kwa nini orodha enheten hawezi tu mbadala vipengele kutoka orodha 2.

43
00:02:34,400 --> 00:02:40,020
Kulinganisha 50 na 23, 23 ni ndogo, hivyo sisi kuchagua kwamba.

44
00:02:40,770 --> 00:02:44,070
Kati ya 50 na 42, 42 ni ndogo.

45
00:02:44,070 --> 00:02:48,290
Kati ya 50 na 108, 50 ni ndogo.

46
00:02:48,290 --> 00:02:52,330
Na, hatimaye, sisi tu 108, hivyo ni lazima kwenda juu ya mwisho wa orodha yetu.

47
00:02:53,750 --> 00:02:56,180
Taarifa kwamba tuna nice, Iliyopangwa orodha.

48
00:02:56,180 --> 00:02:59,040
Kila wakati sisi ikilinganishwa kwanza vipengele 2 ya orodha 2

49
00:02:59,040 --> 00:03:02,730
tulikuwa na uwezo wa kuamua kipengele kingine cha orodha enheten.

50
00:03:02,730 --> 00:03:08,070
Hii ina maana kwamba kama orodha ya mwisho ina idadi n, ambapo n hapa ni 8,

51
00:03:08,070 --> 00:03:12,610
basi tunahitaji katika kulinganisha zaidi n kupata yote ya wale idadi ndani ya mahali pa haki.

52
00:03:13,230 --> 00:03:16,230
Algorithm vile ni alisema kukimbia katika wakati linear,

53
00:03:16,230 --> 00:03:18,090
lakini usijali kuhusu kwamba hapa.

54
00:03:18,570 --> 00:03:22,810
>> Kutumia kompyuta yetu kwa kuunganisha, tunaweza kufanya haraka kuunganisha aina algorithm.

55
00:03:22,810 --> 00:03:25,170
Hivyo, hebu upya orodha yetu.

56
00:03:35,210 --> 00:03:37,750
Kuna hatua kubwa 2 katika mchakato wa aina kuunganisha.

57
00:03:37,750 --> 00:03:41,500
Kwanza, kuendelea kupasuliwa orodha ya vikombe katika halves

58
00:03:41,500 --> 00:03:44,860
mpaka sisi kuwa na rundo la orodha na kikombe 1 tu katika wao.

59
00:03:44,860 --> 00:03:47,350
Usijali kama orodha ina idadi isiyo ya kawaida

60
00:03:47,350 --> 00:03:49,880
na huwezi kufanya kukatwa kikamilifu safi kati yao.

61
00:03:49,880 --> 00:03:53,750
Tu kiholela pick ambayo kwa pamoja orodha kikombe ziada in

62
00:03:53,750 --> 00:03:56,240
Hivyo, hebu kupasuliwa orodha hizi.

63
00:03:58,140 --> 00:04:01,310
Sasa tuna orodha 2.

64
00:04:04,120 --> 00:04:06,570
Sasa tuna orodha 4.

65
00:04:10,350 --> 00:04:13,870
>> Na sasa tuna orodha 8 na kikombe moja katika orodha ya kila.

66
00:04:13,870 --> 00:04:16,630
Basi hiyo ni kwa ajili ya hatua 1.

67
00:04:16,630 --> 00:04:22,230
Kwa hatua ya 2, sisi kurudia kuunganisha jozi ya orodha ya wagombea kutumia algorithm kuunganisha tulijifunza kabla.

68
00:04:22,230 --> 00:04:29,160
Kuunganisha 108 na 15, sisi kuishia na orodha 15, 108.

69
00:04:30,330 --> 00:04:36,250
Kuunganisha 50 na 4, sisi kuishia na 4, 50.

70
00:04:36,960 --> 00:04:41,400
Kuunganisha 8 na 42, sisi kuishia na 8, 42.

71
00:04:42,790 --> 00:04:48,130
Na kuunganisha 23 na 16, sisi kuishia na 16, 23.

72
00:04:49,740 --> 00:04:52,450
Sasa wetu orodha zote ni ya kawaida 2.

73
00:04:53,020 --> 00:04:56,180
Ona kwamba kila moja ya orodha 4 ni Iliyopangwa.

74
00:04:56,180 --> 00:04:59,160
>> Hivyo tunaweza kuanza kuunganisha jozi ya orodha tena.

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

76
00:05:03,240 --> 00:05:11,170
kwanza kuchukua 4, kisha 15, kisha 50, kisha 108.

77
00:05:11,170 --> 00:05:15,120
Kuunganisha 8, 42 na 16, 23,

78
00:05:15,120 --> 00:05:22,440
sisi kwanza kuchukua 8, kisha 16, kisha 23, kisha 42.

79
00:05:22,440 --> 00:05:27,370
Hivyo basi, tuna tu 2 orodha ya ukubwa 4, ya kila ambayo ni Iliyopangwa.

80
00:05:27,370 --> 00:05:30,980
Hivyo sasa sisi kuunganisha orodha hizi 2.

81
00:05:30,980 --> 00:05:33,440
Kwanza sisi kuchukua 4.

82
00:05:33,440 --> 00:05:36,580
Kisha sisi kuchukua 8.

83
00:05:36,580 --> 00:05:50,700
Kisha sisi kuchukua 15 na 16, kisha 23, kisha 42, kisha 50, kisha 108.

84
00:05:50,700 --> 00:05:52,220
Na sisi ni kosa.

85
00:05:52,220 --> 00:05:54,900
Sisi sasa kuwa na orodha Iliyopangwa.

86
00:05:54,900 --> 00:05:57,890
Hivyo jinsi ya kufunga ilikuwa hii, hasa?

87
00:05:57,890 --> 00:06:02,000
Katika suala kiufundi, kuunganisha aina ni O (n logi n),

88
00:06:02,000 --> 00:06:07,380
ambapo wote wa Bubble aina, aina insertion, na aina ya uteuzi ni O (n ²).

89
00:06:07,380 --> 00:06:11,120
Kwa kweli, kama wewe utakuwa kujifunza haraka, huwezi kuwa na uwezo wa kuja na aina

90
00:06:11,120 --> 00:06:14,820
ambayo hufanya bora kuliko O (n logi n) katika kesi ujumla.

91
00:06:14,820 --> 00:06:19,120
Tena, msiwe na wasiwasi juu ya nukuu hii kubwa O kama hawajaona bado.

92
00:06:19,120 --> 00:06:23,490
>> Tu kujua kwamba hii ina maana kama sisi alitaka aina orodha kubwa kweli kweli

93
00:06:23,490 --> 00:06:26,820
Bubble aina, aina insertion, na uteuzi aina inaweza uwezekano kuchukua

94
00:06:26,820 --> 00:06:29,500
kikubwa zaidi ya kuunganisha aina.

95
00:06:29,500 --> 00:06:33,210
Haina maana kwamba kuunganisha aina itakuwa kasi kwa wote orodha

96
00:06:33,210 --> 00:06:36,220
au hata kwa orodha yoyote moja chini ya ukubwa fulani.

97
00:06:36,220 --> 00:06:41,950
Kwa mfano, insertion aina inaweza kuwa aina ya haraka sana kwa orodha zote ndogo kuliko vipengele 5.

98
00:06:41,950 --> 00:06:47,360
Katika mazoezi, kuunganisha aina ni kawaida kwa kasi kwa orodha ndogo kama vipengele 50.

99
00:06:47,360 --> 00:06:51,120
>> Lakini hii kasi ya ziada haina kuja bila gharama.

100
00:06:51,120 --> 00:06:54,770
Tofauti na aina yetu nyingine, ambayo kuchukua orodha na kurekebisha orodha katika mahali

101
00:06:54,770 --> 00:06:58,740
mpaka sisi kupata orodha Iliyopangwa, kuunganisha aina ya mahitaji ya baadhi nafasi ya ziada

102
00:06:58,740 --> 00:07:00,900
kuunganisha orodha 2 pamoja.

103
00:07:00,900 --> 00:07:04,690
Hatuwezi mara moja kutumia orodha hiyo ni kuwa zimeunganishwa kuhifadhi orodha enheten

104
00:07:04,690 --> 00:07:08,880
tangu tupate override mambo ambayo bado wanahitaji zitachanganywa.

105
00:07:08,880 --> 00:07:13,540
Nafasi hii ni kidogo ya bei, lakini ni kawaida ni si unreasonable.

106
00:07:13,540 --> 00:07:15,330
Na hiyo ni kwa ajili ya aina kuunganisha.

107
00:07:15,330 --> 00:07:18,490
>> Jina langu ni Rob Bowden, na hii ni CS50.

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

109
00:07:20,500 --> 00:07:24,000
- Na uteuzi aina.

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

111
00:07:25,880 --> 00:07:31,480
Oh, got kuchukua nje pia kwa sababu mimi nilikuwa switched jinsi kuwasilisha.

112
00:07:31,480 --> 00:07:35,680
Orodha ya upande wa kushoto. Hiyo ilikuwa kosa.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] Mimi Star up -

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

115
00:07:41,190 --> 00:07:44,190
Mimi sijui nini -