1
00:00:00,000 --> 00:00:05,726
>> [Daqq tal-mużika]

2
00:00:05,726 --> 00:00:08,600
Doug LLOYD: tip Għażla huwa
algoritmu li, kif inti tista 'tistenna,

3
00:00:08,600 --> 00:00:10,470
xorta sett ta 'elementi.

4
00:00:10,470 --> 00:00:12,470
U recall algoritmu
huwa sett pass-pass

5
00:00:12,470 --> 00:00:15,260
ta 'struzzjonijiet għal kompletar ta' dmir.

6
00:00:15,260 --> 00:00:17,580
>> Fl-għażla isolvi l-
idea bażika hi din,

7
00:00:17,580 --> 00:00:22,080
isibu l-iżgħar element mhux magħżul u
iżżidhiex mal-aħħar tal-lista Issortjat.

8
00:00:22,080 --> 00:00:26,970
Effettivament dak li dan ma huwa build
lista magħżula, element wieħed kull darba.

9
00:00:26,970 --> 00:00:29,800
Breaking l-isfel għal pseudocode
nistgħu jiddikjaraw dan algoritmu

10
00:00:29,800 --> 00:00:34,490
kif ġej, irrepeti dan sakemm
ebda elementi mhux magħżula jibqgħu.

11
00:00:34,490 --> 00:00:38,660
Fittex permezz tal-mhux magħżul
data biex isibu l-iżgħar valur,

12
00:00:38,660 --> 00:00:44,130
imbagħad tpartit l-iżgħar valur ma 'l-
ewwel element tal-parti mhux magħżul.

13
00:00:44,130 --> 00:00:47,130
>> Hija tista 'tgħin biex Ħares dan,
Mela ejja tagħti ħarsa lejn din.

14
00:00:47,130 --> 00:00:49,710
Allura dan, I jsostnu, huwa
firxa magħżulin u stajt

15
00:00:49,710 --> 00:00:53,040
indika li billi jindika li l
mill-elementi huma kkuluriti aħmar,

16
00:00:53,040 --> 00:00:54,420
dawn għadhom ma jintgħażlux.

17
00:00:54,420 --> 00:00:57,670
Dan huwa l-kollu
parti mhux magħżul mill-firxa.

18
00:00:57,670 --> 00:01:02,020
>> Mela ejja jmorru permezz tal-passi ta '
sort għażla biex issolvi din array.

19
00:01:02,020 --> 00:01:05,296
Għalhekk għal darb'oħra, aħna qed irrepeti gonna
sakemm ebda elementi mhux magħżula jibqgħu.

20
00:01:05,296 --> 00:01:07,920
Aħna tfittxija gonna permezz tal-
data biex isibu l-iżgħar valur,

21
00:01:07,920 --> 00:01:11,990
u mbagħad tpartit dak il-valur ma 'l-
ewwel element tal-parti mhux magħżul.

22
00:01:11,990 --> 00:01:14,380
>> Dritt issa, għal darb'oħra, l kollu
firxa hija l-parti mhux magħżul.

23
00:01:14,380 --> 00:01:16,534
L-elementi kollha aħmar huma mhux magħżul.

24
00:01:16,534 --> 00:01:18,700
Allura aħna tfittxija permezz ta 'u
insibu l-iżgħar valur.

25
00:01:18,700 --> 00:01:20,533
Nibdew fil-bidu,
immorru l-għan,

26
00:01:20,533 --> 00:01:23,630
insibu l-iżgħar valur huwa, wieħed.

27
00:01:23,630 --> 00:01:24,860
Allura li l-parti waħda.

28
00:01:24,860 --> 00:01:29,440
U mbagħad parti tnejn, tpartit dak il-valur ma '
l-ewwel element tal-parti mhux magħżul,

29
00:01:29,440 --> 00:01:31,340
jew l-ewwel element aħmar.

30
00:01:31,340 --> 00:01:34,980
>> F'dan il-każ li jkun
ħames, hekk aħna tpartit wieħed u ħamsa.

31
00:01:34,980 --> 00:01:37,320
Meta nagħmlu dan, nistgħu
viżwalment tara li konna

32
00:01:37,320 --> 00:01:41,260
għamel il-iżgħar element vvalutati
mill-firxa, il-bidu nett.

33
00:01:41,260 --> 00:01:43,920
Effettivament issortjar dak l-element.

34
00:01:43,920 --> 00:01:47,520
>> U hekk nistgħu tabilħaqq jikkonferma
u jiddikjaraw li wieħed, huwa magħżul.

35
00:01:47,520 --> 00:01:52,080
U hekk aħna ser jindika l-porzjon magħżula
tal array tagħna, billi kulur huwa ikħal.

36
00:01:52,080 --> 00:01:53,860
>> Issa aħna biss irrepeti l-proċess mill-ġdid.

37
00:01:53,860 --> 00:01:57,430
Aħna tfittxija permezz tal-parti mhux magħżul ta '
l-array biex isibu l-element iżgħar.

38
00:01:57,430 --> 00:01:59,000
F'dan il-każ, huwa tnejn.

