[Powered by Google Translate] Jy het waarskynlik gehoor mense praat oor 'n vinnige of doeltreffende algoritme vir die uitvoering van jou spesifieke taak, maar wat presies beteken dit vir 'n algoritme om vinnig of doeltreffende te wees? Wel, dit is nie praat oor 'n meting in real-time, soos sekondes of minute. Dit is omdat die rekenaar hardeware en sagteware wissel drasties. My program kan loop stadiger as joune, want ek loop dit op 'n ouer rekenaar, of omdat ek toevallig op 'n aanlyn video spel speel op dieselfde tyd, wat al my geheue verslindende, of ek my program kan hardloop deur middel van verskillende sagteware wat kommunikeer met die masjien anders op 'n lae vlak. Dit is soos appels en lemoene te vergelyk. Net omdat my stadiger rekenaar langer neem as joune terug te gee 'n antwoord beteken nie jy het die meer doeltreffende algoritme. 

So, want ons kan nie direk vergelyk die Runtimes van programme in sekondes of minute, Hoe vergelyk ons ​​2 verskillende algoritmes ongeag van hul hardeware of sagteware-omgewing? 'N meer eenvormige manier van die meet van algoritmiese doeltreffendheid te skep, rekenaar wetenskaplikes en wiskundiges uitgedink het konsepte vir die meet van die asimptotiese kompleksiteit van 'n program en 'n notasie genoem "Big Ohnotation" vir die beskrywing van hierdie. Die formele definisie is dat 'n funksie f (x) loop op die orde van g (x) indien daar 'n paar (x) waarde, x ₀ en n konstante, C, waarvoor f (x) is minder as of gelyk aan dat konstante keer g (x) vir alle x groter as x ₀. 

Maar moenie bang wees nie weg deur die formele definisie. Wat dit eintlik beteken in minder teoretiese terme? Wel, dit is basies 'n manier van die ontleding van hoe vinnig 'n program se runtime asimptoties groei. Dit is, na gelang van die grootte van jou insette verhoog na oneindigheid, Sê jy sorteer 'n verskeidenheid van grootte 1000 in vergelyking met 'n verskeidenheid van grootte 10. Hoe die looptyd van jou program groei? Byvoorbeeld, verbeel die tel van die aantal van karakters in 'n tou die eenvoudigste manier  deur die loop deur die hele string letter-vir-letter en die toevoeging van 1 tot 'n toonbank vir elke karakter. Hierdie algoritme is gesê om uit te voer in 'n lineêre tyd met betrekking tot die aantal karakters, 'N' in die tou. In kort, dit loop in O (n). Hoekom is dit? Wel, die gebruik van hierdie benadering, die tyd wat nodig die hele string te verken is proporsioneel tot die aantal karakters. Die tel van die aantal van karakters in 'n 20-karakterstring gaan twee keer so lank as wat dit neem die karakters te tel in 'n 10-karakterstring, want jy het om te kyk na al die karakters en elke karakter neem die dieselfde hoeveelheid tyd om na te kyk. Soos jy toename in die aantal van karakters, sal die runtime lineêr toeneem met die inset lengte. 

Nou, verbeel as jy besluit dat lineêre tyd, O (n), was net nie vinnig genoeg vir jou? Miskien is jy die stoor van groot snare, en jy kan nie bekostig om die ekstra tyd wat dit sou neem al van hul karakters tel een-vir-een te deurkruis. So, jy besluit om iets anders te probeer. Wat gebeur as jy sou gebeur reeds die aantal karakters te stoor in die tou, sê in 'n veranderlike genaamd "len, vroeg in die program, voordat jy selfs die heel eerste karakter in die string gestoor? Dan al wat jy nou moet doen om uit te vind die string lengte, word bepaal wat die waarde van die veranderlike is. Jy wil nie hê om te kyk na die tou self op alle, en toegang tot die waarde van 'n veranderlike soos len word beskou as 'n asimptoties konstante operasie, of O (1). Hoekom is dit? Wel, onthou wat asimptotiese kompleksiteit beteken. Hoe werk die runtime verandering as die grootte van jou insette groei? 

