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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Så i CS50 vi lært om
en rekke sorterings- og søke

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

4
00:00:09,442 --> 00:00:11,400
Og noen ganger kan det være
litt vanskelig å holde

5
00:00:11,400 --> 00:00:14,161
rede på hva algoritme gjør hva.

6
00:00:14,161 --> 00:00:15,910
Vi har egentlig bare
skummet overflaten også,

7
00:00:15,910 --> 00:00:18,740
det er mange andre søking
og sortering algoritmer.

8
00:00:18,740 --> 00:00:21,780
Så i denne videoen la oss
bare ta noen få minutter

9
00:00:21,780 --> 00:00:24,980
å prøve og destillere hver algoritme
ned til sine kjerneelementer

10
00:00:24,980 --> 00:00:27,810
slik at du kan huske mest
viktig informasjon om dem

11
00:00:27,810 --> 00:00:31,970
og være i stand til å artikulere
forskjeller, om nødvendig.

12
00:00:31,970 --> 00:00:34,220
>> Den første er utvalget slag.

13
00:00:34,220 --> 00:00:38,210
Den grunnleggende ideen bak utvalget sort
er å finne den minste usortert element

14
00:00:38,210 --> 00:00:42,890
i en matrise og bytte det med
første usortert element av denne matrisen.

15
00:00:42,890 --> 00:00:46,620
Vi sa at det verste-fall
kjøretid fra som ble n squared.

16
00:00:46,620 --> 00:00:50,060
Og hvis du ønsker å huske hvorfor, ta
en titt på utvalget slags video.

17
00:00:50,060 --> 00:00:54,560
Den best-case kjøretid
er også n squared.

18
00:00:54,560 --> 00:00:58,910
>> Boble sortere, ideen bak det
en er å bytte tilstøtende par.

19
00:00:58,910 --> 00:01:01,730
Så det er nøkkelen som hjelper deg
Husk forskjellen her.

20
00:01:01,730 --> 00:01:04,920
Utvalg liksom er, så langt,
finne smallest-- boble

21
00:01:04,920 --> 00:01:06,790
sort er bytte tilstøtende par.

22
00:01:06,790 --> 00:01:08,710
Vi bytte tilstøtende par
elementer hvis de

23
00:01:08,710 --> 00:01:12,530
er ute av drift, noe som effektivt
bobler større elementer til høyre,

24
00:01:12,530 --> 00:01:17,060
og samtidig som den også begynner
å flytte mindre elementer til venstre.

25
00:01:17,060 --> 00:01:20,180
Den verst tenkelige tilfelle kjøretid
boble slag er n squared.

26
00:01:20,180 --> 00:01:23,476
Den best-case kjøretid
boble typen er n.

27
00:01:23,476 --> 00:01:25,350
Fordi i den situasjonen
vi ikke actually--

28
00:01:25,350 --> 00:01:27,141
vi kanskje ikke trenger å
gjøre noen bytteavtaler i det hele tatt.

29
00:01:27,141 --> 00:01:31,026
Vi trenger bare å lage én
passere tvers av alle n elementer.

30
00:01:31,026 --> 00:01:34,600
>> I innsetting sortere, den
Grunntanken her er skiftende.

31
00:01:34,600 --> 00:01:36,630
Det er nøkkelordet for innsetting slag.

32
00:01:36,630 --> 00:01:39,630
Vi kommer til å gå en gang gjennom
matrisen fra venstre til høyre.

33
00:01:39,630 --> 00:01:41,670
Og som vi gjør, er vi
kommer til å skifte elementer

34
00:01:41,670 --> 00:01:46,260
har vi allerede sett å gi plass til
små som trenger å passe et sted

35
00:01:46,260 --> 00:01:48,080
tilbake i det sortert delen.

36
00:01:48,080 --> 00:01:51,600
Så vi bygge den sorterte rekke én
element om gangen, fra venstre mot høyre,

37
00:01:51,600 --> 00:01:54,740
og vi skifte ting å gjøre plass.

38
00:01:54,740 --> 00:01:58,650
Worst-case kjøretid fra
innsetting slag er n squared.

39
00:01:58,650 --> 00:02:02,380
Den best-case kjøretid er n.

40
00:02:02,380 --> 00:02:05,380
>> Flett sort-- nøkkelordet
her er splitte og slå.

41
00:02:05,380 --> 00:02:08,949
Vi delt hel rekke, enten
det er seks elementer, åtte elementer,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- vi dele den
ned til det halve, det halve, det halve,

43
00:02:13,790 --> 00:02:17,720
før vi har under matrise
n ett element arrays.

44
00:02:17,720 --> 00:02:19,470
Et sett av n én elementrekker.

