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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Svo í CS50 við lærðum um
a fjölbreytni af flokkun og leita

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

4
00:00:09,442 --> 00:00:11,400
Og stundum getur það verið
a lítill erfiður til að halda

5
00:00:11,400 --> 00:00:14,161
utan um hvað reiknirit gerir hvað.

6
00:00:14,161 --> 00:00:15,910
Við höfum í raun aðeins
undanrennu á yfirborðið líka,

7
00:00:15,910 --> 00:00:18,740
það eru margir aðrir leita
og flokkun reiknirit.

8
00:00:18,740 --> 00:00:21,780
Þannig að í þessu myndbandi við skulum
bara taka nokkrar mínútur

9
00:00:21,780 --> 00:00:24,980
til að reyna að distill hvert reiknirit
niður á meginþáttum hennar

10
00:00:24,980 --> 00:00:27,810
svo þú getur muna mest
mikilvægar upplýsingar um þá

11
00:00:27,810 --> 00:00:31,970
og vera fær um að gera grein fyrir þeim
munur, ef þörf krefur.

12
00:00:31,970 --> 00:00:34,220
>> Í fyrsta lagi er val tegund.

13
00:00:34,220 --> 00:00:38,210
Grunnhugmyndin á bak við val tagi
er að finna minnstu óflokkuðu þáttur

14
00:00:38,210 --> 00:00:42,890
í fjölda og skipta um það með
Fyrsta Óflokkaður þáttur þessi fylking.

15
00:00:42,890 --> 00:00:46,620
Við sögðum að versta
hlaupa tími sem var n veldi.

16
00:00:46,620 --> 00:00:50,060
Og ef þú vilt að muna hvers vegna, taka
a líta á val röðun vídeó.

17
00:00:50,060 --> 00:00:54,560
Besta falli hlaupa tími
er einnig N veldi.

18
00:00:54,560 --> 00:00:58,910
>> Kúla tegund, hugmyndin á bak við það
einn er að skipta aðliggjandi pör.

19
00:00:58,910 --> 00:01:01,730
Svo er það lykillinn sem hjálpar þér
muna muninn hér.

20
00:01:01,730 --> 00:01:04,920
Val tagi, svo langt,
finna smallest-- kúla

21
00:01:04,920 --> 00:01:06,790
tegund er Víxla aðliggjandi pör.

22
00:01:06,790 --> 00:01:08,710
Við skipta samliggjandi pör
staka ef þeir

23
00:01:08,710 --> 00:01:12,530
eru í ólagi, sem í raun
kúla stærri þætti til hægri,

24
00:01:12,530 --> 00:01:17,060
og á sama tíma sem það tekur líka
að færa smærri þætti til vinstri.

25
00:01:17,060 --> 00:01:20,180
Versta tilfelli hlaupa tími
af kúla tagi er n veldi.

26
00:01:20,180 --> 00:01:23,476
Besta falli hlaupa tími
af kúla tegund er n.

27
00:01:23,476 --> 00:01:25,350
Vegna þess að í því ástandi
við actually-- ekki

28
00:01:25,350 --> 00:01:27,141
við gætum ekki að
gera neinar skiptasamninga á öllum.

29
00:01:27,141 --> 00:01:31,026
Við þurfum aðeins að gera eitt
fara yfir öll n þáttum.

30
00:01:31,026 --> 00:01:34,600
>> Í Innsetningarröðun er
Grunnhugmyndin hér er að breytast.

31
00:01:34,600 --> 00:01:36,630
Það er leitarorðið til innsetningu tagi.

32
00:01:36,630 --> 00:01:39,630
Við erum að fara að stíga einu sinni í gegnum
array frá vinstri til hægri.

33
00:01:39,630 --> 00:01:41,670
Og eins og við gerum, við erum
fara að skipta þætti

34
00:01:41,670 --> 00:01:46,260
við höfum þegar séð að gera pláss fyrir
minni sjálfur sem þarf að passa einhversstaðar

35
00:01:46,260 --> 00:01:48,080
aftur í þeirri flokkað hluta.

36
00:01:48,080 --> 00:01:51,600
Þannig að við að byggja raðaða array einn
þáttur í einu, vinstri til hægri,

37
00:01:51,600 --> 00:01:54,740
og við skipta hluti til að gera herbergi.

38
00:01:54,740 --> 00:01:58,650
Versta hlaupa tími
innsetning tegund er n veldi.

39
00:01:58,650 --> 00:02:02,380
Besta falli hlaupa tími er n.

40
00:02:02,380 --> 00:02:05,380
>> Sameina sort-- leitarorðinu
hér er hættu og sameinast.

41
00:02:05,380 --> 00:02:08,949
Við hættu fullt array, hvort
það er sex þætti, átta þætti,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- við hættu það
niður um helming, um helming, um helming,

43
00:02:13,790 --> 00:02:17,720
þar til við höfum undir array
af n einn þáttur fylki.

44
00:02:17,720 --> 00:02:19,470
A setja af n einn þáttur fylki.