Sê jy probeer om die aantal karakters wat in 'n groter string te kry. Wel, sou dit nie saak hoe groot jy die tou, selfs 'n miljoen karakters lank, al wat jy hoef te doen, die tou se lengte met hierdie benadering te vind, is om te lees uit die waarde van die veranderlike len, wat jy reeds gemaak. Die inset lengte, dit is die lengte van die string wat jy probeer om te vind, raak nie al hoe vinnig jou program loop. Hierdie deel van jou program sou ewe vinnig hardloop op 'n een-karakterstring en 'n duisend-karakterstring, en dit is hoekom hierdie program sal na verwys word as hardloop in konstante tyd met betrekking tot die invoer grootte. 

Natuurlik, daar is 'n nadeel. Jy spandeer 'n ekstra geheue ruimte op jou rekenaar die stoor van die veranderlike en die ekstra tyd wat dit neem om jou die werklike stoor van die veranderlike te doen, maar die punt staan ​​nog steeds, om uit te vind hoe lank jou string was nie afhang van die lengte van die string at all. So, dit loop in O (1) of konstante tyd. Dit beteken beslis nie te beteken dat dat jou kode in 1 stap loop, maar maak nie saak hoeveel stappe dit is, as dit nie verander met die grootte van die insette, dit is nog steeds asimptoties konstante wat ons verteenwoordig as O (1). 

Soos jy kan dink, daar is baie verskillende groot O Runtimes algoritmes te meet. O (n) ² algoritmes is asimptoties stadiger as O (n) algoritmes. Dit is, as die aantal elemente (n) groei, O (n) ² algoritmes sal uiteindelik meer tyd neem as O (n) algoritmes uit te voer. Dit beteken nie O (n) algoritmes altyd hardloop vinniger as O (n) ² algoritmes, selfs in dieselfde omgewing, op dieselfde hardeware. Miskien is dit vir klein inset-groottes,  die O (n) ² algoritme kan eintlik vinniger werk, maar uiteindelik, as die inset grootte verhoog na die oneindigheid, die O (n) ² algoritme runtime sal uiteindelik oorskadu die looptyd van die algoritme O (n). Net soos enige kwadratiese wiskundige funksie  enige lineêre funksie sal uiteindelik inhaal, maak nie saak hoeveel van 'n kop begin die lineêre funksie begin met. As jy werk met groot hoeveelhede data, algoritmes wat loop in O (n) ² tyd kan regtig beland stadiger jou program, maar vir klein inset groottes, jy sal waarskynlik nie eens agterkom nie. 

Nog 'n asimptotiese kompleksiteit is, logaritmiese tyd, O (log n). 'N voorbeeld van 'n algoritme wat loop hierdie vinnig is die klassieke binêre soek algoritme, vir die vind van 'n element in 'n reeds-gesorteerde lys van elemente. 

As jy nie weet wat binêre soek doen, Ek sal dit vir jou verduidelik regtig vinnig. Kom ons sê jy is op soek vir die nommer 3 in die skikking van heelgetalle. Dit lyk op die middelste element van die skikking en vra, "Is die element wat ek wil groter as, gelyk aan of minder as dit?" As dit gelyk is, dan groot. Jy die element, en jy klaar is. As dit is groter, dan weet jy die element te wees in die regterkant van die skikking, en jy kan net kyk na wat in die toekoms, en as dit is kleiner, dan weet jy dit moet in die linkerkant. Hierdie proses word dan herhaal met die kleiner-grootte skikking totdat die korrekte element gevind word. 

