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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Dus in CS50 we geleerd over
diverse sorteer- en zoekopties

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

4
00:00:09,442 --> 00:00:11,400
Soms kan het
een beetje lastig te houden

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

6
00:00:14,161 --> 00:00:15,910
We hebben eigenlijk alleen
magere het oppervlak ook,

7
00:00:15,910 --> 00:00:18,740
Er zijn vele andere zoeken
en sorteeralgoritmes.

8
00:00:18,740 --> 00:00:21,780
Dus in deze video laten we
slechts een paar minuten duren

9
00:00:21,780 --> 00:00:24,980
om te proberen te distilleren elk algoritme
tot zijn kernelementen

10
00:00:24,980 --> 00:00:27,810
dus je kunt de meest herinneren
belangrijke informatie over hen

11
00:00:27,810 --> 00:00:31,970
en in staat zijn om het te verwoorden
verschillen, indien nodig.

12
00:00:31,970 --> 00:00:34,220
>> De eerste is een soort selectie.

13
00:00:34,220 --> 00:00:38,210
Het basisidee achter selectie sorteren
ze zijn de kleinste ongesorteerde element

14
00:00:38,210 --> 00:00:42,890
in een array en wisselen met de
ongesorteerde eerste element van deze array.

15
00:00:42,890 --> 00:00:46,620
We hebben gezegd dat de worst-case
looptijd van die werd n kwadraat.

16
00:00:46,620 --> 00:00:50,060
En als je wilt herinneren waarom nemen
Een blik op de selectie soort video.

17
00:00:50,060 --> 00:00:54,560
De best-case runtime
Ook n kwadraat.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, het idee achter dat
een is om aangrenzende paren wisselen.

19
00:00:58,910 --> 00:01:01,730
Dus dat is de sleutel die u helpt
herinner me hier het verschil.

20
00:01:01,730 --> 00:01:04,920
Selectie soort is, tot nu toe,
vindt de smallest-- bubble

21
00:01:04,920 --> 00:01:06,790
sort wil ruilen aangrenzende paren.

22
00:01:06,790 --> 00:01:08,710
We wisselen aangrenzende paren
elementen indien zij

23
00:01:08,710 --> 00:01:12,530
zijn buiten de orde, die effectief
bubbels grotere elementen naar rechts,

24
00:01:12,530 --> 00:01:17,060
en tegelijkertijd begint ook
kleinere elementen naar links te verplaatsen.

25
00:01:17,060 --> 00:01:20,180
De worst-case case runtime
van bubble sort is n kwadraat.

26
00:01:20,180 --> 00:01:23,476
De best-case runtime
van bubble sort is n.

27
00:01:23,476 --> 00:01:25,350
Omdat in deze situatie
we niet actually--

28
00:01:25,350 --> 00:01:27,141
We zouden niet moeten
maken elke swaps op alle.

29
00:01:27,141 --> 00:01:31,026
We hebben slechts een te maken
passeren over alle n elementen.

30
00:01:31,026 --> 00:01:34,600
>> In insertion sort, de
basisidee hier is aan het verschuiven.

31
00:01:34,600 --> 00:01:36,630
Dat is het sleutelwoord voor het inbrengen soort.

32
00:01:36,630 --> 00:01:39,630
We gaan een keer te doorlopen
de array van links naar rechts.

33
00:01:39,630 --> 00:01:41,670
En als we dat doen, zijn we
naar elementen verschuiven

34
00:01:41,670 --> 00:01:46,260
We hebben al gezien om ruimte te maken voor
kleinere die moeten ergens passen

35
00:01:46,260 --> 00:01:48,080
terug doordat gesorteerd gedeelte.

36
00:01:48,080 --> 00:01:51,600
Dus we bouwen aan de gesorteerde array één
element tegelijk, van links naar rechts,

37
00:01:51,600 --> 00:01:54,740
en we verschuiven dingen om ruimte te maken.

38
00:01:54,740 --> 00:01:58,650
De worst-case looptijd van
insertion sort is n kwadraat.

39
00:01:58,650 --> 00:02:02,380
De best-case looptijd is n.

40
00:02:02,380 --> 00:02:05,380
>> Samenvoegen sort-- het trefwoord
hier is splitsen en samenvoegen.

41
00:02:05,380 --> 00:02:08,949
We deelden de volledige reeks, of
het zes elementen, acht elementen,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- we splitsen
tot de helft, de helft met de helft,

43
00:02:13,790 --> 00:02:17,720
totdat we onder scala
n één element arrays.

44
00:02:17,720 --> 00:02:19,470
Een verzameling van n één element arrays.

45
00:02:19,470 --> 00:02:22,640
Dus begonnen we met één
1000-element array,

