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 oss om
en variation av sortering och sökning

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

4
00:00:09,442 --> 00:00:11,400
Och ibland kan det vara
lite knepigt att hålla

5
00:00:11,400 --> 00:00:14,161
koll på vad algoritmen gör vad.

6
00:00:14,161 --> 00:00:15,910
Vi har egentligen bara
skum ytan också,

7
00:00:15,910 --> 00:00:18,740
det finns många andra sökning
och sorteringsalgoritmer.

8
00:00:18,740 --> 00:00:21,780
Så i den här videon låt oss
bara ta några minuter

9
00:00:21,780 --> 00:00:24,980
att försöka destillera varje algoritm
ner till kärnelement

10
00:00:24,980 --> 00:00:27,810
så att du kan minnas mest
viktig information om dem

11
00:00:27,810 --> 00:00:31,970
och kunna artikulera
skillnader vid behov.

12
00:00:31,970 --> 00:00:34,220
>> Den första är valet slag.

13
00:00:34,220 --> 00:00:38,210
Den grundläggande idén bakom val Sortera
är att hitta den minsta osorterade elementet

14
00:00:38,210 --> 00:00:42,890
i en matris och byta den med
första osorterat del av denna uppsättning.

15
00:00:42,890 --> 00:00:46,620
Vi sade att det värsta
körtid av som n kvadrat.

16
00:00:46,620 --> 00:00:50,060
Och om du vill återkalla varför, ta
En titt på valet sorterings video.

17
00:00:50,060 --> 00:00:54,560
Det bästa fall körtid
är också n kvadrat.

18
00:00:54,560 --> 00:00:58,910
>> Bubbelsortering, tanken bakom det
en är att byta intilliggande par.

19
00:00:58,910 --> 00:01:01,730
Så det är nyckeln som hjälper dig
minns skillnaden här.

20
00:01:01,730 --> 00:01:04,920
Val slag är, hittills,
hitta smallest-- bubblan

21
00:01:04,920 --> 00:01:06,790
sort vill säga byta närliggande par.

22
00:01:06,790 --> 00:01:08,710
Vi byter närliggande par
av element, om de

23
00:01:08,710 --> 00:01:12,530
är i ordning, som effektivt
bubblor större element till höger,

24
00:01:12,530 --> 00:01:17,060
och på samma gång också börjar
att flytta mindre element till vänster.

25
00:01:17,060 --> 00:01:20,180
Det värsta fall fall körtid
av bubbelsortering är N i kvadrat.

26
00:01:20,180 --> 00:01:23,476
Det bästa fall körtid
av bubbelsortering är n.

27
00:01:23,476 --> 00:01:25,350
För i den situationen
vi inte actually--

28
00:01:25,350 --> 00:01:27,141
Vi kanske inte behöver
göra några swappar alls.

29
00:01:27,141 --> 00:01:31,026
Vi behöver bara göra en
passera över alla n element.

30
00:01:31,026 --> 00:01:34,600
>> I insättningssortering, den
Grundtanken här håller på att förskjutas.

31
00:01:34,600 --> 00:01:36,630
Det är nyckelordet för insättningssortering.

32
00:01:36,630 --> 00:01:39,630
Vi kommer att gå en gång genom
arrayen från vänster till höger.

33
00:01:39,630 --> 00:01:41,670
Och när vi gör, vi är
kommer att skifta element

34
00:01:41,670 --> 00:01:46,260
Vi har redan sett att göra plats för
mindre som behöver passa någonstans

35
00:01:46,260 --> 00:01:48,080
tillbaka i den sorterade delen.

36
00:01:48,080 --> 00:01:51,600
Så vi bygger den sorterade arrayen en
element i taget, från vänster till höger,

37
00:01:51,600 --> 00:01:54,740
och vi flytta saker att göra rummet.

38
00:01:54,740 --> 00:01:58,650
Det värsta fall gångtid
insättningssortering är n kvadrat.

39
00:01:58,650 --> 00:02:02,380
Det bästa fall körtid är n.

40
00:02:02,380 --> 00:02:05,380
>> Merge sort-- sökordet
Här delas och samman.

41
00:02:05,380 --> 00:02:08,949
Vi dela full uppsättning, om
Det är sex delar, åtta delar,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- vi dela den
ned med hälften, med hälften, med hälften,

43
00:02:13,790 --> 00:02:17,720
tills vi har i array
n en elementuppsättningar.

44
00:02:17,720 --> 00:02:19,470
En uppsättning n en elementuppsättningar.

45
00:02:19,470 --> 00:02:22,640
Så vi började med en
1000-elementgrupp,

