[Powered by Google Translate] Vi verŝajne aŭdis homojn paroli pri rapida aŭ kompetenta algoritmo
por ekzekuti vian apartan taskon,
sed kion ekzakte signifas por algoritmo por esti rapida aŭ efika?
Nu, ĝi ne parolas pri mezurado en reala tempo,
kiel duaj aŭ minutoj.
Ĉi tiu estas ĉar komputilaj aparataro
kaj programaro varias draste.
Mia programo povus kuri pli malrapida ol via,
ĉar mi kurante ĝin sur malnovan komputilon,
aŭ ĉar mi hazarde esti ludante interreta videoludo
samtempe, kiu prenu al vi la tutan mia memoro,
aŭ mi povus kuri mia programo por malsamaj programaro
kiu komunikas kun la maŝino malsame je malalta nivelo.
Estas kiel kompari pomojn kaj oranĝoj.
Nur ĉar mia malrapida komputilo prenas plu
ol la viaj redoni respondon
ne signifas ke ili havas la pli kompetenta algoritmo.
>> Do, cxar ne eblas rekte komparas la runtimes de programoj
en duaj aŭ minutoj,
kiel ni komparu 2 malsamaj algoritmoj
sendepende de ilia aparataro aŭ programaro medio?
Krei pli unuforma maniero de mezuri algoritma efikeco,
komputilo sciencistoj kaj matematikistoj elpensis
konceptoj por mezuri la asimptota komplekseco de programo
kaj skribmaniero nomata 'Big Ohnotation'
por priskribi ĉi.
La formala difino estas tiu funkcio f (x)
funkcias en la ordo de g (x)
se tie ekzistas iu (x) valoro, x ₀ kaj
iu konstanto, C, por kiu
f (x) estas malpli ol aŭ egala al
ke konstantan fojoj g (x)
por ĉiuj x pli granda ol x ₀.
>> Sed ne havi timon for de la formala difino.
Kion tio vere signifas en malpli teoriaj terminoj?
Nu, estas esence formo de analizi
kiel rapide programon de ekzekuto kreskas asimptote.
Tio estas, al la grandeco de via enigoj pliigas al malfinio,
diru vi ordigi tabelo de amplekso 1000 kompare kun tabelo de amplekso 10.
Kiel la runtime de via programo kreski?
Ekzemple, imagu rakonti la nombro da karakteroj
en linio la plej simpla maniero
marŝante tra la tuta ĉeno
letero-de-leteron kaj aldonante 1 al nombrilo por ĉiu signo.
Ĉi tiu algoritmo estas dirita por kuri en lineara tempo
rilate al la nombro da karakteroj,
'N' en la kordo.
Unuvorte, ĝi kuras en O (n).
Kial tio estas?
Nu, uzante tiun koncepton, la tempo bezonata
tra la tuta ĉeno
estas proporcia al la nombro de signoj.
Rakontante la nombro da karakteroj en 20-karaktero ŝnuroj
tuj prenos duoble longe kiel ĝi prenas
por rakonti la gravuloj en 10-karaktero ŝnuroj,
ĉar vi devas rigardi ĉiujn karakterojn
kaj ĉiu karaktero portas la saman kvanton de tempo por rigardi.
Kiel vi pliigos la nombron de karakteroj,
la runtime pliigos lineare kun la eniro longa.
>> Nun, imagu se vi decidas ke lineara tempo,
O (n), simple ne estis sufiĉe rapide por vi?
Eble vi stoki grandan kordoj,
kaj vi ne povas pagi la ekstra tempo necesus
tra ĉiuj liaj karakteroj rakonti unu-por-unu.
Do, vi decidas provi ion malsaman.
Kio se okazus al la jam konservi nombron de karakteroj
en la ĉeno, ni diru, en variablo nomita 'len:
frue en la programo,
antaŭ vi eĉ stoki la unua gravulo en via ĉeno?
Tiam, ĉiuj vi devus fari nun por eltrovi la kordo longo,
estas kontroli kion la valoro de la variablo estas.
Vi ne devus rigardi la kordo mem tute ne,
kaj aliru la valoro de variablo kiel len konsideras
an asimptote konstanta tempo operacio,
aŭ O (1).
Kial tio estas? Nu, memoru kion asimptota komplekseco signifas.
Kiel funkcias la runtime ŝanĝon kiel la grandeco
de via enigoj kreskas?
>> Diru vi volis ricevi la nombro da karakteroj en pli grandan ĉenon.
Nu, ne gravas kiom granda vi fari la ĉeno,
eĉ miliono signojn longa,
ĉiuj vi devus fari, por trovi la kordoj de longa kun ĉi alproksimiĝo,
estas legi ekster la valoro de la variablo len,
kion vi jam faris.
La eniro longo, tio estas, la longo de la kordo vi provas trovi,
ne afekti tute kiel rapide via programo kuras.
Ĉi tiu parto de via programo kurus egale rapide en unu-karaktero ŝnuroj
kaj mil-karaktero ŝnuroj,
kaj tial tiu programo devus esti referita al kiel kurante en konstanta tempo
kun respekto al la eniro grandeco.
>> Kompreneble, ekzistas malavantaĝo.
Vi elspezos ekstra memoro spaco sur via komputilo
stoki la variablo
kaj la ekstra tempo prenas vin
fari la efektiva stokado de la variablo,
sed la punkto ankoraŭ staras,
eltrovi kiom longe viajn kordoj estis
ne dependas de la longo de la kordo ajn.
Do, ĝi kuras en O (1) aŭ konstanta tempo.
Tiu certe ne devas signifi
ke via kodo kuras en 1 paŝo,
sed ne gravas kiom da paŝoj estas,
se ĝi ne ŝanĝi kun la grandeco de la enigoj,
ĝi estas ankoraŭ asimptote konstanta kiu ni reprezentas kiel O (1).
>> Kiel vi povas verŝajne diveni,
ekzistas multaj malsamaj granda a runtimes mezuri algoritmoj kun.
O (n) ² algoritmoj estas asimptote pli malrapida ol O (n) algoritmoj.
Tio estas, kiel la nombro de elementoj (n) kreskas,
eventuale O (n) ² algoritmoj prenos pli da tempo
ol O (n) algoritmoj por kuri.
Tio ne signifas, O (n) algoritmoj ĉiam kuras pli rapide
ol O (n) ² algoritmoj, eĉ en la sama medio,
en la sama aparataro.
Eble por malgrandaj enigo grandecoj,
la O (n) ² algoritmo povus reale labori rapide,
sed, eventuale, kiel la enigo grandeco pliigas
al malfinio, la O (n) ² algoritmo de ekzekuto
eventuale eclipsar la runtime de la O (n) algoritmo.
Same kiel iu kvadrata matematika funkcio
eventuale atingos ajnan lineara funkcio,
kiom ajn en kapo komenci la lineara funkcio dividu kun.
Se vi laboras kun grandaj kvantoj de datumoj,
algoritmoj kiuj kuras en O (n) ² tempo povas vere fini ralentizando vian programon,
sed por malgranda enigo grandecoj,
vi probable eĉ ne rimarkos.
>> Alia asimptota komplekseco estas,
logaritma tempo, O (log n).
Ekzemplo de algoritmo kiu kuras ĉi rapide
estas la klasika duuma serĉo algoritmo,
por trovi elementon en jam-ordo listo de eroj.
>> Se vi ne scias, kion duuma serĉo faras,
Mi klarigas ĝin por vi vere rapide.
Diru vi serĉas la numero 3
en ĉi tiu tabelo de entjeroj.
Ĝi rigardas la mezo ero de la tabelo
kaj demando: "Ĉu la elemento Mi volas pli granda ol, egala al, aŭ malpli ol tio?"
Se estas egalaj, tiam granda. Vi trovis la elementon, kaj vi faris.
Se estas pli granda, tiam vi scias la elemento
devas esti en la dekstra flanko de la tabelo,
kaj vi nur povas rigardi, ke en la estonteco,
kaj se ĝi estas pli malgranda, tiam vi scias ke ĝi devas esti en la maldekstra flanko.
Ĉi tiu procezo estas tiam ripetis kun la plej malgranda-grandeco tabelo
ĝis la korekta elemento estas trovita.
>> Tiu potenca algoritmo tranĉas la tabelo grandeco en duono kun ĉiu operacio.
Do, por trovi elementon en ordo tabelo de amplekso 8,
maksimume (log ₂ 8),
aŭ 3 el tiuj operacioj,
kontrolanta la mezo elemento, tiam tranĉi la tabelo en duono estos bezonata,
dum tabelo de amplekso 16 prenas (log ₂ 16),
aŭ 4 operacioj.
Tio estas nur 1 pli operacio por duobliĝis-grandeco tabelo.
Duobligante la grandeco de la tabelo
pliigas la runtime de nur 1 pecon de ĉi tiu kodo.
Denove, kontrolanta la mezo ero de la listo, tiam forkiĝanta.
Do, ĝi estas dirita al operacii en logaritma tempo,
O (log n).
Sed atendu, vi diras,
Ne ĉi dependas kie en la listo la elemento vi serĉas estas?
Kio se la unua elemento vi rigardas hazarde estas la ĝuste?
Tiam, ĝi nur prenas 1 operacio,
kiel ajn granda la listo estas.
>> Nu, jen kial komputilo sciencistoj havas pli terminoj
por asimptota komplekseco kiu reflektas la plej kazo
kaj plej malbona-kazo agadoj de algoritmo.
Pli ĝuste, la supra kaj subaj baroj
en la tempo de ekzekuto.
En la plej bona kazo por duuma serĉo, nia ero estas
Dekstre en la mezo,
kaj vi akiris ĝin en konstanta tempo,
kiel ajn granda la resto de la tabelo estas.
La simbolo uzita por tiu ĉi estas Ω.
Do, ĉi tiu algoritmo estas dirita al kuri en Ω (1).
En la plej bona kazo, ĝi trovas la elemento rapide,
kiel ajn granda la tabelo estas,
sed en la plej malbona kazo,
ĝi devas plenumi (log n) divido ĉekojn
de la tabelo por trovi la dekstra elemento.
Plej malbona-kazo superaj baroj estas raportita kun la granda "O", kiun vi jam konas.
Do, ĝi estas O (log n), sed Ω (1).
>> Lineara serĉo, per kontrasto,
en kiuj vi trairu ĉiu ero de la tabelo
trovi kiun vi volas,
Estas en la plej bona Ω (1).
Denove, la unua elemento vi volas.
Do, ne gravas kiom granda la tabelo estas.
En la plej malbona kazo, ĝi estas la lasta elemento en la tabelo.
Do, vi devas marŝi tra ĉiuj n elementoj en la tabelo por trovi ĝin,
kiel se vi serĉis 3.
Do, ĝi kuras en O (n) tempo
ĉar ĝi estas proporcia al la nombro de eroj en la tabelo.
>> Unu pli simbolo uzita estas Θ.
Ĉi tiu povas esti uzita por priskribi algoritmojn, kie la plej bona kaj plej malbonaj kazoj
estas samaj.
Tiu estas la kazo en la kordo-longo algoritmoj ni parolis pri pli frua.
Tio estas, se ni konservas ĝin en variablo antaux
ni stoki la kordo kaj konsenti ĝin poste en konstanta tempo.
Ne gravas kion nombro
ni stokante en tiu variablo, ni devos rigardi ĝin.
La plej bona okazo estas, ni rigardu ĝin
kaj trovi la longo de la kordo.
Do Ω (1) aŭ pli kazo konstanta tempo.
La plej malbona kazo estas,
ni rigardas ĝin kaj trovi la longeco de la kordo.
Do, O (1) aŭ konstanta tempo en plej malbona kazo.
Do, ekde la plej bona kazo kaj plej malbonaj kazoj estas la sama,
tiu povas diri kuri en Θ (1) tempo.
>> Resume, ni havas bonajn manierojn kialo pri kodoj efikeco
sen scii ion pri la reala mondo tempo prenas kuri,
kio estas influata de multaj ekster faktoroj,
inkludante diferencanta aparataro, programaro,
aŭ la specifaj detaloj de via kodo.
Ankaŭ, ĝi permesas al ni elpensus bone pri kio okazos
kiam la grandeco de la enigoj pliigas.
>> Se vi kuras en O (n) ² algoritmo,
aŭ malbona, oni ho (2 ⁿ) algoritmo,
unu el la plej rapide kreskanta tipoj,
vi vere komencas rimarki la malrapidiĝo
kiam vi komencos labori kun grandaj kvantoj de datumoj.
>> Tio estas asimptota komplekseco. Dankon.