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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Nii CS50 me õppinud
erinevaid sorteerimise ja otsimise

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

4
00:00:09,442 --> 00:00:11,400
Ja mõnikord võib see olla
natuke keeruline hoida

5
00:00:11,400 --> 00:00:14,161
lugu, mida algoritm teeb mida.

6
00:00:14,161 --> 00:00:15,910
Me oleme tõesti ainult
kooritud pinda liiga,

7
00:00:15,910 --> 00:00:18,740
seal on palju muid otsimine
ja sorteerimine algoritme.

8
00:00:18,740 --> 00:00:21,780
Nii see video olgem
lihtsalt võtta paar minutit

9
00:00:21,780 --> 00:00:24,980
proovida ja ajama iga algoritmi
alla selle põhielemendid

10
00:00:24,980 --> 00:00:27,810
nii et sa ei mäleta kõige
Olulist teavet nende

11
00:00:27,810 --> 00:00:31,970
ja suutma väljendada
erinevusi, kui vaja.

12
00:00:31,970 --> 00:00:34,220
>> Esimene on valikut omamoodi.

13
00:00:34,220 --> 00:00:38,210
Põhiidee valikut omamoodi
on leida väikseim sorteerimata element

14
00:00:38,210 --> 00:00:42,890
massiivi ja vahetada see välja
Esimene sorteerimata element, mis massiivi.

15
00:00:42,890 --> 00:00:46,620
Me ütlesime, et halvima
käivitada ajal, mis oli n ruudus.

16
00:00:46,620 --> 00:00:50,060
Ja kui sa tahad meenutada, miks võtta
Pilk valikut omamoodi video.

17
00:00:50,060 --> 00:00:54,560
Parim puhul töötamise ajal
Samuti n ruudus.

18
00:00:54,560 --> 00:00:58,910
>> Bubble omamoodi, mõte, et
üks on vahetada külgnevate paari.

19
00:00:58,910 --> 00:01:01,730
Nii et see võti, mis aitab teil
mäletan siin midagi.

20
00:01:01,730 --> 00:01:04,920
Valik sorteerida on seni
leida smallest-- mull

21
00:01:04,920 --> 00:01:06,790
sorteerida on swap kõrval paari.

22
00:01:06,790 --> 00:01:08,710
Me swap kõrval paari
elementide kui nad

23
00:01:08,710 --> 00:01:12,530
on rikkis, mis tegelikult
mullid suuremaid elemente paremale,

24
00:01:12,530 --> 00:01:17,060
ja samal ajal algab ka
liikuda väiksemate elementide vasakule.

25
00:01:17,060 --> 00:01:20,180
Halvima juhtumis aeg
mull omamoodi on n ruudus.

26
00:01:20,180 --> 00:01:23,476
Parim puhul töötamise ajal
mull sorteerida on n.

27
00:01:23,476 --> 00:01:25,350
Kuna selles olukorras
me ei actually--

28
00:01:25,350 --> 00:01:27,141
Me ei pruugi vaja
teha vahetustehinguid üldse.

29
00:01:27,141 --> 00:01:31,026
Meil on ainult teha üks
läbida kõik n elementi.

30
00:01:31,026 --> 00:01:34,600
>> In sisestamise omamoodi, siis
Põhiidee siin liigub.

31
00:01:34,600 --> 00:01:36,630
See on märksõna sisestamise omamoodi.

32
00:01:36,630 --> 00:01:39,630
Me läheme samm korraga läbi
massiivi vasakult paremale.

33
00:01:39,630 --> 00:01:41,670
Ja kui me seda teeme, oleme
hakkab nihkuma elemendid

34
00:01:41,670 --> 00:01:46,260
me oleme juba näinud, et teha ruumi
väiksemad, mis vaja, et kusagil

35
00:01:46,260 --> 00:01:48,080
tagasi, et järjestatud osa.

36
00:01:48,080 --> 00:01:51,600
Nii me ehitame sorteeritud massiivi üks
element korraga, vasakult paremale,

37
00:01:51,600 --> 00:01:54,740
ja muudame asju teha ruumi.

38
00:01:54,740 --> 00:01:58,650
Halvima run aeg
sisestamise omamoodi on n ruudus.

39
00:01:58,650 --> 00:02:02,380
Parim puhul kestab aeg on n.

40
00:02:02,380 --> 00:02:05,380
>> Merge sort-- märksõna
Siin on jagatud ja ühendada.

41
00:02:05,380 --> 00:02:08,949
Me jagada kogu massiivi, kas
see on kuus elementi, kaheksa elemente,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- me jagada see
alla poole, poole, poole,

43
00:02:13,790 --> 00:02:17,720
kuni meil on all massiivi
n üks element massiivi.

44
00:02:17,720 --> 00:02:19,470
Komplekt n üks element massiivi.

45
00:02:19,470 --> 00:02:22,640
Nii me alustasime ühe
1000-element massiivi,

