1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Kwa hiyo katika CS50 sisi kujifunza kuhusu
aina ya kuchagua na kutafuta

3
00:00:08,900 --> 00:00:09,442
algorithms.

4
00:00:09,442 --> 00:00:11,400
Na wakati mwingine inaweza kuwa
gumu kidogo kuweka

5
00:00:11,400 --> 00:00:14,161
wimbo wa nini algorithm anafanya nini.

6
00:00:14,161 --> 00:00:15,910
Tumekuwa kweli tu
skimmed uso mno,

7
00:00:15,910 --> 00:00:18,740
kuna watu wengi kutafuta wengine
na kuchagua algorithms.

8
00:00:18,740 --> 00:00:21,780
Hivyo katika video hii hebu
tu kuchukua dakika chache

9
00:00:21,780 --> 00:00:24,980
kujaribu na distill kila algorithm
chini ya mambo yake ya msingi

10
00:00:24,980 --> 00:00:27,810
hivyo unaweza kukumbuka zaidi
taarifa muhimu kuhusu wao

11
00:00:27,810 --> 00:00:31,970
na kuwa na uwezo wa kueleza
tofauti, kama ni lazima.

12
00:00:31,970 --> 00:00:34,220
>> Kwanza ni uteuzi aina.

13
00:00:34,220 --> 00:00:38,210
Wazo msingi nyuma ya uteuzi aina
ni kupata ndogo zisizochambuliwa kipengele

14
00:00:38,210 --> 00:00:42,890
katika safu na wabadilishane kwa
kwanza zisizochambuliwa kipengele cha safu hiyo.

15
00:00:42,890 --> 00:00:46,620
Sisi alisema kuwa mbaya zaidi kesi
kukimbia wakati wa kwamba alikuwa n squared.

16
00:00:46,620 --> 00:00:50,060
Na kama unataka kukumbuka nini, kuchukua
a tuangalie uteuzi aina za video.

17
00:00:50,060 --> 00:00:54,560
Bora kesi kukimbia wakati
Pia n squared.

18
00:00:54,560 --> 00:00:58,910
>> Bubble aina, Dhana ya kwamba
moja ni wabadilishane jozi karibu.

19
00:00:58,910 --> 00:01:01,730
Hivyo hiyo ni muhimu kwamba husaidia
kumbuka tofauti hapa.

20
00:01:01,730 --> 00:01:04,920
Uteuzi aina ni, hadi sasa,
kupata Bubble smallest--

21
00:01:04,920 --> 00:01:06,790
aina ni wabadilishane jozi karibu.

22
00:01:06,790 --> 00:01:08,710
Sisi wabadilishane jozi karibu
ya mambo kama

23
00:01:08,710 --> 00:01:12,530
ni nje ya utaratibu, ambayo kwa ufanisi
Bubbles mambo makubwa na haki,

24
00:01:12,530 --> 00:01:17,060
na wakati huo huo pia huanza
hoja mambo madogo upande wa kushoto.

25
00:01:17,060 --> 00:01:20,180
Mbaya zaidi kesi kesi kukimbia wakati
ya Bubble aina ni n squared.

26
00:01:20,180 --> 00:01:23,476
Bora kesi kukimbia wakati
ya Bubble aina ni n.

27
00:01:23,476 --> 00:01:25,350
Kwa sababu katika hali hiyo
hatuna actually--

28
00:01:25,350 --> 00:01:27,141
tupate haja ya
kufanya swaps yoyote wakati wote.

29
00:01:27,141 --> 00:01:31,026
Sisi tu kuwa na kufanya moja
kupita katika mambo yote n.

30
00:01:31,026 --> 00:01:34,600
>> Katika kuingizwa aina,
wazo la msingi hapa ni shifting.

31
00:01:34,600 --> 00:01:36,630
Hiyo ni neno la kwa kuingizwa aina.

32
00:01:36,630 --> 00:01:39,630
Tunakwenda hatua mara moja kupitia
safu kutoka kushoto kwenda kulia.

33
00:01:39,630 --> 00:01:41,670
Na kama sisi, tuko
kwenda kuhama mambo

34
00:01:41,670 --> 00:01:46,260
tumekuwa tayari kuona na kufanya nafasi ya
ndogo wale wanaohitaji na kifafa mahali fulani

35
00:01:46,260 --> 00:01:48,080
nyuma katika kuwa sehemu yamepangwa.

36
00:01:48,080 --> 00:01:51,600
Hivyo sisi kujenga safu Iliyopangwa moja
kipengele wakati huo, kushoto na kulia,

37
00:01:51,600 --> 00:01:54,740
na sisi kuhama mambo ya kufanya chumba.

38
00:01:54,740 --> 00:01:58,650
Mbaya zaidi kesi kukimbia wakati wa
kuingizwa aina ni n squared.

39
00:01:58,650 --> 00:02:02,380
Bora kesi kukimbia wakati ni n.

40
00:02:02,380 --> 00:02:05,380
>> Kuunganisha sort-- keyword
hapa ni kupasuliwa na kuunganisha.

41
00:02:05,380 --> 00:02:08,949
Sisi mgawanyiko safu kamili, iwe
ni mambo sita, mambo nane,

42
00:02:08,949 --> 00:02:13,790
10,000 elements-- sisi kupasuliwa
chini kwa nusu, kwa nusu, kwa nusu,

43
00:02:13,790 --> 00:02:17,720
mpaka tuna chini ya safu
ya n moja kipengele arrays.

44
00:02:17,720 --> 00:02:19,470
Seti ya n moja kipengele arrays.

45
00:02:19,470 --> 00:02:22,640
Hivyo sisi ilianza na moja
1,000 kipengele safu,