39
00:01:59,000 --> 00:02:02,100
>> Aħna tpartit li l-ewwel
element tad-naħa mhux magħżul.

40
00:02:02,100 --> 00:02:05,540
F'dan il-każ żewġ wkoll jiġri li jkun
l-ewwel element tal-parti mhux magħżul.

41
00:02:05,540 --> 00:02:08,650
Allura aħna tpartit tnejn bil innifsu,
li verament ftit tħalli tnejn

42
00:02:08,650 --> 00:02:11,257
fejn hi, u huwa magħżula.

43
00:02:11,257 --> 00:02:13,840
Kontinwa fuq, aħna tfittxija permezz
biex isibu l-element iżgħar.

44
00:02:13,840 --> 00:02:15,030
Huwa tlieta.

45
00:02:15,030 --> 00:02:17,650
Aħna tpartit ma 'l-ewwel
element, li huwa ħamsa.

46
00:02:17,650 --> 00:02:19,450
U issa tlieta huwa magħżul.

47
00:02:19,450 --> 00:02:22,440
>> Aħna tfittxija permezz-ġdid, u aħna
isibu l-iżgħar element huwa erbgħa.

48
00:02:22,440 --> 00:02:28,070
Aħna tpartit ma 'l-ewwel element tal-
parti mhux magħżul, u issa erbgħa huwa magħżul.

49
00:02:28,070 --> 00:02:29,910
>> Insibu li ħamsa
l-iżgħar element.

50
00:02:29,910 --> 00:02:32,900
Aħna tpartit ma 'l-ewwel
element tad-naħa mhux magħżul.

51
00:02:32,900 --> 00:02:34,740
U issa ħamsa huwa magħżul.

52
00:02:34,740 --> 00:02:36,660
>> U mbagħad fl-aħħar, tagħna
parti mhux magħżul jikkonsisti

53
00:02:36,660 --> 00:02:38,576
ta 'ftit element wieħed,
hekk aħna tfittex permezz

54
00:02:38,576 --> 00:02:41,740
u insibu li sitt huwa l-
iżgħar, u fil-fatt, biss element.

55
00:02:41,740 --> 00:02:44,906
U allura nistgħu istat li huwa magħżul.

56
00:02:44,906 --> 00:02:47,530
U issa konna mixgħula firxa tagħna
milli tkun kompletament mhux magħżul

57
00:02:47,530 --> 00:02:52,660
bl-aħmar, li mifthiema kompletament
bil-blu, bl-użu sort għażla.

58
00:02:52,660 --> 00:02:54,920
>> Allura x'inhu l-agħar każ hawnhekk?

59
00:02:54,920 --> 00:02:57,830
Ukoll fl-agħar assoluta
każ, irridu nħarsu fuq

60
00:02:57,830 --> 00:03:02,170
l-elementi kollha tal-firxa għal
isibu l-iżgħar element mhux magħżul,

61
00:03:02,170 --> 00:03:04,750
u għandna jirrepetu
dan il-proċess n darbiet.

62
00:03:04,750 --> 00:03:09,090
Darba għal kull element ta 'l-array
għaliex aħna biss, f'dan algoritmu,

63
00:03:09,090 --> 00:03:12,180
sort element wieħed fi żmien.

64
00:03:12,180 --> 00:03:13,595
>> X'inhu l-aħjar xenarju?

65
00:03:13,595 --> 00:03:15,040
Ukoll huwa eżattament l-istess, id-dritt?

66
00:03:15,040 --> 00:03:18,440
Aħna attwalment ikollhom xorta pass permezz
kull element wieħed ta 'l-array

67
00:03:18,440 --> 00:03:22,040
sabiex jikkonfermaw illi huwa,
fil-fatt, l-iżgħar element.

68
00:03:22,040 --> 00:03:26,760
>> Allura l-runtime agħar każ, aħna
għandhom jirrepetu proċess n drabi,

69
00:03:26,760 --> 00:03:28,960
darba għal kull wieħed mill-elementi n.

70
00:03:28,960 --> 00:03:31,940
U fil-aħjar xenarju,
għandna nagħmlu l-istess.

71
00:03:31,940 --> 00:03:35,340
>> Allura taħseb lura għall tagħna
toolbox kumplessità komputazzjoni,

72
00:03:35,340 --> 00:03:39,250
dak li inti taħseb hija l-agħar
każ runtime għall tip ta 'għażla?

73
00:03:39,250 --> 00:03:41,840
What do you think huwa l-aħjar
każ runtime għall tip ta 'għażla?

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

75
00:03:44,760 --> 00:03:49,325
>> Ridt raden Big O ta 'n kwadrat,
u Big Omega ta n kwadrat?

76
00:03:49,325 --> 00:03:49,950
Youd tkun id-dritt.

77
00:03:49,950 --> 00:03:52,490
Dawk huma, fil-fatt, il-
agħar każ u l-aħjar każ jibqa 'jiddekorri

78
00:03:52,490 --> 00:03:55,100
drabi, għal tip ta 'għażla.

79
00:03:55,100 --> 00:03:56,260
>> Jien Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Dan huwa CS50.

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