[Powered by Google Translate] U hebt waarschijnlijk gehoord mensen praten over een snelle of efficiënt algoritme voor het uitvoeren van uw specifieke taak, maar wat precies betekent het voor een algoritme om snel en efficiënt? Nou, het is niet over een meting in real-time, zoals seconden of minuten. Dit komt doordat computer hardware en software variëren sterk. Mijn programma zou kunnen lopen langzamer dan die van jou, want ik ben het runnen van het op een oudere computer, of omdat ik toevallig te spelen van een online video game tegelijkertijd wordt die Noteer alle mijn geheugen, of ik zou kunnen lopen mijn programma door middel van verschillende software die communiceert met de machine anders op een laag niveau. Het is als het vergelijken van appels met peren. Gewoon omdat mijn langzamere computer duurt langer dan de jouwe terug te geven een antwoord betekent niet dat je hebt hoe meer efficiënt algoritme. 

Dus, omdat we niet direct vergelijken met de looptijden van de programma's in seconden of minuten, hoe kunnen we vergelijken 2 verschillende algoritmen ongeacht hun hardware-of software-omgeving? Om een ​​meer uniforme manier van meten algoritmische efficiëntie te creëren, informatici en wiskundigen hebben bedacht concepten voor het meten van de asymptotische complexiteit van een programma en een notatie genaamd 'Big Ohnotation' voor het beschrijven deze. De formele definitie is dat een functie f (x) uitgevoerd in de orde van g (x) dan als er een paar (x) waarde, x ₀ en een constante, C, waarbij f (x) kleiner dan of gelijk aan constante maal dat g (x) voor alle x groter is dan x ₀. 

Maar laat u niet afschrikken door de formele definitie. Wat betekent dit eigenlijk in minder theoretische termen? Nou, het is in feite een manier van het analyseren van hoe snel een programma runtime asymptotisch groeit. Dat is, zoals de grootte van uw input verhoogt naar oneindigheid, zeggen, je sorteren een array van grootte 1000 vergeleken met een array van grootte 10. Hoe verhoudt de looptijd van uw programma te laten groeien? Stel bijvoorbeeld het tellen van het aantal tekens in een string de eenvoudigste manier  door een wandeling door de hele reeks letter-voor-letter en het toevoegen van 1 tot en met een teller voor elk karakter. Dit algoritme wordt gezegd om te draaien in lineaire tijd met betrekking tot het aantal tekens, 'N' in de tekenreeks. Kortom, het loopt in O (n). Hoe komt dat? Nou, met behulp van deze aanpak, de tijd die nodig is om de gehele tekenreeks doorkruisen evenredig is met het aantal tekens. Tellen van het aantal tekens in een 20-tekenreeks gaat twee keer zo lang als nodig is om de tekens te tellen in een 10-tekenreeks, want je moet kijken naar alle tekens en elk teken is dezelfde hoeveelheid tijd te zien. Als u het aantal tekens, de runtime zal lineair toeneemt met de ingang lengte. 

Nu, stel je voor dat je besluit dat lineaire tijd, O (n), was gewoon niet snel genoeg voor jou? Misschien bent u het opslaan van grote strijkers, en je kunt niet veroorloven de extra tijd die het zou kosten al hun tekens tellen een voor een passeren. Dus, je besluit om iets anders te proberen. Wat als je zou er gebeuren met al slaan het aantal tekens in de string, bijvoorbeeld in een variabele met de naam 'len,' vroeg in het programma, voordat je zelfs opgeslagen het eerste teken in je string? Dan, alles wat je zou nu moeten doen om uit te vinden de lengte van het touw, is na te gaan wat de waarde van de variabele is. Je zou het niet moeten kijken naar de string zelf helemaal niet, en toegang tot de waarde van een variabele zoals len beschouwd een asymptotisch constante tijd operatie, of O (1). Hoe komt dat? Nou, onthoud wat asymptotische complexiteit betekent. Hoe werkt de runtime verandering als de grootte van uw ingangen groeit? 

Zeg dat je probeerde het aantal tekens in een grotere reeks te krijgen. Nou, het zou niet uit hoe groot je de snaar te maken, zelfs een miljoen tekens lang zijn, alles wat je zou moeten doen om de snaar lengte met deze aanpak te vinden, is het uitlezen van de waarde van de variabele len, die je al gemaakt. De input lengte is, dat de lengte van de tekenreeks u probeert te vinden, heeft geen invloed op helemaal hoe snel je programma draait. Dit deel van uw programma zou even snel draaien op een one-tekenreeks en duizend-tekenreeks, en dat is waarom dit programma zou worden aangeduid als lopen in constante tijd met betrekking tot de input-maat. 

Natuurlijk, er is een nadeel. U besteedt extra geheugenruimte op uw computer opslaan van de variabele en de extra tijd die je nodig hebt de feitelijke opslag van de variabele do, maar het punt staat stil, het vinden van hoe lang uw snaar was niet af van de lengte van de tekenreeks helemaal. Dus, het loopt in O (1) of constante tijd. Dit hoeft zeker niet te betekenen dat uw code wordt uitgevoerd in 1 stap, maar maakt niet uit hoeveel stappen het is, indien niet verandert met de grootte van de ingangen, het is nog steeds asymptotisch constante die wij vertegenwoordigen als O (1). 

