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

2
00:00:05,760 --> 00:00:08,900
>> Doug LLOYD: Torej, v CS50 smo se naučili o
različne sortiranje in iskanje

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

4
00:00:09,442 --> 00:00:11,400
Včasih je lahko
malo zapleteno, da

5
00:00:11,400 --> 00:00:14,161
Spremljajte kaj algoritem počne kaj.

6
00:00:14,161 --> 00:00:15,910
Smo v resnici le
posneto površino preveč,

7
00:00:15,910 --> 00:00:18,740
Obstaja veliko drugih Iskanje
in algoritmov.

8
00:00:18,740 --> 00:00:21,780
Torej, v tem videu pa si
vzemite nekaj minut

9
00:00:21,780 --> 00:00:24,980
poskusiti in destilirati vsak algoritem
navzdol, da njenih ključnih elementov

10
00:00:24,980 --> 00:00:27,810
tako da se lahko spomnite najbolj
pomembne informacije o njih

11
00:00:27,810 --> 00:00:31,970
in biti sposoben artikulirati
razlike, če je potrebno.

12
00:00:31,970 --> 00:00:34,220
>> Prvi je izbira vrste.

13
00:00:34,220 --> 00:00:38,210
Osnovna ideja za izbor vrste
je najti najmanjšo neurejen element

14
00:00:38,210 --> 00:00:42,890
v niz in ga zamenjali z
prvi neprebrani element te matrike.

15
00:00:42,890 --> 00:00:46,620
Rekli smo, da je najslabši
teči čas, da je n kvadrat.

16
00:00:46,620 --> 00:00:50,060
In če želite, da se spomni, zakaj bi
poglej na izbor sort video.

17
00:00:50,060 --> 00:00:54,560
Čas teče najboljšem primeru
tudi n kvadrat.

18
00:00:54,560 --> 00:00:58,910
>> Bubble razvrščanje, ideja, ki
ena je, da swap sosednjih parov.

19
00:00:58,910 --> 00:01:01,730
Tako, da je ključno, da vam pomaga
spomnite razliko tukaj.

20
00:01:01,730 --> 00:01:04,920
Izbor vrste je, doslej,
najti smallest-- mehurček

21
00:01:04,920 --> 00:01:06,790
razvrščanja je swap sosednjih parov.

22
00:01:06,790 --> 00:01:08,710
Mi swap sosednjih parov
elementov, če jih

23
00:01:08,710 --> 00:01:12,530
so v okvari, ki dejansko
mehurčki večje elemente v desno,

24
00:01:12,530 --> 00:01:17,060
in hkrati pa tudi začne
premakniti manjših elementov v levo.

25
00:01:17,060 --> 00:01:20,180
Najslabši čas v primeru run
mehurčkov vrste je n kvadrat.

26
00:01:20,180 --> 00:01:23,476
Čas teče najboljšem primeru
od balona je nekako n.

27
00:01:23,476 --> 00:01:25,350
Ker je v tej situaciji
ne bomo actually--

28
00:01:25,350 --> 00:01:27,141
ne bomo morda morali
kakršno koli zamenjavo sploh.

29
00:01:27,141 --> 00:01:31,026
Imamo le narediti eno
mimo vseh n elementov.

30
00:01:31,026 --> 00:01:34,600
>> V vstavitve vrste je
Osnovna ideja tu se premikajo.

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

32
00:01:36,630 --> 00:01:39,630
Bomo enkrat korak skozi
array od leve proti desni.

33
00:01:39,630 --> 00:01:41,670
In kot mi, mi smo
tekoč premik elementov

34
00:01:41,670 --> 00:01:46,260
smo že videli, da bi naredili prostor za
manjših, ki jih je nekje fit

35
00:01:46,260 --> 00:01:48,080
nazaj v tej razvrščeni delu.

36
00:01:48,080 --> 00:01:51,600
Tako gradimo urejen paleto ena
element naenkrat, od leve proti desni,

37
00:01:51,600 --> 00:01:54,740
in smo premik stvari, da bi naredili prostor.

38
00:01:54,740 --> 00:01:58,650
Čas najslabšem primeru tek
Vstavitev vrsta je n kvadrat.

39
00:01:58,650 --> 00:02:02,380
Čas najboljšem primeru teči n.

40
00:02:02,380 --> 00:02:05,380
>> Spoji sort-- ključno besedo
tukaj se razdeli in združiti.

41
00:02:05,380 --> 00:02:08,949
Razdelili smo celotno paleto, ali
to je šest elementov, osem elementov,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- smo ga razdelili
navzdol za polovico, za polovico, za polovico,

43
00:02:13,790 --> 00:02:17,720
dokler ne bomo imeli pod paleto
n ene nizi elementov.

44
00:02:17,720 --> 00:02:19,470
Niz n enim nizi elementov.

45
00:02:19,470 --> 00:02:22,640
Tako smo začeli z eno
1000-element matrika,

