1
00:00:00,000 --> 00:00:05,726
>> [TÓNLIST spila]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Val tegund er
reiknirit sem, eins og þú might búast við,

3
00:00:08,600 --> 00:00:10,470
skiptir að setja af þáttum.

4
00:00:10,470 --> 00:00:12,470
Og reiknirit muna
er skref-fyrir-skref sett

5
00:00:12,470 --> 00:00:15,260
leiðbeiningar um að ljúka verkefni.

6
00:00:15,260 --> 00:00:17,580
>> Í vali raða
Grunnhugmyndin er þetta,

7
00:00:17,580 --> 00:00:22,080
finna minnstu óflokkuðu frumefni og
bæta því við lok raðaða listanum.

8
00:00:22,080 --> 00:00:26,970
Í raun hvað þetta gerir er að byggja
raðað lista, einn þáttur í einu.

9
00:00:26,970 --> 00:00:29,800
Brjóta hann niður sauðakóðanum
við gætum ríkisins þetta reiknirit

10
00:00:29,800 --> 00:00:34,490
eins og hér segir, endurtaka þetta þar til
engar óflokkaðar þættir áfram.

11
00:00:34,490 --> 00:00:38,660
Leita gegnum Óflokkaður
gögn til að finna minnstu gildi,

12
00:00:38,660 --> 00:00:44,130
þá skipta minnstu gildi með
Fyrsti þátturinn af óflokkaðs hluta.

13
00:00:44,130 --> 00:00:47,130
>> Það getur hjálpað að sjón þessa,
þannig að við skulum taka a líta á þetta.

14
00:00:47,130 --> 00:00:49,710
Svo, ég contend, er þetta
Óflokkaður array og ég hef

15
00:00:49,710 --> 00:00:53,040
kynna það með því að tilgreina að allir
af þeim þáttum eru lituð rauð,

16
00:00:53,040 --> 00:00:54,420
þeir eru ekki enn flokkaður.

17
00:00:54,420 --> 00:00:57,670
Þetta er allt
Óflokkaður hluti fylkisins.

18
00:00:57,670 --> 00:01:02,020
>> Svo skulum við fara í gegnum skrefin
val Raða til að raða þessu fylki.

19
00:01:02,020 --> 00:01:05,296
Svo aftur, við erum ađ endurtaka
uns engar óflokkaðar þættir áfram.

20
00:01:05,296 --> 00:01:07,920
Við ætlum að leita í gegnum
gögn til að finna minnstu gildi,

21
00:01:07,920 --> 00:01:11,990
og þá skipta þessi gildi með
Fyrsti þátturinn af óflokkaðs hluta.

22
00:01:11,990 --> 00:01:14,380
>> Núna, aftur, allt
array er Óflokkaður hluti.

23
00:01:14,380 --> 00:01:16,534
Alla rauða þættir eru Óflokkaður.

24
00:01:16,534 --> 00:01:18,700
Þannig að við leitað og
finnum lægsta gildi.

25
00:01:18,700 --> 00:01:20,533
Við byrjum á byrjun,
við förum til enda,

26
00:01:20,533 --> 00:01:23,630
finnum minnstu gildi er einn.

27
00:01:23,630 --> 00:01:24,860
Svo er það hluti einn.

28
00:01:24,860 --> 00:01:29,440
Og þá hluti tveir, skipta þessi gildi með
fyrsti þátturinn í óflokkaðs hluta,

29
00:01:29,440 --> 00:01:31,340
eða fyrsta rauða þáttur.

30
00:01:31,340 --> 00:01:34,980
>> Í þessu tilfelli sem væri
fimm, þannig að við skipta eitt og fimm.

31
00:01:34,980 --> 00:01:37,320
Þegar við gerum þetta, við getum
sjónrænt sjá að við höfum

32
00:01:37,320 --> 00:01:41,260
flutti minnstu metin þáttur
fylkisins, að upphafi.

33
00:01:41,260 --> 00:01:43,920
Í raun flokka sem þáttur.

34
00:01:43,920 --> 00:01:47,520
>> Og svo við getum örugglega staðfesta
og ástand sem einn, er flokkað.

35
00:01:47,520 --> 00:01:52,080
Og svo við munum kynna raðaða hluta
af array okkar, með því að lita það blátt.

36
00:01:52,080 --> 00:01:53,860
>> Nú erum við að endurtaka bara ferlið aftur.

37
00:01:53,860 --> 00:01:57,430
Við leit í gegnum óflokkuðu hluta
array til að finna minnstu frumefni.

38
00:01:57,430 --> 00:01:59,000
Í þessu tilfelli, er það tveir.

