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

2
00:00:05,760 --> 00:00:08,900
>> DOUG Lloyd: Niin CS50 me opimme
erilaisia ​​lajittelu ja etsiminen

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

4
00:00:09,442 --> 00:00:11,400
Ja joskus se voi olla
hieman hankala pitää

5
00:00:11,400 --> 00:00:14,161
kirjaa mitä algoritmin tekee mitä.

6
00:00:14,161 --> 00:00:15,910
Olemme oikeastaan ​​vain
rasvaton pinta liian,

7
00:00:15,910 --> 00:00:18,740
on olemassa monia muita etsimistä
ja lajittelualgoritmeja.

8
00:00:18,740 --> 00:00:21,780
Joten tässä video nyt
vain kestää muutaman minuutin

9
00:00:21,780 --> 00:00:24,980
yrittää polttaa kukin algoritmi
alas sen keskeiset osatekijät

10
00:00:24,980 --> 00:00:27,810
joten voit muistaa eniten
tärkeää tietoa niistä

11
00:00:27,810 --> 00:00:31,970
ja pystyä ilmaisemaan
erot, jos on tarpeen.

12
00:00:31,970 --> 00:00:34,220
>> Ensimmäinen on valinta lajitella.

13
00:00:34,220 --> 00:00:38,210
Perusajatuksena valinta lajitella
on löytää pienin lajittelemattomat elementti

14
00:00:38,210 --> 00:00:42,890
array ja vaihtaa sen kanssa
ensimmäinen lajittelematon osa tätä array.

15
00:00:42,890 --> 00:00:46,620
Sanoimme, että pahin
ajoaika, joka oli n potenssiin.

16
00:00:46,620 --> 00:00:50,060
Ja jos haluat muistaa miksi, ota
katso valinta lajitella video.

17
00:00:50,060 --> 00:00:54,560
Parhaassa tapauksessa ajoaika
on myös n potenssiin.

18
00:00:54,560 --> 00:00:58,910
>> Kuplalajittelu, ajatuksena että
yksi on vaihtaa vieressä paria.

19
00:00:58,910 --> 00:01:01,730
Niin se on avain, jonka avulla voit
muistaa ero täällä.

20
00:01:01,730 --> 00:01:04,920
Valinta lajitella on, toistaiseksi,
löytää smallest-- kupla

21
00:01:04,920 --> 00:01:06,790
SORT vaihtaa vieressä paria.

22
00:01:06,790 --> 00:01:08,710
Me vaihtaa vieressä paria
elementtien jos he

23
00:01:08,710 --> 00:01:12,530
ovat epäkunnossa, joka tehokkaasti
kuplia suurempi elementit oikealle,

24
00:01:12,530 --> 00:01:17,060
ja samalla se myös alkaa
siirtyä pienempiä osia vasemmalle.

25
00:01:17,060 --> 00:01:20,180
Pahin tapaus ajoaika
kupla lajitella on n potenssiin.

26
00:01:20,180 --> 00:01:23,476
Parhaassa tapauksessa ajoaika
kupla lajitella on n.

27
00:01:23,476 --> 00:01:25,350
Koska tässä tilanteessa
emme actually--

28
00:01:25,350 --> 00:01:27,141
emme ehkä tarvitse
tehdä swap ollenkaan.

29
00:01:27,141 --> 00:01:31,026
Meillä on vain tehdä yhden
siirtää kaikilla n elementtiä.

30
00:01:31,026 --> 00:01:34,600
>> Vuonna lisäyslajittelun,
Perusajatuksena tässä on siirtymässä.

31
00:01:34,600 --> 00:01:36,630
Se avainsanan lisäyslajittelun.

32
00:01:36,630 --> 00:01:39,630
Aiomme vaiheeseen kerran kautta
array vasemmalta oikealle.

33
00:01:39,630 --> 00:01:41,670
Ja kuten teemme, olemme
menossa siirtää elementtejä

34
00:01:41,670 --> 00:01:46,260
olemme jo nähneet tehdä tilaa
pienempiä, jotka täytyy sovittaa jonnekin

35
00:01:46,260 --> 00:01:48,080
takaisin että lajiteltu osaan.

36
00:01:48,080 --> 00:01:51,600
Joten me rakennamme lajitellut array yksi
elementti kerrallaan, vasemmalta oikealle,

37
00:01:51,600 --> 00:01:54,740
ja siirrämme asioita tehdä tilaa.

38
00:01:54,740 --> 00:01:58,650
Pahimman tapauksen ajoaika
lisäyslajittelun on n potenssiin.

39
00:01:58,650 --> 00:02:02,380
Paras-tapaus ajoaika on n.

40
00:02:02,380 --> 00:02:05,380
>> Yhdistä sort-- avainsanan
täällä on jakaa ja yhdistää.

41
00:02:05,380 --> 00:02:08,949
Jaamme täyden valikoiman, onko
se on kuusi elementtejä, kahdeksan elementtejä,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- me jakaa sen
laskenut puoleen, puoleen, puoleen,

43
00:02:13,790 --> 00:02:17,720
kunnes meillä on alle array
n yksi elementti taulukot.

44
00:02:17,720 --> 00:02:19,470
Joukko n yksi elementti taulukot.

