1
00:00:00,000 --> 00:00:05,726
>> [MUZIKO Ludante]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Selektado speco estas
algoritmo kiu, kiel vi eble atendus,

3
00:00:08,600 --> 00:00:10,470
ordigas aron de elementoj.

4
00:00:10,470 --> 00:00:12,470
Kaj algoritmo revokon
Estas paŝo-de-paŝo aro

5
00:00:12,470 --> 00:00:15,260
de instrukcioj por kompletigado de tasko.

6
00:00:15,260 --> 00:00:17,580
>> En selektado ordigi la
baza ideo estas jena:

7
00:00:17,580 --> 00:00:22,080
trovi la plej malgranda elemento kaj unsorted
aldoni ĝin al la fino de la ordo listo.

8
00:00:22,080 --> 00:00:26,970
Efike kio ĉi faras estas muntaĵo
a ordo listo, unu elementon je fojo.

9
00:00:26,970 --> 00:00:29,800
Rompanta ĝin malsupren al _pseudocode_
ni povis konstati tiun algoritmon

10
00:00:29,800 --> 00:00:34,490
jene, ripeti ĉi ĝis
neniu unsorted elementoj restas.

11
00:00:34,490 --> 00:00:38,660
Serĉu tra la unsorted
datumoj por trovi la plej malgranda valoro,

12
00:00:38,660 --> 00:00:44,130
tiam interŝanĝi la plej malgranda valoro kun la
unua elemento de la unsorted parto.

13
00:00:44,130 --> 00:00:47,130
>> Eble helpos bildigi tion,
do ni rigardu tiun.

14
00:00:47,130 --> 00:00:49,710
Do ĉi, mi disputi, estas
unsorted tabelo kaj mi havas

15
00:00:49,710 --> 00:00:53,040
indikis ĝin indikante ke ĉiuj
de la elementoj estas koloritaj ruĝaj,

16
00:00:53,040 --> 00:00:54,420
Ili ankoraŭ ne ordigita.

17
00:00:54,420 --> 00:00:57,670
Tiu estas la tuta
unsorted parto de la tabelo.

18
00:00:57,670 --> 00:01:02,020
>> Do ni iru tra la paŝoj de
selektado speco ordigi ĉi tabelo.

19
00:01:02,020 --> 00:01:05,296
Do denove, ni estas gonna ripeto
ĝis neniu unsorted elementoj restas.

20
00:01:05,296 --> 00:01:07,920
Ni estas gonna serĉo tra la
datumoj por trovi la plej malgranda valoro,

21
00:01:07,920 --> 00:01:11,990
kaj tiam interŝanĝi tiun valoron kun la
unua elemento de la unsorted parto.

22
00:01:11,990 --> 00:01:14,380
>> Ĝuste nun, denove, la tuta
tabelo estas la unsorted parto.

23
00:01:14,380 --> 00:01:16,534
Ĉiuj de la ruĝaj elementoj estas unsorted.

24
00:01:16,534 --> 00:01:18,700
Do ni serĉu tra kaj
ni trovos la plej malgranda valoro.

25
00:01:18,700 --> 00:01:20,533
Ni starti je la komenco,
ni iru al la fino,

26
00:01:20,533 --> 00:01:23,630
ni trovos la plej malgranda valoro estas, unu.

27
00:01:23,630 --> 00:01:24,860
Do jen parto unu.

28
00:01:24,860 --> 00:01:29,440
Kaj poste parto du, interŝanĝu tiun valoron kun
la unua elemento de la unsorted parto,

29
00:01:29,440 --> 00:01:31,340
aŭ la unua ruĝa elemento.

30
00:01:31,340 --> 00:01:34,980
>> En ĉi tiu kazo kiu estus
kvin, do ni interŝanĝu unu kaj kvin.

31
00:01:34,980 --> 00:01:37,320
Kiam ni fari tion ĉi, ni povas
vide vidi ke ni

32
00:01:37,320 --> 00:01:41,260
kopiis la malgranda valora elemento
de la tabelo, por la tre komenco.

33
00:01:41,260 --> 00:01:43,920
Efike ordigado tiu elemento.

34
00:01:43,920 --> 00:01:47,520
>> Kaj tiel ni povas ja konfirmas
kaj stato ke oni, estas ordo.

35
00:01:47,520 --> 00:01:52,080
Kaj do ni indikos la ordo parto
de nia tabelo, per coloreando bluajn.

36
00:01:52,080 --> 00:01:53,860
>> Nun ni nur ripeti la procezon denove.

37
00:01:53,860 --> 00:01:57,430
Ni traserĉu la unsorted parto de
la tabelo por trovi la plej malgranda ero.

38
00:01:57,430 --> 00:01:59,000
En tiu kazo, ĝi estas du.

39
00:01:59,000 --> 00:02:02,100
>> Ni interŝanĝu ke kun la unua
elemento de la unsorted parto.