45
00:02:19,470 --> 00:02:22,640
Þannig að við byrjuðum með einn
1000-þáttur array,

46
00:02:22,640 --> 00:02:26,550
og við fá til the benda hvar við
hafa 1.000 eitt frumefni fylki.

47
00:02:26,550 --> 00:02:30,990
Þá erum við að byrja að sameina þær undir fylki
aftur saman í réttri röð.

48
00:02:30,990 --> 00:02:34,860
Svo við tökum tvær eitt frumefni fylki
og búa til tveggja-þáttur fylkisins.

49
00:02:34,860 --> 00:02:38,180
Við taka tvær tveggja frumefni fylki
og búa til fjögurra þátturinn array

50
00:02:38,180 --> 00:02:43,900
og svo framvegis og svo framvegis þar til að við höfum
aftur endurreist einn n þátturinn array.

51
00:02:43,900 --> 00:02:48,410
>> Versta hlaupa tími
sameinast tagi n sinnum log n.

52
00:02:48,410 --> 00:02:52,390
Við höfum n þætti, en
þetta recombining ferli

53
00:02:52,390 --> 00:02:56,960
tekur log n skref til að fá
baka að fullu fylki.

54
00:02:56,960 --> 00:03:01,160
Besta ræða hlaupa tími er einnig n log
n vegna þess að þetta ferli er í raun ekki

55
00:03:01,160 --> 00:03:04,090
sama hvort array var
raðað eða ekki til að byrja með.

56
00:03:04,090 --> 00:03:07,590
Ferlið er það sama, það er
engin leið að stuttum hlutum hringrás.

57
00:03:07,590 --> 00:03:11,610
Svo n log n í versta tilfelli,
n log n í besta tilfelli.

58
00:03:11,610 --> 00:03:13,960
>> Við ræddum um tvo
leita reiknirit.

59
00:03:13,960 --> 00:03:16,230
Svo er línuleg leit um iterating.

60
00:03:16,230 --> 00:03:19,500
Við halda áfram yfir í fylkinu
einu sinni, frá vinstri til hægri,

61
00:03:19,500 --> 00:03:21,950
reyna að finna fjölda
sem við erum að leita að.

62
00:03:21,950 --> 00:03:24,550
Versta hlaupa tími er stór O á n.

63
00:03:24,550 --> 00:03:27,610
Það gæti tekið okkur iterating
yfir hverjum einasta þætti

64
00:03:27,610 --> 00:03:30,660
að finna þáttur sem við erum að leita
fyrir, annað hvort í neðstu stöðu,

65
00:03:30,660 --> 00:03:31,630
eða alls ekki.

66
00:03:31,630 --> 00:03:34,720
En við getum ekki staðfest að fyrr
við höfum litið á allt.

67
00:03:34,720 --> 00:03:36,730
m besta falli, finnum við strax.

68
00:03:36,730 --> 00:03:41,060
Besta falli hlaupa tími
línuleg leit er omega af 1.

69
00:03:41,060 --> 00:03:43,689
>> Loks var tvöfaldur leit,
sem krefst blandað fylkisins.

70
00:03:43,689 --> 00:03:45,605
Mundu það er mjög
mikilvægt huga

71
00:03:45,605 --> 00:03:47,155
þegar unnið er með tvöfaldur leit.

72
00:03:47,155 --> 00:03:50,180
Það er forsenda þess að nota it--
array sem þú ert að leita í gegnum

73
00:03:50,180 --> 00:03:52,160
verður flokkaður.

74
00:03:52,160 --> 00:03:54,500
Annars leitarorðið
er gjá og sigra.

75
00:03:54,500 --> 00:03:58,310
Skipta array í tvennt og
útrýma helmingur af þeim þáttum

76
00:03:58,310 --> 00:04:00,780
í hvert skipti sem þú halda áfram í gegnum.

77
00:04:00,780 --> 00:04:04,330
Vegna þessa skipta og sigra
og skerandi hlutir í hálfa nálgun,

78
00:04:04,330 --> 00:04:07,450
versta hlaupa tími
af tvöfaldur leit er

79
00:04:07,450 --> 00:04:11,730
log n, sem er að mestu leyti
betri en n línuleg leit er.

80
00:04:11,730 --> 00:04:13,570
Besta falli hlaupa tími er enn einn.

81
00:04:13,570 --> 00:04:17,010
>> Við gætum fundið það strax
fyrsta skipti sem við tökum deild, en

82
00:04:17,010 --> 00:04:19,339
aftur, muna að
þó tvöfaldur leit er

83
00:04:19,339 --> 00:04:24,030
talsvert betri en línuleg leit
í krafti þess að vera log n móti n,

84
00:04:24,030 --> 00:04:27,110
þú gætir þurft að fara í gegnum vinnu
að flokka array fyrst, sem

85
00:04:27,110 --> 00:04:32,010
gæti gert það árangri minna eftir
á stærð iterating flokkað.

86
00:04:32,010 --> 00:04:35,250
>> Ég er Doug Lloyd, þetta er CS50.

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