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

2
00:00:05,760 --> 00:00:08,900
>> Doug LLOYD: Tako je u CS50 smo naučili o
razne sortiranje i pretraživanje

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

4
00:00:09,442 --> 00:00:11,400
A ponekad to može biti
malo lukav da bi

5
00:00:11,400 --> 00:00:14,161
pratiti što algoritam što radi.

6
00:00:14,161 --> 00:00:15,910
Mi smo zapravo samo
obrano površinu previše,

7
00:00:15,910 --> 00:00:18,740
postoje mnoge druge pretraživanje
i sortiranje algoritama.

8
00:00:18,740 --> 00:00:21,780
Tako je u ovom videu ćemo
samo uzeti nekoliko minuta

9
00:00:21,780 --> 00:00:24,980
pokušati destilirati svaki algoritam
do njezinih temeljnih elemenata

10
00:00:24,980 --> 00:00:27,810
tako da možete se sjetiti najviše
važne informacije o njima

11
00:00:27,810 --> 00:00:31,970
i biti u stanju artikulirati
razlike, ako je potrebno.

12
00:00:31,970 --> 00:00:34,220
>> Prvi je izbor vrsta.

13
00:00:34,220 --> 00:00:38,210
Osnovna ideja za odabir vrste
se naći najmanji nesortiranog elementa

14
00:00:38,210 --> 00:00:42,890
u niz i zamijeniti s
Prvi Nesortirano element tog polja.

15
00:00:42,890 --> 00:00:46,620
Rekli smo da je najgori slučaj
pokrenuti vrijeme da n je kvadrat.

16
00:00:46,620 --> 00:00:50,060
A ako želite podsjetiti zašto je, potrajati
Pogled na izbor sortiranja video.

17
00:00:50,060 --> 00:00:54,560
Najbolji slučaja pokrenuti vrijeme
također je n kvadrat.

18
00:00:54,560 --> 00:00:58,910
>> Mjehurić vrsta, ideja da
jedna za swap susjedna parova.

19
00:00:58,910 --> 00:01:01,730
Dakle, to je ključ koji vam pomaže
zapamtite razliku ovdje.

20
00:01:01,730 --> 00:01:04,920
Izbor vrste je, do sada,
naći smallest-- mjehurić

21
00:01:04,920 --> 00:01:06,790
sorta je swap susjedna parova.

22
00:01:06,790 --> 00:01:08,710
Mi swap susjedna para
elemenata ako su

23
00:01:08,710 --> 00:01:12,530
izvan reda, koji učinkovito
mjehurići većih elemenata desno,

24
00:01:12,530 --> 00:01:17,060
a ujedno je i počinje
premjestiti manje elemenata na lijevo.

25
00:01:17,060 --> 00:01:20,180
Najgorem slučaju slučaja pokrenuti vrijeme
od mjehurića vrste n na kvadrat.

26
00:01:20,180 --> 00:01:23,476
Najbolji slučaja pokrenuti vrijeme
Bubble sort n.

27
00:01:23,476 --> 00:01:25,350
Jer u toj situaciji
ne actually--

28
00:01:25,350 --> 00:01:27,141
nismo mogli trebati
napraviti nikakve zamjene na sve.

29
00:01:27,141 --> 00:01:31,026
Imamo samo napraviti jedan
proći kroz sve n elemenata.

30
00:01:31,026 --> 00:01:34,600
>> U unosa vrste,
Osnovna ideja je ovdje prebacuje.

31
00:01:34,600 --> 00:01:36,630
To je ključna za umetanje vrste.

32
00:01:36,630 --> 00:01:39,630
Idemo korak po jednom
Niz od lijeva na desno.

33
00:01:39,630 --> 00:01:41,670
I kao što nam je činiti, mi smo
će pomak elemenata

34
00:01:41,670 --> 00:01:46,260
već smo vidjeli kako bi napravili mjesta za
manjih koje je potrebno da stane negdje

35
00:01:46,260 --> 00:01:48,080
natrag u tom sortirani dijelu.

36
00:01:48,080 --> 00:01:51,600
Tako smo izgraditi sortirani niz jedan
Element na vrijeme, s lijeva na desno,

37
00:01:51,600 --> 00:01:54,740
a mi pomak stvari kako bi napravili mjesta.

38
00:01:54,740 --> 00:01:58,650
Najgorem slučaju izvođenja vrijeme
umetanje vrsta n na kvadrat.

39
00:01:58,650 --> 00:02:02,380
Najbolji slučaja pokrenuti vrijeme nje.

40
00:02:02,380 --> 00:02:05,380
>> Spoji sort-- ključnu riječ
Ovdje je podijeljen i spajanje.

41
00:02:05,380 --> 00:02:08,949
Podijeliti smo cijeli niz, bilo
to je šest elemenata, osam elemenata,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- smo ga podijeliti
dolje po pola, pola, pola,

43
00:02:13,790 --> 00:02:17,720
dok smo pod nizom
n jedan element polja.

44
00:02:17,720 --> 00:02:19,470
Skup je n jedan element polja.

45
00:02:19,470 --> 00:02:22,640
Tako smo počeli s jednim
1000-element matrice,