40
00:02:02,100 --> 00:02:05,540
En tiu kazo du ankaŭ hazarde estas
la unua elemento de la unsorted parto.

41
00:02:05,540 --> 00:02:08,650
Do ni interŝanĝu du kun sin,
kiuj vere nur lasas du

42
00:02:08,650 --> 00:02:11,257
kie estas, kaj ĝi estas ordo.

43
00:02:11,257 --> 00:02:13,840
Daŭrigante sur, ni serĉu pere
por trovi la plej malgranda ero.

44
00:02:13,840 --> 00:02:15,030
Estas tri.

45
00:02:15,030 --> 00:02:17,650
Ni interŝanĝu ĝin kun la unua
elemento, kiu estas kvin.

46
00:02:17,650 --> 00:02:19,450
Kaj nun tri estas ordo.

47
00:02:19,450 --> 00:02:22,440
>> Ni serĉu pere denove, kaj ni
trovi la plej malgranda elemento estas kvar.

48
00:02:22,440 --> 00:02:28,070
Ni interŝanĝu ĝin kun la unua elemento de la
unsorted parton, kaj nun kvar estas ordo.

49
00:02:28,070 --> 00:02:29,910
>> Ni trovas ke kvin estas
la plej malgranda ero.

50
00:02:29,910 --> 00:02:32,900
Ni interŝanĝu ĝin kun la unua
elemento de la unsorted parto.

51
00:02:32,900 --> 00:02:34,740
Kaj nun kvin estas ordo.

52
00:02:34,740 --> 00:02:36,660
>> Kaj poste persiste, nia
unsorted parto konsistas

53
00:02:36,660 --> 00:02:38,576
de nur unu elemento,
do ni serĉu pere

54
00:02:38,576 --> 00:02:41,740
kaj ni trovas ke ses estas la
malgranda, kaj fakte, nur elemento.

55
00:02:41,740 --> 00:02:44,906
Kaj tiam ni povas aserti ke ĝi estas ordo.

56
00:02:44,906 --> 00:02:47,530
Kaj nun ni ŝanĝis nia tabelo
de estanta tute unsorted

57
00:02:47,530 --> 00:02:52,660
en ruĝa, al tute ordigitaj
en blua, uzante selektado varon.

58
00:02:52,660 --> 00:02:54,920
>> Do kio estas la plej malbona kazo scenaron ĉi tie?

59
00:02:54,920 --> 00:02:57,830
Nu en la absoluta plej malbona
kazo, ni devas rigardi super

60
00:02:57,830 --> 00:03:02,170
ĉiuj de la elementoj de la tabelo
trovi la plej malgranda unsorted elemento,

61
00:03:02,170 --> 00:03:04,750
kaj ni devas ripeti
tiun procezon n fojojn.

62
00:03:04,750 --> 00:03:09,090
Unufoje por ĉiu elemento de la tabelo
ĉar ni nur, en ĉi tiu algoritmo,

63
00:03:09,090 --> 00:03:12,180
ia unu elementon je fojo.

64
00:03:12,180 --> 00:03:13,595
>> Kio estas la plej bona kazo scenaro?

65
00:03:13,595 --> 00:03:15,040
Nu ĝi estas precize la sama, ĉu ne?

66
00:03:15,040 --> 00:03:18,440
Ni fakte devos ankoraŭ paŝi tra
ĉiu unuopa elemento de la tabelo

67
00:03:18,440 --> 00:03:22,040
por konfirmi, ke ĝi estas,
fakte, la plej malgranda ero.

68
00:03:22,040 --> 00:03:26,760
>> Do la plej malbona kazo tempo de ekzekuto, ni
devi ripeti procezon n fojojn,

69
00:03:26,760 --> 00:03:28,960
unufoje por ĉiu el n elementoj.

70
00:03:28,960 --> 00:03:31,940
Kaj en la plej bona kazo scenaro,
ni devas fari la saman.

71
00:03:31,940 --> 00:03:35,340
>> Do pensante reen al nia
komputa komplekseca toolbox,

72
00:03:35,340 --> 00:03:39,250
kion vi pensas estas la plej malbona
kazo tempo de ekzekuto por selektado speco?

73
00:03:39,250 --> 00:03:41,840
Kion vi pensas estas la plej bona
kazo tempo de ekzekuto por selektado speco?

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

75
00:03:44,760 --> 00:03:49,325
>> Ĉu vi divenas Big O de n kvadratoj,
kaj Big Omega de n kvadratoj?

76
00:03:49,325 --> 00:03:49,950
Vi estus prava.

77
00:03:49,950 --> 00:03:52,490
Tiuj estas, fakte, la
plej malbona kazo kaj bona kazo run

78
00:03:52,490 --> 00:03:55,100
tempoj, por selektado speco.

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

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

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