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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: So in CS50 ons geleer het oor
'n verskeidenheid van sortering en soek

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

4
00:00:09,442 --> 00:00:11,400
En soms is dit kan wees
'n bietjie lastig te hou

5
00:00:11,400 --> 00:00:14,161
spoor van wat algoritme wat doen.

6
00:00:14,161 --> 00:00:15,910
Ons het eintlik net
maer die oppervlak ook

7
00:00:15,910 --> 00:00:18,740
daar is baie ander soek
en sortering algoritmes.

8
00:00:18,740 --> 00:00:21,780
So in hierdie video laat
net 'n paar minute

9
00:00:21,780 --> 00:00:24,980
om te probeer en distilleer elke algoritme
af na die kern elemente

10
00:00:24,980 --> 00:00:27,810
sodat jy kan die mees onthou
belangrike inligting oor hulle

11
00:00:27,810 --> 00:00:31,970
en in staat wees om die te verwoord
verskille, indien nodig.

12
00:00:31,970 --> 00:00:34,220
>> Die eerste is seleksie soort.

13
00:00:34,220 --> 00:00:38,210
Die basiese idee agter seleksie soort
is te vind in die kleinste ongesorteerde element

14
00:00:38,210 --> 00:00:42,890
in 'n skikking en ruil dit met die
eerste ongesorteerde element van daardie skikking.

15
00:00:42,890 --> 00:00:46,620
Ons het gesê dat die ergste geval
hardloop tyd van wat n vierkant.

16
00:00:46,620 --> 00:00:50,060
En as jy wil om te onthou hoekom nie, neem
'n blik op die seleksie soort video.

17
00:00:50,060 --> 00:00:54,560
Die beste geval hardloop tyd
ook N kwadraat.

18
00:00:54,560 --> 00:00:58,910
>> Borrel soort, die idee agter dat
een is om aangrensende pare te ruil.

19
00:00:58,910 --> 00:01:01,730
So wat is die sleutel wat jy help
Onthou hier die verskil.

20
00:01:01,730 --> 00:01:04,920
Seleksie soort is, so ver,
vind die smallest-- borrel

21
00:01:04,920 --> 00:01:06,790
sorteer IS ruil aangrensende pare.

22
00:01:06,790 --> 00:01:08,710
Ons ruil aangrensende pare
elemente as hulle

23
00:01:08,710 --> 00:01:12,530
is buite orde, wat effektief
borrels groter elemente na regs,

24
00:01:12,530 --> 00:01:17,060
en op dieselfde tyd wat dit begin ook
kleiner elemente aan die linkerkant beweeg.

25
00:01:17,060 --> 00:01:20,180
Die ergste geval geval hardloop tyd
van die borrel soort is N kwadraat.

26
00:01:20,180 --> 00:01:23,476
Die beste geval hardloop tyd
van die borrel soort is n.

27
00:01:23,476 --> 00:01:25,350
Want in daardie situasie
ons nie actually--

28
00:01:25,350 --> 00:01:27,141
ons dalk nie nodig om
enige swaps at all.

29
00:01:27,141 --> 00:01:31,026
Ons het net om een ​​te maak
slaag in al n elemente.

30
00:01:31,026 --> 00:01:34,600
>> In invoeging soort, die
basiese idee hier is verskuiwing.

31
00:01:34,600 --> 00:01:36,630
Dit is die sleutelwoord vir invoeging soort.

32
00:01:36,630 --> 00:01:39,630
Ons gaan een keer stap vir stap deur
die skikking van links na regs.

33
00:01:39,630 --> 00:01:41,670
En as ons dit doen, ons is
gaan elemente skuif

34
00:01:41,670 --> 00:01:46,260
ons het reeds gesien om plek te maak vir
kleiner wat nodig het om iewers te pas

35
00:01:46,260 --> 00:01:48,080
terug in daardie gesorteer gedeelte.

36
00:01:48,080 --> 00:01:51,600
So ons bou die gesorteerde skikking een
element op 'n slag, van links na regs,

37
00:01:51,600 --> 00:01:54,740
en ons skuif dinge om plek te maak.

38
00:01:54,740 --> 00:01:58,650
Die ergste geval run tyd van
invoeging soort is N kwadraat.

39
00:01:58,650 --> 00:02:02,380
Die beste geval loop die tyd is n.

40
00:02:02,380 --> 00:02:05,380
>> Merge sort-- die navraag
hier is verdeel en saam te smelt.

41
00:02:05,380 --> 00:02:08,949
Ons verdeel die volle reeks, of
dit is ses elemente, agt elemente,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- ons verdeel dit
af met die helfte, met die helfte, met die helfte,

43
00:02:13,790 --> 00:02:17,720
totdat ons onder array
van N een element skikkings.

44
00:02:17,720 --> 00:02:19,470
'N stel van N een element skikkings.

45
00:02:19,470 --> 00:02:22,640
So het ons begin met 'n
1000-element skikking,