Zoals je waarschijnlijk wel kunt raden, er zijn veel verschillende grote O runtimes om algoritmen te meten met. O (n) ² algoritmen asymptotisch langzamer dan O (n) algoritmen. Dat is, zoals het aantal elementen (n) groeit, uiteindelijk O (n) ² algoritmes kost meer tijd dan O (n) algoritmen uit te voeren. Dit betekent niet dat O (n) algoritme altijd sneller lopen dan O (n) ² algoritmen, zelfs in dezelfde omgeving, op dezelfde hardware. Misschien voor kleine ingang maten,  de O (n) ² algoritme misschien wel sneller werken, maar, uiteindelijk, als de input grootte toenemen naar het oneindige, de O (n) ² algoritme runtime zal uiteindelijk overschaduwen de looptijd van de O (n) algoritme. Net als elke kwadratische wiskundige functie  zal uiteindelijk inhalen elke lineaire functie, maakt niet uit hoe veel van een voorsprong de lineaire functie begint met. Als u werkt met grote hoeveelheden gegevens, algoritmen die worden uitgevoerd in O (n) ² tijd kan echt uiteindelijk vertragen van uw programma, maar voor kleine ingang maten, zal je waarschijnlijk niet eens merken. 

Een asymptotische complexiteit, logaritmische tijd, O (log n). Een voorbeeld van een algoritme dat deze verloopt snel is de klassieke binaire zoekalgoritme, voor het vinden van een element in een reeds gesorteerde lijst van elementen. 

Als je niet weet wat binary search doet, Ik leg het voor u heel snel. Laten we zeggen dat je op zoek bent naar het getal 3 in deze array van integers. Het ziet er in het midden element van de array en vraagt: "Is het element wil ik groter dan, gelijk aan of kleiner is dan dit?" Als het gelijk, dan groot. Je vond het element, en je bent klaar. Als het groter is, dan weet je het element moet in de rechterzijde van de array, en je kunt alleen kijken naar dat in de toekomst, en als het kleiner is, dan weet je het moet aan de linkerkant. Dit proces wordt vervolgens herhaald met de kleinere grootte matrix totdat de juiste element wordt gevonden. 

Deze krachtige algoritme snijdt de array size in de helft na elke handeling. Dus, om een ​​element te vinden in een gesorteerde array van maat 8, bij de meeste (log ₂ 8), of 3 van deze operaties, controleren van de middelste element, dan snijden de array in half is vereist, terwijl een array van grootte 16 heeft (log ₂ 16), of 4 operaties. Dat is slechts 1 meer bediening voor een dubbele-size array. Verdubbeling van de array verhoogt de looptijd met slechts 1 stuk van deze code. Nogmaals, het controleren van de middelste element van de lijst, dan splitsen. Dus, het is gezegd om te werken in logaritmische tijd, O (log n). Maar wacht, u zegt, niet dit is afhankelijk van waar in de lijst het element dat u zoekt is? Wat als het eerste element je kijkt naar toevallig ook de juiste? Dan, het duurt maar 1 operatie, maakt niet uit hoe groot de lijst is. 

Nou, dat is waarom informatici hebben meer termen voor asymptotische complexiteit die het best-case weerspiegelen en worst-case prestaties van een algoritme. Beter gezegd, de boven-en ondergrenzen op de runtime. In het beste geval voor binaire zoeken, ons element is daar in het midden, en je krijgt het in constante tijd, ongeacht hoe groot de rest van de matrix. Het symbool voor dit Ω. Dus, is dit algoritme gezegd om te draaien in Ω (1). In het beste geval, het vindt het element snel, maakt niet uit hoe groot de array, maar in het ergste geval, het heeft uit te voeren (log n) split controles van de matrix om de juiste element vinden. Worst-case bovengrenzen worden aangeduid met de grote "O" die je al kent. Dus, het is O (log n), maar Ω (1). 

Een lineair zoeken daarentegen in waarin je door elk element van de array aan degene die je wilt vinden, is best Ω (1). Nogmaals, het eerste element dat u wilt. Het maakt dus niet uit hoe groot de array is. In het ergste geval, het is het laatste element in de array. Dus, je moet je door alle n elementen in de array om het te vinden, graag als je op zoek naar een 3. Dus, het loopt in O (n) tijd omdat het evenredig aan het aantal elementen in de array. 

Een meer gebruikt symbool Θ. Dit kan worden gebruikt om algoritmen waar de beste en slechtste geval beschrijven dezelfde. Dit is het geval in de string-length algoritmen hebben we het eerder over had. Dat wil zeggen, als we het op te slaan in een variabele voor slaan we de string en de toegang later in constante tijd. Het maakt niet uit welk nummer we opslaan in de variabele, zullen we moeten kijken. Het beste geval is, kijken we naar het en vind de lengte van de tekenreeks. Dus Ω (1) of best-case constante tijd. Het ergste geval is, we kijken ernaar en vind de lengte van de string. Dus, O (1) of constante tijd in het ergste geval. Dus, aangezien de beste en slechtste geval gevallen hetzelfde, Dit kan worden gezegd om te draaien in Θ (1) tijd. 

Kortom, we hebben goede manieren om te redeneren over codes efficiëntie zonder iets te weten over de echte wereld tijd die zij nemen om te draaien, die wordt beïnvloed door vele factoren van buitenaf, waaronder verschillende hardware, software, of de specifieke kenmerken van uw code. Ook is het ons in staat stelt om goed te redeneren over wat er zal gebeuren wanneer de omvang van de ingangen toeneemt. 

Als u gebruik maakt van O (n) ² algoritme, of erger nog, een O (2 ⁿ) algoritme, een van de snelst groeiende types, je zult echt beginnen aan de vertraging merken wanneer u begint te werken met grotere hoeveelheden data. 

Dat is asymptotische complexiteit. Bedankt.