[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.