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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Do en CS50 ni lernis pri
vario de ordigado kaj serĉado

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

4
00:00:09,442 --> 00:00:11,400
Kaj kelkfoje ĝi povas esti
iom malfacila teni

5
00:00:11,400 --> 00:00:14,161
trako de kio algoritmo faras kion.

6
00:00:14,161 --> 00:00:15,910
Ni vere nur
senkremigita la surfaco tro,

7
00:00:15,910 --> 00:00:18,740
ekzistas multaj aliaj traserĉado
kaj ordigado algoritmoj.

8
00:00:18,740 --> 00:00:21,780
Do en ĉi tiu video ni
nur preni kelkajn minutojn

9
00:00:21,780 --> 00:00:24,980
provi kaj distili ĉiu algoritmo
malsupren al sia kerno elementoj

10
00:00:24,980 --> 00:00:27,810
do vi povas memori la plej
grava informo pri ili

11
00:00:27,810 --> 00:00:31,970
kaj povos artiki la
diferencoj, se necese.

12
00:00:31,970 --> 00:00:34,220
>> La unua estas selektado varon.

13
00:00:34,220 --> 00:00:38,210
La baza ideo malantaŭ selektado speco
estas trovi la plej malgrandan elementon unsorted

14
00:00:38,210 --> 00:00:42,890
en tabelo kaj interŝanĝi ĝin kun la
unua unsorted elemento de tiu tabelo.

15
00:00:42,890 --> 00:00:46,620
Ni diris ke la plej malbona-kazo
kuri tempo de kiu n kvadratoj.

16
00:00:46,620 --> 00:00:50,060
Kaj se vi volas memori kial, prenu
Rigardu la selektado speco vídeo.

17
00:00:50,060 --> 00:00:54,560
La plej kazo tempo de ekzekuto
ankaŭ n kvadratoj.

18
00:00:54,560 --> 00:00:58,910
>> Bobelo varo, la ideo malantaŭ tiu
unu estas interŝanĝi apudajn parojn.

19
00:00:58,910 --> 00:01:01,730
Do jen la ŝlosilo kiu helpas vin
memori la diferenco ĉi tie.

20
00:01:01,730 --> 00:01:04,920
Selektado varo estas, ĝis nun,
trovi la smallest-- bobelo

21
00:01:04,920 --> 00:01:06,790
varo interŝanĝi apudajn parojn.

22
00:01:06,790 --> 00:01:08,710
Ni interŝanĝu najbaraj paroj
de elementoj se ili

23
00:01:08,710 --> 00:01:12,530
estas el ordo, kiu efike
bobelas grandaj elementoj dekstren,

24
00:01:12,530 --> 00:01:17,060
kaj samtempe ĝi ankaŭ komencas
moviĝi malgrandaj elementoj maldekstren.

25
00:01:17,060 --> 00:01:20,180
La plej malbona-kazo kazo tempo de ekzekuto
de bobelo varo estas n kvadratoj.

26
00:01:20,180 --> 00:01:23,476
La plej kazo tempo de ekzekuto
de bobelo varo estas n.

27
00:01:23,476 --> 00:01:25,350
Ĉar en tiu situacio
ni ne actually--

28
00:01:25,350 --> 00:01:27,141
ni ne bezonas
fari ajnan svopoj ajn.

29
00:01:27,141 --> 00:01:31,026
Ni nur devas fari unu
pasas tra ĉiuj n elementoj.

30
00:01:31,026 --> 00:01:34,600
>> En inserción varon, la
baza ideo tie estas movanta.

31
00:01:34,600 --> 00:01:36,630
Tio estas la ŝlosilvorto por inserción varon.

32
00:01:36,630 --> 00:01:39,630
Ni tuj paŝi iam tra
la tabelo de maldekstre al dekstre.

33
00:01:39,630 --> 00:01:41,670
Kaj kiel ni faras, ni estas
tuj movi elementojn

34
00:01:41,670 --> 00:01:46,260
Ni jam vidis por fari lokon por
malgrandaj ke bezonas persvadi ie

35
00:01:46,260 --> 00:01:48,080
reen en tiu ordo parton.

36
00:01:48,080 --> 00:01:51,600
Do ni konstruas la ordo tabelo unu
elementon je fojo, maldekstre dekstren,

37
00:01:51,600 --> 00:01:54,740
kaj ni ŝanĝi aferojn por fari lokon.

38
00:01:54,740 --> 00:01:58,650
La plej malbona-kazo tempo de ekzekuto de
inserción varo estas n kvadratoj.

39
00:01:58,650 --> 00:02:02,380
La plej kazo tempo de ekzekuto estas n.

40
00:02:02,380 --> 00:02:05,380
>> Kunfandi sort-- la ŝlosilvorto
tie estas fendita kaj kunfandi.

41
00:02:05,380 --> 00:02:08,949
Ni disiĝis la plena tabelo, ĉu
ĝi estas ses elementoj, ok elementojn,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- ni fendi ĝin
malsupren por la duono, de la duono, de la duono,

43
00:02:13,790 --> 00:02:17,720
ĝis ni havas sub tabelo
de n unu elemento tabeloj.

44
00:02:17,720 --> 00:02:19,470
Aro de n unu elemento tabeloj.