46
00:02:22,640 --> 00:02:26,550
en ons kry tot op die punt waar ons
het 1000 een-element skikkings.

47
00:02:26,550 --> 00:02:30,990
Dan begin ons om daardie sub skikkings saamsmelt
weer saam in die korrekte volgorde.

48
00:02:30,990 --> 00:02:34,860
So neem ons twee een-element skikkings
en die skep van 'n twee-element skikking.

49
00:02:34,860 --> 00:02:38,180
Ons neem twee twee-element skikkings
en die skep van 'n vier-element array

50
00:02:38,180 --> 00:02:43,900
en so aan en so aan totdat ons het
weer herbou een N element skikking.

51
00:02:43,900 --> 00:02:48,410
>> Die ergste geval run tyd van
saamsmelt soort is n keer inteken n.

52
00:02:48,410 --> 00:02:52,390
Ons het n elemente, maar
hierdie recombining proses

53
00:02:52,390 --> 00:02:56,960
neem meld N stappe te kry
terug na 'n volle reeks.

54
00:02:56,960 --> 00:03:01,160
Die beste geval loop die tyd is ook n log
N omdat hierdie proses nie regtig

55
00:03:01,160 --> 00:03:04,090
omgee of die skikking was
gesorteer of nie om te begin met.

56
00:03:04,090 --> 00:03:07,590
Die proses is dieselfde, daar is
geen manier om 'n kortsluiting dinge.

57
00:03:07,590 --> 00:03:11,610
So n teken N in die ergste geval,
N teken N in die beste geval.

58
00:03:11,610 --> 00:03:13,960
>> Ons het gepraat oor twee
soek algoritmes.

59
00:03:13,960 --> 00:03:16,230
So lineêre soek is sowat iterating.

60
00:03:16,230 --> 00:03:19,500
Ons gaan oor die skikking
een keer, van links na regs,

61
00:03:19,500 --> 00:03:21,950
probeer om die getal te vind
dat ons is op soek na.

62
00:03:21,950 --> 00:03:24,550
Die ergste geval loop die tyd is groot O van n.

63
00:03:24,550 --> 00:03:27,610
Dit mag dalk vir ons neem iterating
oor elke enkele element

64
00:03:27,610 --> 00:03:30,660
om die element wat ons soek vind
vir, óf in die laaste posisie,

65
00:03:30,660 --> 00:03:31,630
of glad nie.

66
00:03:31,630 --> 00:03:34,720
Maar ons kan nie bevestig dat tot
Ons het gekyk na alles.

67
00:03:34,720 --> 00:03:36,730
m die beste geval is, vind ons onmiddellik.

68
00:03:36,730 --> 00:03:41,060
Die beste geval run tyd van
lineêre soek is omega van 1.

69
00:03:41,060 --> 00:03:43,689
>> Laastens was daar binêre soek,
wat vereis verskillende skikking.

70
00:03:43,689 --> 00:03:45,605
Onthou dat 'n baie
belangrike oorweging

71
00:03:45,605 --> 00:03:47,155
wanneer daar met binêre soek.

72
00:03:47,155 --> 00:03:50,180
Dit is 'n voorvereiste vir die gebruik van it--
die skikking wat jy soek deur middel van

73
00:03:50,180 --> 00:03:52,160
gesorteer moet word.

74
00:03:52,160 --> 00:03:54,500
Andersins, die navraag
is verdeel en oorwin.

75
00:03:54,500 --> 00:03:58,310
Verdeel die skikking in die helfte en
helfte van die elemente te skakel

76
00:03:58,310 --> 00:04:00,780
elke keer as jy deur.

77
00:04:00,780 --> 00:04:04,330
As gevolg van hierdie Verdeel en oorwin
en verdeel dinge in die helfte benadering,

78
00:04:04,330 --> 00:04:07,450
die ergste geval hardloop tyd
van binêre soek is

79
00:04:07,450 --> 00:04:11,730
meld N, wat aansienlik is
beter as lineêre soek se n.

80
00:04:11,730 --> 00:04:13,570
Die beste geval loop die tyd is nog steeds een.

81
00:04:13,570 --> 00:04:17,010
>> Ons kan dit dadelik die vind
eerste keer maak ons ​​'n afdeling, maar

82
00:04:17,010 --> 00:04:19,339
weer, onthou dat
hoewel binêre soek is

83
00:04:19,339 --> 00:04:24,030
aansienlik beter as lineêre soek
uit hoofde van wat log N versus n,

84
00:04:24,030 --> 00:04:27,110
jy mag hê om te gaan deur die werk
sorteer jou array eerste, wat

85
00:04:27,110 --> 00:04:32,010
kan dit minder doeltreffend maak, afhangende
van die grootte van die iterating gesorteer.

86
00:04:32,010 --> 00:04:35,250
>> Ek is Doug Lloyd, dit is CS50.

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