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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Beraz CS50 buruz ikasi dugu
sailkatzeko eta bilaketak barietate

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

4
00:00:09,442 --> 00:00:11,400
Eta batzuetan izan daiteke
apur bat delikatua mantentzeko

5
00:00:11,400 --> 00:00:14,161
zer algoritmo jarraipena egiten duenari.

6
00:00:14,161 --> 00:00:15,910
Benetan besterik ez dugu
azalera gaingabetuak gehiegi,

7
00:00:15,910 --> 00:00:18,740
Han, beste hainbat irizpide horiek dira
eta algoritmoen arabera ordenatzeko.

8
00:00:18,740 --> 00:00:21,780
Beraz, bideo honetan goazen
besterik minutu batzuk hartu

9
00:00:21,780 --> 00:00:24,980
saiatu eta destila algoritmoa bakoitzeko
bere core elements behera

10
00:00:24,980 --> 00:00:27,810
beraz, gehien gogoratzen duzu
haiei buruzko informazio garrantzitsua

11
00:00:27,810 --> 00:00:31,970
eta izan artikulatzeko gai
desberdintasunak, beharrezkoa izanez gero.

12
00:00:31,970 --> 00:00:34,220
>> Lehena hautaketa ordenatu.

13
00:00:34,220 --> 00:00:38,210
Oinarrizko ideia hautaketa ordena atzean
Unsorted elementu txikiena aurkitu da

14
00:00:38,210 --> 00:00:42,890
sorta bat eta trukatu egiten dituzten
Array horretan lehenengo elementua Sailkatu.

15
00:00:42,890 --> 00:00:46,620
Esan dugu kasurik txarrenaren dagoela
n karratu zela garai exekutatu.

16
00:00:46,620 --> 00:00:50,060
Eta gogoratzen zergatik nahi baduzu, hartu
a hautaketa ordena bideoa begiratzeko.

17
00:00:50,060 --> 00:00:54,560
Best-kasuan run garai
halaber karratu n.

18
00:00:54,560 --> 00:00:58,910
>> Burbuila ordenatu, horren atzean ideia
da ondoko bikote trukatzeko.

19
00:00:58,910 --> 00:01:01,730
Beraz, hori gakoa laguntzen duen da
Gogoratzen aldea hemen.

20
00:01:01,730 --> 00:01:04,920
Aukeraketa ordenatu, hau da, orain arte,
the smallest-- burbuila aurkitu

21
00:01:04,920 --> 00:01:06,790
moduko da trukatu ondoko bikoteak.

22
00:01:06,790 --> 00:01:08,710
Ondoko bikote trukatu dugu
elementuen badute

23
00:01:08,710 --> 00:01:12,530
ordenatik kanpo daude, eta eraginkortasunez
eskubidea elementu handiagoak burbuila,

24
00:01:12,530 --> 00:01:17,060
eta, aldi berean hasten da, gainera,
ezkerreko elementu txikiagoak mugitzeko.

25
00:01:17,060 --> 00:01:20,180
Kasurik txarrenaren kasuan run garai
burbuila sort karratu n.

26
00:01:20,180 --> 00:01:23,476
Best-kasuan run garai
burbuila moduko da n.

27
00:01:23,476 --> 00:01:25,350
Zeren eta egoera horretan
ez dugu, egia esan,

28
00:01:25,350 --> 00:01:27,141
Agian ez dugu behar
trukeak edozein egiteko guztietan.

29
00:01:27,141 --> 00:01:31,026
Bat egiteko besterik ez dugu
n elementu guztietan zehar pasatzen.

30
00:01:31,026 --> 00:01:34,600
>> Txertatzeko ordenatu batean,
Oinarrizko ideia hemen aldatzearen da.

31
00:01:34,600 --> 00:01:36,630
Txertatzeko ordenatu for keyword da.

32
00:01:36,630 --> 00:01:39,630
Behin urratsera bidez goaz
array ezkerretik eskuinera.

33
00:01:39,630 --> 00:01:41,670
Eta egin dugun bezala, ez gara
elementu filmea joan

34
00:01:41,670 --> 00:01:46,260
Dagoeneko ikusi dugu gelan egiteko
nonbait egokitzeko behar txikiago

35
00:01:46,260 --> 00:01:48,080
ordenatuko zati horretan atzera.

36
00:01:48,080 --> 00:01:51,600
Beraz ordenatzen array eraikitzen dugu bat
aldi berean elementu, ezkerretik eskuinera,

37
00:01:51,600 --> 00:01:54,740
eta gauza gela egiteko filmea dugu.

38
00:01:54,740 --> 00:01:58,650
Kasurik txarrenaren run garai
txertatzeko ordenatu karratu n.

39
00:01:58,650 --> 00:02:02,380
Best-kasuan exekutatu ordua ez da n.

40
00:02:02,380 --> 00:02:05,380
>> Bateratu hitzarekin orain arte bezala
Hemen zatitu eta batzea.

41
00:02:05,380 --> 00:02:08,949
Array osoa zatitu dugu, ala
Sei elementu, zortzi elementu da,

42
00:02:08,949 --> 00:02:13,790
10.000 elementuen zatitu dugu
behera erdia, erdia, erdia,

43
00:02:13,790 --> 00:02:17,720
array azpian daukagun arte
elementu arrayak n bat.