45
00:02:19,470 --> 00:02:22,640
Do ni komencis kun unu
1.000-era tabelo,

46
00:02:22,640 --> 00:02:26,550
kaj ni atingos la punkto kie ni
havas 1,000 unu-era tabeloj.

47
00:02:26,550 --> 00:02:30,990
Tiam ni komencas kunfandi tiuj sub tabeloj
reen kune en la ĝusta ordo.

48
00:02:30,990 --> 00:02:34,860
Do ni prenu du unu-era tabeloj
kaj krei du-era tabelo.

49
00:02:34,860 --> 00:02:38,180
Ni prenu du du-eraj aroj
kaj krei kvar-era tabelo

50
00:02:38,180 --> 00:02:43,900
kaj tiel plu kaj tiel plu ĝis ni havas
denove rekonstruis unu n elemento tabelo.

51
00:02:43,900 --> 00:02:48,410
>> La plej malbona-kazo tempo de ekzekuto de
kunfandi varo estas n fojoj logo n.

52
00:02:48,410 --> 00:02:52,390
Ni havas n erojn, sed
ĉi rekombini procezo

53
00:02:52,390 --> 00:02:56,960
prenas log n paŝoj akiri
malantaŭo al plena tabelo.

54
00:02:56,960 --> 00:03:01,160
La plej bona kazo kuri tempo estas ankaŭ n log
n ĉar tiu procezo ne vere

55
00:03:01,160 --> 00:03:04,090
gravis ĉu la tabelo estis
ordo aŭ ne komence.

56
00:03:04,090 --> 00:03:07,590
La procezo estas la sama, estas
neniu vojo fuŝkontakto aferojn.

57
00:03:07,590 --> 00:03:11,610
Do n log n en la plej malbona kazo,
n log n en la plej bona kazo.

58
00:03:11,610 --> 00:03:13,960
>> Ni parolis pri du
serĉanta algoritmoj.

59
00:03:13,960 --> 00:03:16,230
Do lineara serĉo estas pri ripetanta.

60
00:03:16,230 --> 00:03:19,500
Ni procedi trans la tabelo
unufoje, de maldekstra al dekstra,

61
00:03:19,500 --> 00:03:21,950
provante trovi la nombron
ke ni serĉas.

62
00:03:21,950 --> 00:03:24,550
La plej malbona-kazo tempo de ekzekuto estas granda a de n.

63
00:03:24,550 --> 00:03:27,610
Ĝi povus preni nin ripetanta
trans ĉiu unuopa elemento

64
00:03:27,610 --> 00:03:30,660
trovi la elemento ni serĉas
por, ĉu en la lasta pozicio,

65
00:03:30,660 --> 00:03:31,630
aŭ tute ne.

66
00:03:31,630 --> 00:03:34,720
Sed ni ne povas konfirmi ke ĝis
ni rigardis ĉion.

67
00:03:34,720 --> 00:03:36,730
m la plej kazo, ni trovas tuj.

68
00:03:36,730 --> 00:03:41,060
La plej kazo tempo de ekzekuto de
lineara serĉo estas omega de 1.

69
00:03:41,060 --> 00:03:43,689
>> Finfine, ekzistis duuma serĉo,
kiu postulas diversspeca tabelo.

70
00:03:43,689 --> 00:03:45,605
Memoru ke estas tre
grava konsidero

71
00:03:45,605 --> 00:03:47,155
kiam laborante kun duuma serĉo.

72
00:03:47,155 --> 00:03:50,180
Ĝi estas antaŭkondiĉo por uzanta it--
la tabelo kiun vi serĉas tra

73
00:03:50,180 --> 00:03:52,160
devas esti ordo.

74
00:03:52,160 --> 00:03:54,500
Alie, la ŝlosilvorto
estas dividi kaj venki.

75
00:03:54,500 --> 00:03:58,310
Fendi la tabelo en duono kaj
forigi duonon de la elementoj

76
00:03:58,310 --> 00:04:00,780
ĉiufoje kiam vi procedi tra.

77
00:04:00,780 --> 00:04:04,330
Pro tiu dividu kaj regu
kaj forkiĝanta aferoj en duono alproksimiĝo,

78
00:04:04,330 --> 00:04:07,450
la plej malbona-kazo tempo de ekzekuto
de duuma serĉo estas

79
00:04:07,450 --> 00:04:11,730
logo n, kiu estas substance
bona ol lineara serĉo de n.

80
00:04:11,730 --> 00:04:13,570
La plej kazo kuri horo estas ankoraŭ unu.

81
00:04:13,570 --> 00:04:17,010
>> Ni povus trovi ĝin tuj la
unuafoje ni faras dividon, sed,

82
00:04:17,010 --> 00:04:19,339
denove, memoru ke
kvankam duuma serĉo estas

83
00:04:19,339 --> 00:04:24,030
substance bona ol lineara serĉo
pro esti log n kontre n,

84
00:04:24,030 --> 00:04:27,110
vi eble devas iri tra la verkon
de ordiga via tabelo unuaj, kiuj

85
00:04:27,110 --> 00:04:32,010
povus fari ĝin malpli efika depende
sur la grandeco de la ripetanta ordo.

86
00:04:32,010 --> 00:04:35,250
>> Mi Doug Lloyd, tiu estas CS50.

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