Hierdie kragtige algoritme sny die skikking grootte in die helfte met elke operasie. So, 'n element te vind in 'n gesorteerde skikking van grootte 8, by die meeste (teken ₂ 8), of 3 van hierdie bedrywighede, die beheer van die middelste element, dan die skikking te sny in die helfte sal vereis word, terwyl 'n verskeidenheid van grootte 16 neem (teken ₂ 16), of 4 bedrywighede. Dit is net 1 meer operasie vir 'n verdubbel-grootte skikking. Verdubbeling van die grootte van die skikking verhoog die runtime deur slegs 1 stuk van hierdie kode. Weer, kontrole die middelste element van die lys, dan verdeel. So, is dit gesê om te werk in 'n logaritmiese tyd, O (log n). Maar wag, sê jy, dit nie afhang van waar die element wat jy soek is in die lys? Wat as die eerste element wat jy kyk na gebeur om die regte een te wees? Dan, dit neem net 1 werking, maak nie saak hoe groot die lys is. 

Wel, dit is waarom die rekenaar wetenskaplikes het meer terme vir asimptotiese kompleksiteit wat weerspieël die beste-geval en die ergste-geval optredes van 'n algoritme. Meer gewoon, die boonste en onderste grense op die runtime. In die beste geval vir binêre soek, ons element is reg daar in die middel, en jy kry dit in konstante tyd, maak nie saak hoe groot die res van die skikking is. Die simbool wat gebruik word vir hierdie Ω. So, hierdie algoritme het gesê in Ω (1) uit te voer. In die beste geval, is dit bevind dat die element vinnig, maak nie saak hoe groot die skikking is, maar in die ergste geval, dit het uit te voer (log n) verdeel tjeks die regte element van die skikking te vind. Ergste geval bogrense word bedoel met die groot "O" wat jy reeds ken. So, dit is O (log n), maar Ω (1). 

'N lineêre soek, in teenstelling, wat jy loop deur elke element van die skikking die een wat jy wil om te vind, is aan die beste Ω (1). Weereens, die eerste element wat jy wil. So, dit maak nie saak hoe groot die skikking is. In die ergste geval, dit is die laaste element in die skikking. Dus, jy het om te loop deur al die N-elemente in die skikking om dit te vind, graag as jy op soek vir 'n 3. So, dit loop in O (n) tyd want dit is eweredig aan die aantal elemente in die skikking. 

Een meer simbool wat gebruik word, is Θ. Dit kan gebruik word om algoritmes te beskryf waar die beste en die ergste gevalle is dieselfde. Dit is die geval in die string lengte algoritmes het ons gepraat oor vroeër. Dit is, as ons bêre dit in 'n veranderlike voor ons die stoor van die string en toegang tot dit later in konstante tyd. Maak nie saak watter getal ons stoor in daardie veranderlike, sal ons om te kyk na dit. Die beste geval is, ons kyk na dit en vind die lengte van die string. So Ω (1) of die beste geval konstante tyd. Die ergste geval is, ons kyk na dit en vind die lengte van die string. So, O (1) of konstante tyd in die ergste geval. Dus, sedert die beste geval en die ergste gevalle is die dieselfde, hierdie kan gesê word om uit te voer in Θ (1) tyd. 

In die opsomming, ons het goeie maniere om te redeneer oor kodes doeltreffendheid sonder om te weet enigiets oor die werklike wêreld tyd wat hulle neem om te hardloop, wat geraak word deur baie van die buite faktore, insluitende verskillende hardeware, sagteware, of die besonderhede van u kode. Ook, dit stel ons in staat om goed te redeneer oor wat sal gebeur wanneer die grootte van die insette toeneem. 

As jy loop in O (n) ² algoritme, of nog erger, 'n O (2 ⁿ) algoritme, een van die vinnigste groeiende tipes, jy regtig begin om die verlangsaming om op te let wanneer jy begin werk met groter hoeveelhede data. 

Dis asimptotiese kompleksiteit. Dankie.