46
00:02:22,640 --> 00:02:26,550
na sisi kupata kwa uhakika ambapo sisi
na 1,000 mmoja kipengele arrays.

47
00:02:26,550 --> 00:02:30,990
Kisha tunaanza kuunganisha arrays wale ndogo
nyuma pamoja katika mpangilio sahihi.

48
00:02:30,990 --> 00:02:34,860
Kwa hiyo sisi kuchukua mbili arrays mmoja kipengele
na kujenga mbili kipengele safu.

49
00:02:34,860 --> 00:02:38,180
Tunachukua mbili arrays mbili kipengele
na kujenga nne kipengele safu

50
00:02:38,180 --> 00:02:43,900
na kadhalika na kadhalika mpaka tumekuwa
tena upya moja n kipengele safu.

51
00:02:43,900 --> 00:02:48,410
>> Mbaya zaidi kesi kukimbia wakati wa
kuunganisha aina ipo n mara logi n.

52
00:02:48,410 --> 00:02:52,390
Tuna mambo n, lakini
mchakato huu recombining

53
00:02:52,390 --> 00:02:56,960
inachukua logi n hatua ya kupata
nyuma kwa safu kamili.

54
00:02:56,960 --> 00:03:01,160
Kesi bora kukimbia wakati ni pia n gogo
n kwa sababu mchakato huu haina kweli

55
00:03:01,160 --> 00:03:04,090
huduma kama safu alikuwa
yamepangwa au si kuanza na.

56
00:03:04,090 --> 00:03:07,590
Mchakato ni sawa, kuna
hakuna njia ya mambo mzunguko mfupi.

57
00:03:07,590 --> 00:03:11,610
Hivyo n logi n katika hali mbaya zaidi,
n logi n katika kesi bora.

58
00:03:11,610 --> 00:03:13,960
>> Kuongelea mbili
kutafuta algorithms.

59
00:03:13,960 --> 00:03:16,230
Hivyo tafuta linear ni kuhusu iterating.

60
00:03:16,230 --> 00:03:19,500
Sisi kuendelea katika safu
mara moja, kutoka kushoto kwenda kulia,

61
00:03:19,500 --> 00:03:21,950
kujaribu kupata idadi
kwamba sisi ni kuangalia kwa.

62
00:03:21,950 --> 00:03:24,550
Wakati mbaya zaidi kesi kukimbia ni O kubwa ya n.

63
00:03:24,550 --> 00:03:27,610
Inaweza kuchukua sisi iterating
hela kila kipengele moja

64
00:03:27,610 --> 00:03:30,660
kupata kipengele sisi ni kuangalia
kwa maana, ama katika nafasi ya mwisho,

65
00:03:30,660 --> 00:03:31,630
au si wakati wote.

66
00:03:31,630 --> 00:03:34,720
Lakini hatuwezi kuthibitisha kwamba mpaka
tumekuwa inaonekana katika kila kitu.

67
00:03:34,720 --> 00:03:36,730
m bora kesi, tunaona mara moja.

68
00:03:36,730 --> 00:03:41,060
Bora kesi kukimbia wakati wa
tafuta linear ni omega ya 1.

69
00:03:41,060 --> 00:03:43,689
>> Mwisho, kulikuwa na tafuta binary,
ambayo inahitaji safu mbalimbali.

70
00:03:43,689 --> 00:03:45,605
Kumbuka kwamba sana
muhimu kuzingatia

71
00:03:45,605 --> 00:03:47,155
wakati wa kufanya kazi na utafutaji mapacha.

72
00:03:47,155 --> 00:03:50,180
Ni sharti la kutumia it--
safu kwamba wewe ni kutafuta njia ya

73
00:03:50,180 --> 00:03:52,160
Lazima kutatuliwa.

74
00:03:52,160 --> 00:03:54,500
Vinginevyo, keyword
ni mgawanyiko na kushinda.

75
00:03:54,500 --> 00:03:58,310
Kupasuliwa safu katika nusu na
kuondoa nusu ya mambo

76
00:03:58,310 --> 00:04:00,780
kila wakati kama wewe kuendelea kwa njia ya.

77
00:04:00,780 --> 00:04:04,330
Kwa sababu ya mgawanyiko huu na kushinda
na kugawanyika mambo katika njia nusu,

78
00:04:04,330 --> 00:04:07,450
mbaya zaidi kesi kukimbia wakati
ya kutafuta binary ni

79
00:04:07,450 --> 00:04:11,730
kuingia n, ambayo ni kikubwa
bora kuliko search ya linear n.

80
00:04:11,730 --> 00:04:13,570
Bora kesi kukimbia wakati bado ni moja.

81
00:04:13,570 --> 00:04:17,010
>> Tunaweza kukuta ni mara moja
mara ya kwanza sisi kufanya mgawanyiko, lakini,

82
00:04:17,010 --> 00:04:19,339
tena, kumbuka kwamba
ingawa search binary ni

83
00:04:19,339 --> 00:04:24,030
kikubwa bora kuliko tafuta linear
kwa nguvu ya kuwa logi n dhidi n,

84
00:04:24,030 --> 00:04:27,110
unaweza kuwa na kwenda kwa njia ya kazi
ya kuchagua safu yako ya kwanza, ambayo

85
00:04:27,110 --> 00:04:32,010
inaweza kufanya hivyo kutokuwa na ufanisi kulingana
na ukubwa wa iterating yamepangwa.

86
00:04:32,010 --> 00:04:35,250
>> Mimi nina Doug Lloyd, hii ni CS50.

87
00:04:35,250 --> 00:04:36,757