46
00:02:22,640 --> 00:02:26,550
en we krijgen tot het punt waar we
heeft een 1000-element arrays.

47
00:02:26,550 --> 00:02:30,990
Dan beginnen we met die sub-arrays samenvoegen
weer bij elkaar in de juiste volgorde.

48
00:02:30,990 --> 00:02:34,860
Dus nemen we twee een-element arrays
en een twee-element array.

49
00:02:34,860 --> 00:02:38,180
We nemen twee twee-element arrays
en het creëren van een vier-element serie

50
00:02:38,180 --> 00:02:43,900
en zo voort en zo verder tot we hebben
weer herbouwd one n element array.

51
00:02:43,900 --> 00:02:48,410
>> De worst-case looptijd van
samenvoegen soort n keer log n.

52
00:02:48,410 --> 00:02:52,390
We hebben n elementen, maar
Dit recombineren proces

53
00:02:52,390 --> 00:02:56,960
neemt log n stappen om
terug naar volledige array.

54
00:02:56,960 --> 00:03:01,160
Het beste geval run tijd is ook n log
n omdat dit proces niet echt

55
00:03:01,160 --> 00:03:04,090
schelen of de array was
gesorteerd of niet te beginnen.

56
00:03:04,090 --> 00:03:07,590
Het proces is hetzelfde, er
geen manier om kortsluiting dingen.

57
00:03:07,590 --> 00:03:11,610
Zo n log n in het ergste geval,
n log n in het beste geval.

58
00:03:11,610 --> 00:03:13,960
>> We spraken over twee
zoeken algoritmen.

59
00:03:13,960 --> 00:03:16,230
Dus lineair zoeken is ongeveer iteratie.

60
00:03:16,230 --> 00:03:19,500
We verder over de array
een keer, van links naar rechts,

61
00:03:19,500 --> 00:03:21,950
proberen om het nummer te vinden
dat we zoeken.

62
00:03:21,950 --> 00:03:24,550
De worst-case looptijd is groot O n.

63
00:03:24,550 --> 00:03:27,610
Het zou ons iteratie
over elk element

64
00:03:27,610 --> 00:03:30,660
het element we zoeken vinden
voor, hetzij in de laatste positie,

65
00:03:30,660 --> 00:03:31,630
of helemaal niet.

66
00:03:31,630 --> 00:03:34,720
Maar we kunnen niet bevestigen dat tot
we hebben gekeken naar alles.

67
00:03:34,720 --> 00:03:36,730
m het beste geval, vinden we onmiddellijk.

68
00:03:36,730 --> 00:03:41,060
De best-case looptijd van
lineair zoeken is omega van 1.

69
00:03:41,060 --> 00:03:43,689
>> Ten slotte was er binary search,
die vereist dat diverse array.

70
00:03:43,689 --> 00:03:45,605
Vergeet niet dat is een zeer
belangrijke overweging

71
00:03:45,605 --> 00:03:47,155
bij het werken met binaire zoeken.

72
00:03:47,155 --> 00:03:50,180
Het is een vereiste voor het gebruik het--
de array die u op zoek bent door middel van

73
00:03:50,180 --> 00:03:52,160
moeten worden gesorteerd.

74
00:03:52,160 --> 00:03:54,500
Anders, de trefwoord
is verdeel en heers.

75
00:03:54,500 --> 00:03:58,310
Splits de array in de helft en
de helft van de elementen te elimineren

76
00:03:58,310 --> 00:04:00,780
elke keer als je verder door.

77
00:04:00,780 --> 00:04:04,330
Vanwege deze verdeel en heers
en splitsen dingen in de helft aanpak,

78
00:04:04,330 --> 00:04:07,450
het ergste geval runtime
van binaire zoeken is

79
00:04:07,450 --> 00:04:11,730
log n, die in hoofdzaak
beter dan lineair zoeken is n.

80
00:04:11,730 --> 00:04:13,570
De best-case run tijd is nog steeds één.

81
00:04:13,570 --> 00:04:17,010
>> We zouden het onmiddellijk het vinden
eerste keer maken we een divisie, maar,

82
00:04:17,010 --> 00:04:19,339
weer, bedenk dan dat
hoewel binaire zoeken is

83
00:04:19,339 --> 00:04:24,030
aanzienlijk beter dan lineair zoeken
vanwege zijn log n versus n,

84
00:04:24,030 --> 00:04:27,110
je zou kunnen hebben om te gaan door het werk
sorteren eerste array, waarbij

85
00:04:27,110 --> 00:04:32,010
zou het minder effectief afhankelijk maken
van de grootte van het itereren gesorteerd.

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

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