46
00:02:22,640 --> 00:02:26,550
in smo prišli do točke, kjer smo
imajo 1.000 nizi eno sestavljeno.

47
00:02:26,550 --> 00:02:30,990
Potem smo začeli spajanje teh sub nize
spet skupaj v pravilnem zaporedju.

48
00:02:30,990 --> 00:02:34,860
Tako smo vzeli dva nizi eno sestavljeno
in ustvariti niz dveh elementov.

49
00:02:34,860 --> 00:02:38,180
Peljemo dva nizi dvodelne
in ustvariti niz štiri-element

50
00:02:38,180 --> 00:02:43,900
in tako naprej in tako naprej, dokler smo jih
spet obnovili eno n element array.

51
00:02:43,900 --> 00:02:48,410
>> Čas najslabšem primeru tek
zlivanjem je n krat log n.

52
00:02:48,410 --> 00:02:52,390
Imamo n elementov, vendar
ta proces rekombinacija

53
00:02:52,390 --> 00:02:56,960
traja log n korakih, da bi dobili
nazaj na polno paleto.

54
00:02:56,960 --> 00:03:01,160
Najboljši primer teči čas je tudi n log
n ker je ta proces v resnici ne

55
00:03:01,160 --> 00:03:04,090
skrbi, ali je bil niz
razporejene ali ne, za začetek.

56
00:03:04,090 --> 00:03:07,590
Postopek je enak, tam
noben način kratkega stika stvari.

57
00:03:07,590 --> 00:03:11,610
Torej n log n v najslabšem primeru,
n log n v najboljšem primeru.

58
00:03:11,610 --> 00:03:13,960
>> Pogovarjali smo se o dveh
iskanje algoritmov.

59
00:03:13,960 --> 00:03:16,230
Torej linearno iskanje je približno ponavljanjem.

60
00:03:16,230 --> 00:03:19,500
Bomo nadaljevali čez polja
enkrat, od leve proti desni,

61
00:03:19,500 --> 00:03:21,950
poskuša najti številko
da iščemo.

62
00:03:21,950 --> 00:03:24,550
Najslabši primer teči čas je velik O n.

63
00:03:24,550 --> 00:03:27,610
Morda nas bo ponavljanjem
po vsakem posameznem elementu

64
00:03:27,610 --> 00:03:30,660
poiščite element, ki ga iščemo
za bodisi v zadnjem položaju,

65
00:03:30,660 --> 00:03:31,630
ali pa sploh ne.

66
00:03:31,630 --> 00:03:34,720
Vendar ne moremo potrditi, da dokler
smo pogledal vse.

67
00:03:34,720 --> 00:03:36,730
sem v najboljšem primeru, najdemo takoj.

68
00:03:36,730 --> 00:03:41,060
Čas najboljšem primeru tek
linearna iskanje je omega 1.

69
00:03:41,060 --> 00:03:43,689
>> Nazadnje je bilo binarno iskanje,
ki zahteva urejene paleto.

70
00:03:43,689 --> 00:03:45,605
Ne pozabite, da je zelo
pomemben dejavnik

71
00:03:45,605 --> 00:03:47,155
Pri delu z binarno iskanje.

72
00:03:47,155 --> 00:03:50,180
To je predpogoj za uporabo it--
matrika, ki jo iščete s pomočjo

73
00:03:50,180 --> 00:03:52,160
morajo biti razporejene.

74
00:03:52,160 --> 00:03:54,500
Sicer pa je ključna beseda
je deli in vladaj.

75
00:03:54,500 --> 00:03:58,310
Razdeli niz na pol in
odpravo polovica elementov

76
00:03:58,310 --> 00:04:00,780
vsakič, ko se nadaljuje skozi.

77
00:04:00,780 --> 00:04:04,330
Zaradi tega Deli in vladaj
in delitve stvari v pol pristopa,

78
00:04:04,330 --> 00:04:07,450
čas delovanja najslabšem primeru
z binarno iskanje je

79
00:04:07,450 --> 00:04:11,730
log n, ki je v bistvu
bolje kot linearne Iskanje je n.

80
00:04:11,730 --> 00:04:13,570
Čas najboljšem primeru teče še ena.

81
00:04:13,570 --> 00:04:17,010
>> Lahko bi ga takoj našli
prvič naredimo delitev, vendar,

82
00:04:17,010 --> 00:04:19,339
še enkrat, ne pozabite, da
čeprav binarno iskanje je

83
00:04:19,339 --> 00:04:24,030
bistveno bolje kot linearni iskanju
ki jih zaradi tega, ker log n versus n,

84
00:04:24,030 --> 00:04:27,110
boste morda morali iti skozi delo
sortiranja svojo paleto prvi, ki

85
00:04:27,110 --> 00:04:32,010
Morda bi bilo manj učinkovito, odvisno
o velikosti ponavljanjem razvrščeni.

86
00:04:32,010 --> 00:04:35,250
>> Sem Doug Lloyd, to je CS50.

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