46
00:02:22,640 --> 00:02:26,550
ja me jõuame punkti, kus me
on 1000 üks element massiivi.

47
00:02:26,550 --> 00:02:30,990
Siis hakkame ühendada need sub massiivid
tagasi kokku õiges järjekorras.

48
00:02:30,990 --> 00:02:34,860
Nii me võtame kaks ühe elemendi massiivid
ja luua kaks elementi massiivi.

49
00:02:34,860 --> 00:02:38,180
Võtame kaks kahe elemendi massiivid
ja luua nelja elementi massiivi

50
00:02:38,180 --> 00:02:43,900
ja nii edasi ja nii edasi, kuni me oleme
uuesti ümber ühe n element massiivi.

51
00:02:43,900 --> 00:02:48,410
>> Halvima run aeg
ühendada sorteerida on n korda sisse n.

52
00:02:48,410 --> 00:02:52,390
Meil on n elementi, kuid
Selle recombining protsessi

53
00:02:52,390 --> 00:02:56,960
võtab sisse n samme, et saada
tagasi täis massiivi.

54
00:02:56,960 --> 00:03:01,160
Parimal juhul kestab aeg on ka n log
n, sest see protsess ei ole tegelikult

55
00:03:01,160 --> 00:03:04,090
huvita, kas massiiv oli
järjestatud või mitte alustada.

56
00:03:04,090 --> 00:03:07,590
Protsess on sama, seal on
kuidagi lühise asju.

57
00:03:07,590 --> 00:03:11,610
Nii n log n halvimal juhul,
n log n parimal juhul.

58
00:03:11,610 --> 00:03:13,960
>> Rääkisime kaks
otsivad algoritme.

59
00:03:13,960 --> 00:03:16,230
Nii lineaarne otsing on umbes iterating.

60
00:03:16,230 --> 00:03:19,500
Lähtume kogu massiivi
kord, vasakult paremale,

61
00:03:19,500 --> 00:03:21,950
püüdes leida number
et me otsime.

62
00:03:21,950 --> 00:03:24,550
Halvima jooksuga on suur O n.

63
00:03:24,550 --> 00:03:27,610
See võib meid iterating
üle iga element

64
00:03:27,610 --> 00:03:30,660
leida element ootame
eest, kas viimasel positsioonil

65
00:03:30,660 --> 00:03:31,630
või üldse mitte.

66
00:03:31,630 --> 00:03:34,720
Kuid me ei saa kinnitada, et kuni
me vaatasime kõike.

67
00:03:34,720 --> 00:03:36,730
olen parimal juhul leiame kohe.

68
00:03:36,730 --> 00:03:41,060
Parim puhul run aeg
lineaarne otsing on omega 1.

69
00:03:41,060 --> 00:03:43,689
>> Lõpuks oli Kahendotsingupuu,
mis nõuab assortii massiivi.

70
00:03:43,689 --> 00:03:45,605
Pea meeles, et on väga
tähtsam

71
00:03:45,605 --> 00:03:47,155
töötamisel Kahendotsingupuu.

72
00:03:47,155 --> 00:03:50,180
See on eelduseks, et kasutades see--
massiivi, et te otsite läbi

73
00:03:50,180 --> 00:03:52,160
tuleb sorteerida.

74
00:03:52,160 --> 00:03:54,500
Muidu märksõna
on jaga ja valitse.

75
00:03:54,500 --> 00:03:58,310
Split massiivi pooleks ja
kõrvaldada pool elemendid

76
00:03:58,310 --> 00:04:00,780
iga kord, kui sa sõita läbi.

77
00:04:00,780 --> 00:04:04,330
Sellepärast jaga ja valitse
ja jagamise asju poole lähenemist,

78
00:04:04,330 --> 00:04:07,450
halvima töötamise ajal
kahekomponentsete otsing on

79
00:04:07,450 --> 00:04:11,730
log n, mis on praktiliselt
parem kui lineaarne otsing on n.

80
00:04:11,730 --> 00:04:13,570
Parim puhul kestab ajad on ikka üks.

81
00:04:13,570 --> 00:04:17,010
>> Me võime leida see kohe
Esimene kord, kui me jagunemine, kuid

82
00:04:17,010 --> 00:04:19,339
uuesti, pea meeles, et
kuigi Kahendotsingupuu on

83
00:04:19,339 --> 00:04:24,030
oluliselt parem kui lineaarne otsing
tõttu on samamoodi n versus n,

84
00:04:24,030 --> 00:04:27,110
sa oleks võinud minna läbi tööd
sorteerimine oma massiivi esimene, mis

85
00:04:27,110 --> 00:04:32,010
võib teha vähem tõhusad sõltuvalt
suurusest ning iterating järjestatud.

86
00:04:32,010 --> 00:04:35,250
>> Ma olen Doug Lloyd, see on CS50.

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