45
00:02:19,470 --> 00:02:22,640
Så vi startet med en
1000-element array,

46
00:02:22,640 --> 00:02:26,550
og vi kommer til et punkt der vi
har 1000 ett element arrays.

47
00:02:26,550 --> 00:02:30,990
Da begynner vi å fusjonere de under arrays
sammen igjen i riktig rekkefølge.

48
00:02:30,990 --> 00:02:34,860
Så vi tar to one-element arrays
og lage en to-element array.

49
00:02:34,860 --> 00:02:38,180
Vi tar to to-element arrays
og skape en fire-elementsatsen

50
00:02:38,180 --> 00:02:43,900
og så videre og så videre inntil vi har
igjen ombygd én n element array.

51
00:02:43,900 --> 00:02:48,410
>> Worst-case kjøretid fra
fusjonere slags er N ganger log n.

52
00:02:48,410 --> 00:02:52,390
Vi har n elementer, men
dette rekombinerende prosessen

53
00:02:52,390 --> 00:02:56,960
tar log n skritt for å få
tilbake til en hel rekke.

54
00:02:56,960 --> 00:03:01,160
Beste fall kjøretid er også n log
n fordi denne prosessen gjør egentlig ikke

55
00:03:01,160 --> 00:03:04,090
bryr seg om tabellen var
sortert eller ikke til å begynne med.

56
00:03:04,090 --> 00:03:07,590
Prosessen er den samme, er det
ingen måte å kortslutnings ting.

57
00:03:07,590 --> 00:03:11,610
Så n log n i verste fall
n log n i beste fall.

58
00:03:11,610 --> 00:03:13,960
>> Vi snakket om to-
søke algoritmer.

59
00:03:13,960 --> 00:03:16,230
Så lineær søk er om itera.

60
00:03:16,230 --> 00:03:19,500
Vi fortsetter gjennom hele arrayet
en gang, fra venstre til høyre,

61
00:03:19,500 --> 00:03:21,950
prøver å finne nummeret
at vi leter etter.

62
00:03:21,950 --> 00:03:24,550
Worst-case kjøretid er stor O av n.

63
00:03:24,550 --> 00:03:27,610
Det kan ta oss itera
over hver enkelt element

64
00:03:27,610 --> 00:03:30,660
å finne elementet vi leter
for, enten i den siste plassen,

65
00:03:30,660 --> 00:03:31,630
eller ikke i det hele tatt.

66
00:03:31,630 --> 00:03:34,720
Men vi kan ikke bekrefte at inntil
vi har sett på alt.

67
00:03:34,720 --> 00:03:36,730
m best-case, finner vi umiddelbart.

68
00:03:36,730 --> 00:03:41,060
Den best case driftstiden
lineær søk er omega for en.

69
00:03:41,060 --> 00:03:43,689
>> Endelig var det binære søk,
som krever assortert utvalg.

70
00:03:43,689 --> 00:03:45,605
Husk at det er en veldig
viktig faktor

71
00:03:45,605 --> 00:03:47,155
når du arbeider med binære søk.

72
00:03:47,155 --> 00:03:50,180
Det er en forutsetning for å hjelp it--
matrisen at du leter gjennom

73
00:03:50,180 --> 00:03:52,160
skal sorteres.

74
00:03:52,160 --> 00:03:54,500
Ellers nøkkelordet
er splitt og hersk.

75
00:03:54,500 --> 00:03:58,310
Splitte rekken i halv og
eliminere halvparten av elementene

76
00:03:58,310 --> 00:04:00,780
hver gang du går gjennom.

77
00:04:00,780 --> 00:04:04,330
På grunn av dette Splitt og hersk
og dele ting i halvparten tilnærming,

78
00:04:04,330 --> 00:04:07,450
worst-case kjøretid
av binære søk er

79
00:04:07,450 --> 00:04:11,730
log n, som er i det vesentlige
bedre enn lineær søk er n.

80
00:04:11,730 --> 00:04:13,570
Den best-case kjøre tiden er fortsatt en.

81
00:04:13,570 --> 00:04:17,010
>> Vi kan finne det umiddelbart
første gang vi gjør en divisjon, men,

82
00:04:17,010 --> 00:04:19,339
igjen, husk at
selv om binære søk er

83
00:04:19,339 --> 00:04:24,030
vesentlig bedre enn lineær søk
kraft av å være log n versus n,

84
00:04:24,030 --> 00:04:27,110
du kan ha til å gå gjennom arbeidet
sorterings array først, noe som

85
00:04:27,110 --> 00:04:32,010
kan gjøre det mindre effektivt avhengig
på størrelsen av den itera sortert.

86
00:04:32,010 --> 00:04:35,250
>> Jeg er Doug Lloyd, dette er CS50.

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