46
00:02:22,640 --> 00:02:26,550
i mi doći do točke gdje smo
ima 1.000 jedna elementa polja.

47
00:02:26,550 --> 00:02:30,990
Onda smo počeli spojiti one pod polja
natrag zajedno u ispravnom redoslijedu.

48
00:02:30,990 --> 00:02:34,860
Tako smo se dva jedan-elementa polja
i stvoriti dva elementa niza.

49
00:02:34,860 --> 00:02:38,180
Vodimo dva dva elementa polja
i stvoriti četiri elementa niz

50
00:02:38,180 --> 00:02:43,900
i tako dalje i tako dalje dok imamo
opet obnovili jednu n element matrice.

51
00:02:43,900 --> 00:02:48,410
>> Najgorem slučaju izvođenja vrijeme
spojiti vrsta je N puta prijavite nje.

52
00:02:48,410 --> 00:02:52,390
Imamo n elemenata, ali
ovaj proces ponovnog spajanja

53
00:02:52,390 --> 00:02:56,960
traje prijavite n koraka kako bi dobili
natrag na punu lepezu.

54
00:02:56,960 --> 00:03:01,160
Najbolji slučaj pokrenuti vrijeme je n dnevnik
nje, jer se taj proces ne stvarno

55
00:03:01,160 --> 00:03:04,090
briga je li niz je
razvrstani ili ne početi s.

56
00:03:04,090 --> 00:03:07,590
Postupak je isti, nema
ni na koji način kratkog spoja stvari.

57
00:03:07,590 --> 00:03:11,610
Tako je n log n u najgorem slučaju,
n log n u najboljem slučaju.

58
00:03:11,610 --> 00:03:13,960
>> Razgovarali smo o dvije
traži algoritama.

59
00:03:13,960 --> 00:03:16,230
Dakle, linearno pretraživanje je oko Ponavljanje.

60
00:03:16,230 --> 00:03:19,500
Nastavljamo preko polja
jednom, s lijeva na desno,

61
00:03:19,500 --> 00:03:21,950
pokušava pronaći broj
da tražimo.

62
00:03:21,950 --> 00:03:24,550
Najgorem slučaju pokrenuti vrijeme je veliki O n.

63
00:03:24,550 --> 00:03:27,610
To bi moglo potrajati iterating nas
preko svakog pojedinog elementa

64
00:03:27,610 --> 00:03:30,660
pronaći element tražimo
za, bilo u zadnjem položaju,

65
00:03:30,660 --> 00:03:31,630
ili uopće ne.

66
00:03:31,630 --> 00:03:34,720
No, ne možemo potvrditi da je do
smo pogledali sve.

67
00:03:34,720 --> 00:03:36,730
m najbolje slučaj, odmah smo pronašli.

68
00:03:36,730 --> 00:03:41,060
Najbolji slučaja pokrenuti vrijeme
linearno pretraživanje je omega 1.

69
00:03:41,060 --> 00:03:43,689
>> Na kraju, tu je binarno pretraživanje,
što zahtijeva ponekog niz.

70
00:03:43,689 --> 00:03:45,605
Sjetite se da je vrlo
važno razmatranje

71
00:03:45,605 --> 00:03:47,155
kada se radi s binarnim pretraživanja.

72
00:03:47,155 --> 00:03:50,180
To je preduvjet korištenja it--
Niz koji ste u potrazi kroz

73
00:03:50,180 --> 00:03:52,160
moraju biti razvrstani.

74
00:03:52,160 --> 00:03:54,500
Inače, ključna riječ
je podijeli pa vladaj.

75
00:03:54,500 --> 00:03:58,310
Split niz u pola i
eliminirati polovice elemenata

76
00:03:58,310 --> 00:04:00,780
svaki put kao što nastavite putem.

77
00:04:00,780 --> 00:04:04,330
Zbog tog Podijeli pa vladaj
i cijepanje stvari u pola pristupu,

78
00:04:04,330 --> 00:04:07,450
najgorem slučaju izvođenja vrijeme
od binarno pretraživanje je

79
00:04:07,450 --> 00:04:11,730
Prijava N, koji je uglavnom
bolji od linearnog Traži u n.

80
00:04:11,730 --> 00:04:13,570
Najbolji slučaja pokrenuti vrijeme je još uvijek jedan.

81
00:04:13,570 --> 00:04:17,010
>> Možemo ga pronaći odmah
Prvi put smo napraviti podjelu, ali,

82
00:04:17,010 --> 00:04:19,339
opet, ne zaboravite da
Iako je binarno pretraživanje je

83
00:04:19,339 --> 00:04:24,030
znatno bolje nego linearna pretraživanje
samim time što su log n odnosu n,

84
00:04:24,030 --> 00:04:27,110
možda ćete morati proći kroz rad
sortiranje svoj niz prvi, koji

85
00:04:27,110 --> 00:04:32,010
Možda bi ga manje učinkovit, ovisno
o veličini Ponavljanje sortirati.

86
00:04:32,010 --> 00:04:35,250
>> Ja sam Doug Lloyd, ovo je CS50.

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