46
00:02:22,640 --> 00:02:26,550
och vi kommer till den punkt där vi
har 1000 ett element matriser.

47
00:02:26,550 --> 00:02:30,990
Då börjar vi att slå samman dessa undergrupper
tillbaka tillsammans i rätt ordning.

48
00:02:30,990 --> 00:02:34,860
Så vi tar två en-elementuppsättningar
och skapa en två-elementgrupp.

49
00:02:34,860 --> 00:02:38,180
Vi tar två två-elementuppsättningar
och skapa en fyra-elementgrupp

50
00:02:38,180 --> 00:02:43,900
och så vidare och så vidare tills vi har
igen ombyggd en n elementgrupp.

51
00:02:43,900 --> 00:02:48,410
>> Det värsta fall gångtid
merge sort är N gånger log n.

52
00:02:48,410 --> 00:02:52,390
Vi har n element, men
denna rekombinering process

53
00:02:52,390 --> 00:02:56,960
tar log n steg för att få
tillbaka till ett komplett utbud.

54
00:02:56,960 --> 00:03:01,160
I bästa fall körtid är också n log
n eftersom denna process inte riktigt

55
00:03:01,160 --> 00:03:04,090
bryr sig om gruppen var
sorterade eller inte till att börja med.

56
00:03:04,090 --> 00:03:07,590
Processen är densamma, det finns
inget sätt att kortslutnings saker.

57
00:03:07,590 --> 00:03:11,610
Så n log n i värsta fall,
n log n i bästa fall.

58
00:03:11,610 --> 00:03:13,960
>> Vi pratade om två
sökalgoritmer.

59
00:03:13,960 --> 00:03:16,230
Så linjär sökning handlar om iteration.

60
00:03:16,230 --> 00:03:19,500
Vi fortsätter över arrayen
en gång, från vänster till höger,

61
00:03:19,500 --> 00:03:21,950
försöka hitta numret
att vi letar efter.

62
00:03:21,950 --> 00:03:24,550
Det värsta fall körtid är stort O n.

63
00:03:24,550 --> 00:03:27,610
Det kan ta oss iterera
över varje enskilt element

64
00:03:27,610 --> 00:03:30,660
att hitta elementet vi söker
för, antingen i den sista positionen,

65
00:03:30,660 --> 00:03:31,630
eller inte alls.

66
00:03:31,630 --> 00:03:34,720
Men vi kan inte bekräfta att tills
Vi har tittat på allt.

67
00:03:34,720 --> 00:03:36,730
m bästa fall finner vi omedelbart.

68
00:03:36,730 --> 00:03:41,060
Bästa fall gångtid
linjär sökning är omega 1.

69
00:03:41,060 --> 00:03:43,689
>> Slutligen fanns det binär sökning,
vilket kräver diverse array.

70
00:03:43,689 --> 00:03:45,605
Kom ihåg att det är en mycket
viktigt övervägande

71
00:03:45,605 --> 00:03:47,155
när man arbetar med binär sökning.

72
00:03:47,155 --> 00:03:50,180
Det är en förutsättning för att använda det--
matrisen som du söker igenom

73
00:03:50,180 --> 00:03:52,160
måste sorteras.

74
00:03:52,160 --> 00:03:54,500
Annars sökordet
är söndra och härska.

75
00:03:54,500 --> 00:03:58,310
Split arrayen till hälften och
eliminera hälften av elementen

76
00:03:58,310 --> 00:04:00,780
varje gång som du går igenom.

77
00:04:00,780 --> 00:04:04,330
På grund av denna söndra och härska
och dela upp saker i halv strategi

78
00:04:04,330 --> 00:04:07,450
det värsta körning
av binär sökning är

79
00:04:07,450 --> 00:04:11,730
log n, som är väsentligen
bättre än linjär sökning på n.

80
00:04:11,730 --> 00:04:13,570
Det bästa fall körtid är fortfarande ett.

81
00:04:13,570 --> 00:04:17,010
>> Vi kanske tycker att det omedelbart
första gången vi gör en uppdelning, men

82
00:04:17,010 --> 00:04:19,339
igen, kom ihåg att
även om binär sökning är

83
00:04:19,339 --> 00:04:24,030
betydligt bättre än linjär sökning
genom att vara log n kontra n

84
00:04:24,030 --> 00:04:27,110
du kanske måste gå igenom arbetet
sorterings arrayen först, vilket

85
00:04:27,110 --> 00:04:32,010
kan göra det mindre effektivt beroende
på storleken av den iteration sortering.

86
00:04:32,010 --> 00:04:35,250
>> Jag är Doug Lloyd, är detta CS50.

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