[Powered by Google Translate] Ju ndoshta keni dëgjuar njerëzit flasin rreth një algoritmi të shpejtë apo të efektshme
për ekzekutimin detyrën tuaj të veçantë,
Por çfarë saktësisht do të thotë kjo për një algoritmi të jetë i shpejtë apo të efektshme?
E pra, kjo nuk është duke folur për një matje në kohë reale,
si sekonda ose minuta.
Kjo është për shkak hardware kompjuteri
dhe software të ndryshojnë në mënyrë drastike.
Programi im mund të kandidojë ngadalshëm se sa tuajat,
sepse unë jam running atë në një kompjuter të vjetër,
ose sepse Unë të ndodhë për të luajtur një lojë online video
në të njëjtën kohë, e cila është e hogging gjitha memorie time,
ose unë mund të konkurrojnë programin tim nëpërmjet programeve të ndryshme
e cila komunikon me makinë ndryshe në një nivel të ulët.
Është si krahasuar mollë dhe portokall.
Vetëm për shkak se kompjuteri im merr më e ngadalshme
se juaja për t'i kthyer një përgjigje
nuk do të thotë që ju keni algorithm më efikas.
>> Pra, pasi ne nuk mund të drejtpërdrejt të krahasojnë runtimes e programeve
në sekonda ose minuta,
si nuk kemi krahasojnë 2 algoritme të ndryshme
pavarësisht nga hardware e tyre apo mjedisi software?
Për të krijuar një mënyrë më uniforme për të matur efikasitetin algorithmic,
shkencëtarët kompjuterike dhe matematicienë kanë shpikur
Konceptet për matjen kompleksitetin asymptotic e një programi
dhe një simbol i quajtur 'Ohnotation Big'
për përshkrimin këtë.
Përkufizimi formal është se një funksioni f (x)
shkon në mënyrë të g (x)
nëse ekziston ndonjë vlerë (x), x ₀ dhe
disa konstante, C, për të cilat
f (x) është më pak se ose e barabartë me
që herë konstante g (x)
për të gjitha x madhe se x ₀.
>> Por nuk do të jetë i frikësuar larg nga përkufizimi formal.
Çfarë e bën këtë të vërtetë do të thotë më pak në aspektin teorik?
E pra, kjo është në thelb një mënyrë për të analizuar
sa shpejt Runtime të një programi rritet asymptotically.
Kjo është, si madhësia e inputeve tuaj rritet drejt pafundësi,
Thuaj, ju jeni zgjidhja një rrjet të madhësisë 1000 në krahasim me një grup të madhësisë 10.
Si e runtime e programit tuaj të rriten?
Për shembull, imagjinoni numëruar numrin e karaktereve
në një varg Mënyra më e thjeshtë
duke ecur nëpër varg të tërë
letër-nga-letër dhe duke shtuar 1 në një sportel për çdo karakter.
Ky algoritëm është thënë për të kandiduar në kohë lineare
në lidhje me numrin e karaktereve,
'N' në vargun.
Me pak fjalë, ajo shkon në O (n).
Pse është kjo?
E pra, duke përdorur këtë qasje, koha e nevojshme
të kaloj nëpër të gjithë tekstin
është proporcionale me numrin e karaktereve.
Numëruar numrin e karaktereve në një varg 20-karakter
do të marrë dy herë për aq kohë sa ajo merr
për të numëruar personazhet në një varg 10-karakter,
sepse ju duhet të shikoni në të gjitha personazhet
dhe çdo karakter merr të njëjtën sasi e kohës për të parë në.
Si ju rritet numri i karaktereve,
runtime e do të rritet linearisht me gjatësi input.
>> Tani, imagjinoni nëse ju vendosni atë kohë lineare,
O (n), thjesht nuk ishte e shpejtë të mjaftueshme për ju?
Ndoshta ju jeni ruajtjen vargje të mëdha,
dhe ju nuk mund të përballojë kohën shtesë që do të marrë
të kaloj nëpër të gjitha karakteret e tyre të numërimit një-nga-një.
Pra, ju vendosni të provoni diçka të ndryshme.
Çfarë ndodh nëse ju do të ndodhte me tashmë të ruajtur numrin e shkronjave
në vargun, të themi, në një ndryshore të quajtur 'len,'
në fillim të programit,
para se të ruajtur edhe karakterin e parë në vargun tuaj?
Pastaj, të gjithë ju do të duhet të bëni tani për të gjetur gjatësinë string,
shikoni se çfarë është vlera e variablit është.
Ju nuk do të duhet të shikoni në vargun e vetë në të gjitha,
dhe qasjen vlerën e një ndryshore si len konsiderohet
një operacion asymptotically konstante kohë,
ose O (1).
Pse është kjo? E pra, mbani mend se çfarë do të thotë kompleksiteti asymptotic.
Si funksionon ndryshimi runtime si madhësia
Inputet e juaj rritet?
>> Thonë se ju ishin duke u përpjekur për të marrë numrin e karaktereve në një varg të madh.
E pra, kjo nuk do të marrë parasysh sa i madh ju bëni string,
edhe një milion karaktere të gjatë,
të gjithë ju do të duhet të bëni për të gjetur gjatësinë e vargut me këtë qasje,
është për të lexuar vlerën e len ndryshueshme,
që keni bërë tashmë.
Gjatësia input, që është, gjatësia e vargut që ju jeni duke u përpjekur për të gjetur,
nuk ndikon fare se sa shpejt programi juaj shkon.
Kjo pjesë e programit tuaj do të kandidojë në mënyrë të barabartë të shpejtë në një varg një karakter
dhe një mijë karakter string,
dhe kjo është arsyeja pse ky program do t'i referohemi si drejtimin në kohë konstante
në lidhje me madhësinë e input.
>> Sigurisht, ka një pengesë.
Ju shpenzojnë hapësirë ​​shtesë kujtesës në kompjuterin tuaj
ruajtjen e ndryshueshme
dhe koha shtesë ajo ju merr
të bëjë ruajtjen aktuale të ndryshueshme,
por pika ende qëndron,
gjetur se sa kohë string juaj ishte
nuk varet nga gjatësia e vargut në të gjitha.
Kështu, ajo shkon në O (1) ose kohë të vazhdueshëm.
Kjo sigurisht nuk do të duhet të thotë
se kodi juaj shkon në 1 hap,
por pa marrë parasysh se sa hapa është,
në qoftë se ajo nuk ndryshon me madhësinë e inputeve,
ajo është ende asymptotically konstante e cila ne përfaqësojnë si O (1).
>> Si ju mund ndoshta me mend,
ka shumë runtimes ndryshme Big O për të matur me algoritme.
O (n) ² algoritme janë asymptotically ngadalshme se O (n) algoritme.
Kjo është, si numri i elementeve (n) rritet,
përfundimisht O (n) ² algoritme do të marrë më shumë kohë
se O (n) algoritme për të kandiduar.
Kjo nuk do të thotë O (n) algoritme gjithmonë kandidojë më të shpejtë
se O (n) ² algoritme, madje edhe në të njëjtin mjedis,
në të njëjtën hardware.
Ndoshta për të madhësive të vogla të dhëna,
O (n) ² algorithm mund të vërtetë punojnë më shpejt,
por, përfundimisht, si madhësia input rrit
drejt pafundësisë, të (n) Kohezgjatja O ² algoritmin e
përfundimisht do të eklipsonte Runtime të algorithm (n) O.
Ashtu si çdo funksion kuadratik matematikore
përfundimisht do të arrij ndonjë funksion linear,
pa marrë parasysh se sa e një kokë të fillojë funksionin linear fillon me.
Nëse ju jeni duke punuar me sasi të mëdha të të dhënave,
algoritme që të kandidojë në O (n) ² kohë mund të vërtetë të përfundojë ngadalësuar programin tuaj,
por për të madhësive të vogla të dhëna,
ju ndoshta nuk do të vini re.
>> Një tjetër kompleksiteti asymptotic është,
Ora logaritmike, O (log n).
Një shembull i një algoritmi që drejton këtë shpejt
është klasik kërkimit binar algorithm,
për të gjetur një element në një listë të renditura tashmë të elementeve.
>> Nëse ju nuk e dini se çfarë kërkoni binar bën,
Unë do të shpjegojë atë për ju me të vërtetë shpejt.
Le të thonë se ju jeni duke kërkuar për numrin 3
në këtë grup e integers.
Ajo duket në elementin e mesme e grup
dhe pyet, "A është elementi më i madh se unë dua, e barabartë me ose më pak se kjo?"
Nëse është e barabartë, atëherë e madhe. Keni gjetur elementin, dhe ju jeni bërë.
Në qoftë se kjo është më e madhe, atëherë ju e dini elementin
ka të jetë në anën e duhur e vektorit,
dhe ju mund të shikoni në atë në të ardhmen,
dhe në qoftë se është e vogël, atëherë ju e dini se ajo duhet të jetë në anën e majtë.
Ky proces është përsëritur më pas me grup të vogël të madhësisë
derisa elementi saktë është gjetur.
>> Kjo algorithm fuqishme shkurtime madhësinë e vektorit në gjysmën e me çdo operacion.
Pra, për të gjetur një element në një grup të renditura të madhësisë 8,
më së shumti (hyni ₂ 8),
ose 3 prej këtyre operacioneve,
kontrolluar elementin e mesme, pastaj prerja array në gjysmën do të jetë e nevojshme,
ndërsa një grup i madhësisë 16 merr (hyni ₂ 16),
ose 4 operacione.
Kjo është vetëm 1 operacion më shumë për një grup të dyfishuar në madhësi.
Dyfishuar madhësinë e vektorit
rrit Runtime vetëm nga 1 copë të këtij kodi.
Përsëri, duke kontrolluar elementin e mesme të listës, atëherë ndarjen.
Pra, ai tha se për të vepruar në kohë logaritmike,
O (log n).
Por prisni, ju thoni,
kjo nuk varet nga ku në listë elementi që ju jeni duke kërkuar për të është?
Çfarë ndodh nëse elementi i parë që ju shikoni në ndodh të jetë një e drejtë?
Pastaj, ajo merr vetëm 1 operacion,
pa marrë parasysh sa e madhe është lista.
>> E pra, kjo është arsyeja pse shkencëtarët kompjuter kanë kushtet më të
për kompleksitetin asymptotic që reflektojnë më të mirë rast
dhe më të keq rasti shfaqje të një algoritmi.
Më siç duhet, kufijtë e sipërme dhe të poshtme
në runtime.
Në rastin më të mirë për kërkimin binar, elementi ynë është
ka të drejtë në mes,
dhe ju të merrni atë në kohë të vazhdueshme,
pa marrë parasysh sa i madh pjesa tjetër e array është.
Simboli i përdorur për këtë është Ω.
Kështu, kjo algoritmi është thënë të drejtuar në Ω (1).
Në rastin më të mirë, ai e gjen elementin shpejt,
pa marrë parasysh sa i madh array është,
por në rastin më të keq,
ajo ka për të kryer (log n) kontrolle ndarë
e array për të gjetur elementin e duhur.
Kufijtë më të keq rastin e sipërme janë të referuara me "O" e madhe që ju tashmë e dini.
Kështu, ajo është O (log n), por Ω (1).
>> Një kërkim linear, nga ana tjetër,
në të cilën ju ecni nëpër çdo element i vektorit
për të gjetur një që ju dëshironi,
është në Ω mirë (1).
Përsëri, elementi i parë që ju dëshironi.
Pra, kjo nuk ka rëndësi se sa i madh është array.
Në rastin më të keq, kjo është elementi i fundit në grup.
Pra, ju duhet të ecin nëpër të gjitha elementet n në rrjet për të gjetur atë,
si në qoftë se ju jeni duke kërkuar për një 3.
Pra, ajo shkon në kohë O (n)
sepse kjo është në proporcion me numrin e elementeve në array.
>> Një simbol më të përdorur është Θ.
Kjo mund të përdoret për të përshkruar algoritme ku rastet më të mira dhe më të keq
janë të njëjta.
Ky është rasti në string-gjatësi algoritme kemi folur më herët.
Kjo është, në qoftë se ne të ruajtur atë në një variabël para
ne dyqan të vargut dhe të hyni në atë më vonë në kohë konstante.
Pa marrë parasysh se çfarë numri
ne jemi ruajtjen në atë variabël, ne do të duhet të shikojmë në të.
Rasti më i mirë është, ne e shohim atë
dhe për të gjetur gjatësinë e vargut.
Kështu Ω (1) ose më të mirë-rast koha konstante.
Rasti më i keq është,
ne shikojmë në atë dhe për të gjetur gjatësinë e vargut.
Kështu, O (1) ose koha konstante në rastin keq.
Pra, pasi rastin më të mirë dhe rastet më të këqija janë të njëjta,
kjo mund të tha te drejtuar në Θ kohë (1).
>> Në përmbledhje, ne kemi mënyra të mira për të arsyes rreth efikasitetit kodet
pa e ditur asgjë në lidhje me kohën reale botë që ata marrin për të kandiduar,
e cila është prekur nga shumë faktorë jashtë,
përfshirë hardware të ndryshme, software,
ose specifikat e kodit tuaj.
Gjithashtu, ajo na lejon për arsye të mirë për atë që do të ndodhë
kur madhësia e rrit inputeve.
>> Nëse ju jeni drejtimin në O (n) algorithm ²,
ose më keq, një O (2 ⁿ) algoritmi,
një nga llojet më të shpejtë në rritje,
ju do të vërtetë të fillojë të vërehet ngadalësim
kur ju filloni duke punuar me sasi të mëdha të të dhënave.
>> Kjo është kompleksiteti asymptotic. Faleminderit.