45
00:02:19,470 --> 00:02:22,640
Joten aloitimme yksi
1000-elementti array,

46
00:02:22,640 --> 00:02:26,550
ja saamme siihen pisteeseen, jossa meillä
on 1000 yksi-elementti paneelit.

47
00:02:26,550 --> 00:02:30,990
Sitten alamme yhdistää niillä osa paneelit
takaisin yhteen oikeassa järjestyksessä.

48
00:02:30,990 --> 00:02:34,860
Joten otamme kaksi yhden elementin paneelit
ja luoda kaksi-elementti array.

49
00:02:34,860 --> 00:02:38,180
Otamme kaksi kahden alkion taulukot
ja luoda neljän alkiotaulukon

50
00:02:38,180 --> 00:02:43,900
ja niin edelleen ja niin edelleen, kunnes olemme
taas uudelleen yksi n alkiotaulukko.

51
00:02:43,900 --> 00:02:48,410
>> Pahimman tapauksen ajoaika
yhdistää lajitella on n kertaa log n.

52
00:02:48,410 --> 00:02:52,390
Meillä on n alkiota, mutta
tämä rekombinaatiovälineen prosessi

53
00:02:52,390 --> 00:02:56,960
panee log n askelta päästä
Takaisin täyden valikoiman.

54
00:02:56,960 --> 00:03:01,160
Parhaassa tapauksessa ajoaika on myös n loki
n koska tämä prosessi ei oikeastaan

55
00:03:01,160 --> 00:03:04,090
piittaa siitä array oli
lajiteltu tai ei aloittaa.

56
00:03:04,090 --> 00:03:07,590
Prosessi on sama, on olemassa
mitenkään oikosulku asioita.

57
00:03:07,590 --> 00:03:11,610
Joten n log n pahimmassa tapauksessa,
n log n parhaassa tapauksessa.

58
00:03:11,610 --> 00:03:13,960
>> Puhuimme kaksi
hakuja algoritmeja.

59
00:03:13,960 --> 00:03:16,230
Joten lineaarinen haku on noin iteroimalla.

60
00:03:16,230 --> 00:03:19,500
Etenemme koko joukko
kerran, vasemmalta oikealle,

61
00:03:19,500 --> 00:03:21,950
yrittää löytää numero
että etsimme.

62
00:03:21,950 --> 00:03:24,550
Pahimman tapauksen ajoaika on iso O n.

63
00:03:24,550 --> 00:03:27,610
Se voi viedä meidät iteroimalla
poikki jokainen elementti

64
00:03:27,610 --> 00:03:30,660
löytää elementti etsimme
varten, joko viimeisessä asennossa,

65
00:03:30,660 --> 00:03:31,630
tai ei lainkaan.

66
00:03:31,630 --> 00:03:34,720
Mutta emme voi vahvistaa, että ennen
teimme kaiken.

67
00:03:34,720 --> 00:03:36,730
m parhaassa tapauksessa, löydämme heti.

68
00:03:36,730 --> 00:03:41,060
Paras-tapaus ajoaika
lineaarinen haku on omega 1.

69
00:03:41,060 --> 00:03:43,689
>> Lopuksi nousi binäärihaku,
joka vaatii valikoituja array.

70
00:03:43,689 --> 00:03:45,605
Muista, että on hyvin
tärkeä näkökohta

71
00:03:45,605 --> 00:03:47,155
kun työskentelet binäärihakupuu.

72
00:03:47,155 --> 00:03:50,180
Se on edellytys käyttäen it--
array että etsit kautta

73
00:03:50,180 --> 00:03:52,160
pitää lajitella.

74
00:03:52,160 --> 00:03:54,500
Muuten avainsana
on hajota ja hallitse.

75
00:03:54,500 --> 00:03:58,310
Jakaa array osaksi puoli ja
poistaa puolet elementit

76
00:03:58,310 --> 00:04:00,780
joka kerta kun jatkat kautta.

77
00:04:00,780 --> 00:04:04,330
Tämän vuoksi hajoita ja hallitse
ja halkaisu asioita puoli lähestymistapa,

78
00:04:04,330 --> 00:04:07,450
pahimman tapauksen ajoaika
binary haku on

79
00:04:07,450 --> 00:04:11,730
log n, joka on olennaisesti
parempi kuin lineaarinen haku n n.

80
00:04:11,730 --> 00:04:13,570
Paras-tapaus ajoaika on edelleen yksi.

81
00:04:13,570 --> 00:04:17,010
>> Voisimme löytää sen heti
Ensimmäistä kertaa teemme jako, mutta,

82
00:04:17,010 --> 00:04:19,339
jälleen, muista, että
vaikka binary haku on

83
00:04:19,339 --> 00:04:24,030
huomattavasti parempi kuin lineaarinen haku
sen perusteella, että log n vs. n,

84
00:04:24,030 --> 00:04:27,110
saatat joutua käydä läpi työn
lajittelu matriisisi ensimmäinen, joka

85
00:04:27,110 --> 00:04:32,010
voisi tehdä sen vähemmän tehokas riippuen
koosta iteroimalla lajiteltu.

86
00:04:32,010 --> 00:04:35,250
>> Olen Doug Lloyd, tämä on CS50.

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