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ærte om
en række sortering og søgning

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

4
00:00:09,442 --> 00:00:11,400
Og nogle gange kan det være
lidt vanskelig at holde

5
00:00:11,400 --> 00:00:14,161
styr på, hvad algoritme gør hvad.

6
00:00:14,161 --> 00:00:15,910
Vi har virkelig kun
skummet overfladen også,

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

8
00:00:18,740 --> 00:00:21,780
Så i denne video lad os
bare tage et par minutter

9
00:00:21,780 --> 00:00:24,980
at forsøge at destillere hver algoritme
ned til dens centrale elementer

10
00:00:24,980 --> 00:00:27,810
så du kan huske den mest
vigtige oplysninger om dem

11
00:00:27,810 --> 00:00:31,970
og være i stand til at formulere det
forskelle, hvis nødvendigt.

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

13
00:00:34,220 --> 00:00:38,210
Den grundlæggende idé bag valg Sorter
er at finde den mindste usorterede element

14
00:00:38,210 --> 00:00:42,890
i et array og bytte den med
første usorteret element i denne matrix.

15
00:00:42,890 --> 00:00:46,620
Vi sagde, at det værst tænkelige
køre tidspunktet for denne var n potens.

16
00:00:46,620 --> 00:00:50,060
Og hvis du ønsker at huske hvorfor, tage
Et kig på valg Sorter video.

17
00:00:50,060 --> 00:00:54,560
Den bedste fald kørselstid
også n potens.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sortere, idéen bag det
den ene er at bytte tilstødende par.

19
00:00:58,910 --> 00:01:01,730
Så det er den nøgle, der hjælper dig
huske forskellen her.

20
00:01:01,730 --> 00:01:04,920
Valg Sorter er, indtil videre,
finde den smallest-- boble

21
00:01:04,920 --> 00:01:06,790
sortere sige bytte tilstødende par.

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

23
00:01:08,710 --> 00:01:12,530
er ude af drift, som effektivt
bobler større elementer til højre,

24
00:01:12,530 --> 00:01:17,060
og på samme tid, det også begynder
at flytte mindre elementer til venstre.

25
00:01:17,060 --> 00:01:20,180
Det værst tænkelige tilfælde kørselstid
boble slags er n potens.

26
00:01:20,180 --> 00:01:23,476
Den bedste fald kørselstid
af boble slags er n.

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

28
00:01:25,350 --> 00:01:27,141
vi måske ikke behøver at
eventuelle swaps overhovedet.

29
00:01:27,141 --> 00:01:31,026
Vi har kun at gøre en
passere over alle n elementer.

30
00:01:31,026 --> 00:01:34,600
>> I indsættelse sortere, den
grundlæggende idé her er ved at flytte.

31
00:01:34,600 --> 00:01:36,630
Det er nøgleordet til indsætning slags.

32
00:01:36,630 --> 00:01:39,630
Vi kommer til at træde en gang gennem
arrayet fra venstre til højre.

33
00:01:39,630 --> 00:01:41,670
Og som vi gør, er vi
kommer til at flytte elementer

34
00:01:41,670 --> 00:01:46,260
Vi har allerede set at gøre plads til
mindre, som trænger til at passe sted

35
00:01:46,260 --> 00:01:48,080
igen der sorteret del.

36
00:01:48,080 --> 00:01:51,600
Så vi bygger det sorterede vifte én
element ad gangen, fra venstre mod højre,

37
00:01:51,600 --> 00:01:54,740
og vi flytter ting at gøre plads.

38
00:01:54,740 --> 00:01:58,650
Det værst tænkelige køre tid af
indsættelse sorteringen er n potens.

39
00:01:58,650 --> 00:02:02,380
Den bedst tænkelige køre tid er n.

40
00:02:02,380 --> 00:02:05,380
>> Flet sort-- søgeordet
her er splittet og flette.

41
00:02:05,380 --> 00:02:08,949
Vi opdeler den fulde vifte, uanset om
det er seks elementer, otte elementer,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- vi delt det
ned til det halve, halve, halve,

43
00:02:13,790 --> 00:02:17,720
indtil vi har under matrix
n et element arrays.

44
00:02:17,720 --> 00:02:19,470
Et sæt af n et element arrays.