39
00:01:59,000 --> 00:02:02,100
>> Við skipta að með fyrsta
þáttur í óflokkaðs hluta.

40
00:02:02,100 --> 00:02:05,540
Í þessu tilfelli eru tveir gerist líka að vera
fyrsti þátturinn í óflokkaðs hluta.

41
00:02:05,540 --> 00:02:08,650
Þannig að við skipta tvö með sér,
sem í raun bara skilur tvö

42
00:02:08,650 --> 00:02:11,257
þar sem það er, og það er flokkað.

43
00:02:11,257 --> 00:02:13,840
Endurmenntun á, við leit í
að finna minnstu frumefni.

44
00:02:13,840 --> 00:02:15,030
Það er þrjú.

45
00:02:15,030 --> 00:02:17,650
Við skipta um það með fyrsta
þáttur, sem er fimm.

46
00:02:17,650 --> 00:02:19,450
Og nú þrjú er flokkaður.

47
00:02:19,450 --> 00:02:22,440
>> Við leit í gegnum aftur, og við
finna minnstu þáttur er fjórir.

48
00:02:22,440 --> 00:02:28,070
Við skipta um það með fyrsta þáttur af
Óflokkaður hluti, og nú fjögur er flokkaður.

49
00:02:28,070 --> 00:02:29,910
>> Við finnum að fimm er
minnsti þáttur.

50
00:02:29,910 --> 00:02:32,900
Við skipta um það með fyrsta
þáttur í óflokkaðs hluta.

51
00:02:32,900 --> 00:02:34,740
Og nú fimm er flokkaður.

52
00:02:34,740 --> 00:02:36,660
>> Og þá loks, okkar
Óflokkaður hluti samanstendur

53
00:02:36,660 --> 00:02:38,576
af réttlátur a einn þáttur,
svo við leitað í

54
00:02:38,576 --> 00:02:41,740
og við finnum að sex er
minnsta, og í raun aðeins þáttur.

55
00:02:41,740 --> 00:02:44,906
Og þá getum við fram að það er flokkað.

56
00:02:44,906 --> 00:02:47,530
Og nú höfum við kveikt array okkar
frá því að vera alveg óflokkuðu

57
00:02:47,530 --> 00:02:52,660
í rauðu, alveg flokkaður
í bláum, með val konar.

58
00:02:52,660 --> 00:02:54,920
>> Svo er það versta falli hér?

59
00:02:54,920 --> 00:02:57,830
Jæja í alger versta
ræða, verðum við að líta yfir

60
00:02:57,830 --> 00:03:02,170
alla þá þætti fylkisins til
finna minnstu óflokkuðu frumefni,

61
00:03:02,170 --> 00:03:04,750
og við verðum að endurtaka
Þetta ferli n sinnum.

62
00:03:04,750 --> 00:03:09,090
Einu sinni fyrir hvern hluta fylkisins
vegna þess að við bara, í þessum reiknirit,

63
00:03:09,090 --> 00:03:12,180
tegund einn þáttur í einu.

64
00:03:12,180 --> 00:03:13,595
>> Hvað er besta falli?

65
00:03:13,595 --> 00:03:15,040
Jæja það er nákvæmlega það sama, ekki satt?

66
00:03:15,040 --> 00:03:18,440
Við höfum í raun að enn stíga í gegnum
hvert einasta þáttur í fylkinu

67
00:03:18,440 --> 00:03:22,040
í því skyni að staðfesta að það er,
í raun minnstu þáttur.

68
00:03:22,040 --> 00:03:26,760
>> Svo versta afturkreistingur, við
að endurtaka ferli n sinnum,

69
00:03:26,760 --> 00:03:28,960
eina fyrir hvern N þætti.

70
00:03:28,960 --> 00:03:31,940
Og í besta falli,
við verðum að gera það sama.

71
00:03:31,940 --> 00:03:35,340
>> Svo hugsa til baka til okkar
computational flókið Verkfæri,

72
00:03:35,340 --> 00:03:39,250
hvað finnst þér er það versta
Málið afturkreistingur fyrir vali tagi?

73
00:03:39,250 --> 00:03:41,840
Hvað finnst þér best
Málið afturkreistingur fyrir vali tagi?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Vissir þú giska Big O n veldi,
og Big Omega n veldi?

76
00:03:49,325 --> 00:03:49,950
Þú vilt vera rétt.

77
00:03:49,950 --> 00:03:52,490
Þeir eru, í raun,
versta og besta tilfelli hlaupa

78
00:03:52,490 --> 00:03:55,100
sinnum, fyrir val tagi.

79
00:03:55,100 --> 00:03:56,260
>> Ég er Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Þetta er CS50.

81
00:03:58,600 --> 00:04:00,279