44
00:02:17,720 --> 00:02:19,470
Elementu arrayak n inork multzoa.

45
00:02:19,470 --> 00:02:22,640
Beraz, hasi batez dugu
1.000-elementu array,

46
00:02:22,640 --> 00:02:26,550
eta harira dugu non gauden
1.000 bat-elementu array izan.

47
00:02:26,550 --> 00:02:30,990
Ondoren sub arrayak horiek batzea hasiko dugu
itzuli batera zuzena izateko.

48
00:02:30,990 --> 00:02:34,860
Beraz, bi bat-elementu arrayak hartuko dugu
eta bi elementu array bat sortzeko.

49
00:02:34,860 --> 00:02:38,180
Bi bi elementu arrayak hartu dugu
eta lau elementu sorta bat sortu

50
00:02:38,180 --> 00:02:43,900
eta abar eta abar izan ditugu arte
Berriro n elementu array bat berreraiki.

51
00:02:43,900 --> 00:02:48,410
>> Kasurik txarrenaren run garai
Batu sort-n aldiz log n.

52
00:02:48,410 --> 00:02:52,390
N elementu ditugu, baina
gurutzagarria prozesu honetan

53
00:02:52,390 --> 00:02:56,960
hartzen log n urratsak iristeko
multzo osoa bat itzuli.

54
00:02:56,960 --> 00:03:01,160
Halaber, denbora exekutatu Kasu onena da n log
n Prozesu honek ez du benetan delako

55
00:03:01,160 --> 00:03:04,090
Laguntza array ote zen
ordenatuko edo ez hasteko.

56
00:03:04,090 --> 00:03:07,590
Prozesua bera da, ez dago
Zirkuitu gauzak labur modurik.

57
00:03:07,590 --> 00:03:11,610
Beraz, n log txarrena kasuan n,
n log onena kasuan n.

58
00:03:11,610 --> 00:03:13,960
>> Hitz egin dugu bi buruz
algoritmoak bilatzen.

59
00:03:13,960 --> 00:03:16,230
Beraz, bilaketa lineala errepikatzean ingurukoa da.

60
00:03:16,230 --> 00:03:19,500
Jarraitu dugu array zehar
behin, ezkerretik eskuinera,

61
00:03:19,500 --> 00:03:21,950
zenbakia aurkitu nahian
ari garela bila.

62
00:03:21,950 --> 00:03:24,550
Kasurik txarrenaren exekutatu denboraren n O big da.

63
00:03:24,550 --> 00:03:27,610
Baliteke gurekin eraman errepikatzean
elementu bakar guztietan zehar

64
00:03:27,610 --> 00:03:30,660
elementua begira ari gara aurkitu
Ba, bai, azken postuan kokatu,

65
00:03:30,660 --> 00:03:31,630
edo ez guztietan.

66
00:03:31,630 --> 00:03:34,720
Baina ezin dugu baieztatu duten arte
Guztia begiratu dugu.

67
00:03:34,720 --> 00:03:36,730
M-kasuan onena, berehala aurkituko dugu.

68
00:03:36,730 --> 00:03:41,060
Best-kasuan run garai
Bilaketa lineala 1 omega da.

69
00:03:41,060 --> 00:03:43,689
>> Azkenik, ez zen bilaketa bitarra,
bertan askotariko array eskatzen du.

70
00:03:43,689 --> 00:03:45,605
Gogoratu hori oso bat
consideración garrantzitsua

71
00:03:45,605 --> 00:03:47,155
bilaketa bitarra lan egiten denean.

72
00:03:47,155 --> 00:03:50,180
Aurrebaldintza bat da it erabiliz It
horren baitan bilatzen ari zaren array

73
00:03:50,180 --> 00:03:52,160
banatu behar dira.

74
00:03:52,160 --> 00:03:54,500
Bestela, hitzarekin
Banatu eta agindu da.

75
00:03:54,500 --> 00:03:58,310
Zatitu array erdia sartu eta
elementuak erdia kentzeko

76
00:03:58,310 --> 00:04:00,780
aldi bakoitzean jarraitu bitartez.

77
00:04:00,780 --> 00:04:04,330
Honegatik arraila hau eta konkistatzeko
eta splitting hurbilketa zatian gauzak,

78
00:04:04,330 --> 00:04:07,450
kasurik txarrenaren run ordua
bilaketa bitarra da

79
00:04:07,450 --> 00:04:11,730
log n, hau da, nabarmen
Bilaketa-en lineala n baino hobea.

80
00:04:11,730 --> 00:04:13,570
Best-kasuan exekutatu ordua ez da oraindik.

81
00:04:13,570 --> 00:04:17,010
>> Baliteke berehala aurkituko dugu
Lehen aldiz zatiketa bat egin dugu, baina,

82
00:04:17,010 --> 00:04:19,339
Berriro, gogoratu
nahiz bitar bilaketa

83
00:04:19,339 --> 00:04:24,030
funtsean bilaketa lineala baino hobea
log izatearen arabera n versus n,

84
00:04:24,030 --> 00:04:27,110
den lanaren bidez joan behar duzu agian
sailkatuz, zure array lehen, zein

85
00:04:27,110 --> 00:04:32,010
hain eraginkorra da arabera egin liteke
ordenatuko errepikatzean tamaina gainean.

86
00:04:32,010 --> 00:04:35,250
>> Naiz Doug Lloyd, hau CS50 da.

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