45
00:02:19,470 --> 00:02:22,640
Så vi startede med én
1000-element array,

46
00:02:22,640 --> 00:02:26,550
og vi kommer til det punkt, hvor vi
har 1.000 én-element arrays.

47
00:02:26,550 --> 00:02:30,990
Så begynder vi at flette disse sub arrays
sammen igen i den rigtige rækkefølge.

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

49
00:02:34,860 --> 00:02:38,180
Vi tager to to-element arrays
og skabe en fire-elementopstillingen

50
00:02:38,180 --> 00:02:43,900
og så videre og så videre, indtil vi har
igen ombygget en n element array.

51
00:02:43,900 --> 00:02:48,410
>> Det værst tænkelige køre tid af
mergesort er N gange log n.

52
00:02:48,410 --> 00:02:52,390
Vi har n elementer, men
denne rekombination proces

53
00:02:52,390 --> 00:02:56,960
tager log n skridt til at få
tilbage til en komplet vifte.

54
00:02:56,960 --> 00:03:01,160
Bedste fald køretid er også n log
n fordi denne proces ikke rigtig

55
00:03:01,160 --> 00:03:04,090
pleje om array var
sorteres eller ikke til at begynde med.

56
00:03:04,090 --> 00:03:07,590
Fremgangsmåden er den samme, er der
ingen måde at kortslutte ting.

57
00:03:07,590 --> 00:03:11,610
Så n log n i værste fald,
n log n i bedste fald.

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

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

60
00:03:16,230 --> 00:03:19,500
Vi går på tværs af arrayet
gang, fra venstre mod højre,

61
00:03:19,500 --> 00:03:21,950
forsøger at finde nummeret
at vi leder efter.

62
00:03:21,950 --> 00:03:24,550
Det værst tænkelige køre tid er stort O i n.

63
00:03:24,550 --> 00:03:27,610
Det kan tage os iteration
på tværs af hver eneste element

64
00:03:27,610 --> 00:03:30,660
at finde det element, vi leder
for, enten i den sidste position,

65
00:03:30,660 --> 00:03:31,630
eller slet ikke.

66
00:03:31,630 --> 00:03:34,720
Men vi kan ikke bekræfte, at indtil
Vi har kigget på alt.

67
00:03:34,720 --> 00:03:36,730
m det bedste tilfælde, finder vi det samme.

68
00:03:36,730 --> 00:03:41,060
Den bedste fald køre tid af
lineær søgning er omega på 1.

69
00:03:41,060 --> 00:03:43,689
>> Endelig var der binær søgning,
som kræver diverse array.

70
00:03:43,689 --> 00:03:45,605
Husk det er en meget
vigtig overvejelse

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

72
00:03:47,155 --> 00:03:50,180
Det er en forudsætning for at bruge det--
array, som du søger gennem

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

74
00:03:52,160 --> 00:03:54,500
Ellers nøgleordet
er kløft og erobre.

75
00:03:54,500 --> 00:03:58,310
Split array i halve og
fjerne halvdelen af ​​elementerne

76
00:03:58,310 --> 00:04:00,780
hver gang, som du fortsætte gennem.

77
00:04:00,780 --> 00:04:04,330
På grund af denne kløft og erobre
og opsplitning ting i halv tilgang,

78
00:04:04,330 --> 00:04:07,450
det værst tænkelige kørselstid
af binære søgning er

79
00:04:07,450 --> 00:04:11,730
log n, som i det væsentlige
bedre end lineær søgning s n.

80
00:04:11,730 --> 00:04:13,570
Den bedst tænkelige køre tiden er stadig en.

81
00:04:13,570 --> 00:04:17,010
>> Vi kan finde det straks
første gang vi laver en division, men,

82
00:04:17,010 --> 00:04:19,339
igen, så husk at
selv binær søgning er

83
00:04:19,339 --> 00:04:24,030
væsentligt bedre end lineær søgning
i kraft af at være log n versus n,

84
00:04:24,030 --> 00:04:27,110
du måske nødt til at gå gennem arbejdet
sortering arrayet først, hvilket

85
00:04:27,110 --> 00:04:32,010
kan gøre det mindre effektivt afhængigt
på størrelsen af ​​iteration sorteret.

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

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