Diversen

Tijdscomplexiteit: waarom sommige algoritmen miljarden jaren lopen

Tijdscomplexiteit: waarom sommige algoritmen miljarden jaren lopen


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Dit is het derde artikel in een zevendelige serie over algoritmen en berekeningen, waarin wordt onderzocht hoe we eenvoudige binaire getallen gebruiken om onze wereld van stroom te voorzien. Het eerste artikel, Hoe algoritmen de wereld waarin we leven beheersen, vindt u hier.

Als je een visualisatie bekijkt van verschillende sorteeralgoritmen die aan een dataset werken, wordt het heel snel duidelijk dat sommige veel beter zijn dan andere. Waar een algoritme neemt seconden om te voltooien, een ander zal nemen minuten zelfs met kleine datasets. Gelukkig hoeven we het algoritme niet aan het werk te zien om te weten of het algoritme de klus snel kan klaren of dat het zal instorten onder het gewicht van zijn invoer. Dat is wat Big O-notatie is voor, en het kan ons in één oogopslag vertellen of de Tijdscomplexiteit van een algoritme betekent dat we het binnen een paar krijgen uren of miljarden jaren.

Wat is tijdcomplexiteit?

In meer formele termen, tijd complexiteit is de meting van hoe lang het duurt voordat een algoritme wordt geproduceerd een resultaat, ten opzichte van de grootte van zijn input. Praktisch is het de groeiratio in de aantal bewerkingen nodig om een ​​resultaat te produceren voor elke extra invoereenheid.

In het eerste artikel in deze serie beschreef ik een rechttoe rechtaan sommatie-algoritme. Om de som van alle nummers tussen de nummers p en q, Ik heb een andere variabele verklaard, r, en zet deze op nul. Ik heb toen toegevoegd p naar r, voegde ik eraan toe p + 1 naar r, vervolgens p + 2, enzovoort totdat ik eindelijk heb toegevoegd q zichzelf aan r, op welk punt ik stopte en het resultaat terugstuurde, r, die de som.

Hoeveel bewerkingen zijn hiervoor nodig, zonder te weten wat de uiteindelijke invoergrootte zal zijn, met alleen de abstracte variabelen p en q? Wat we eigenlijk doen, is een lus waar elke iteratie toeneemt p door precies 1 en voegt het toe r. Dit is eigenlijk hoe ons algoritme eruitziet wanneer het wat formeler wordt gepresenteerd:

1. laten r = 0
2. terwijl p is <= naar q
3. r=p+r
4. p = p+1
5. terugkeer r

Wanneer zo opgemaakt in wat we noemen pseudocode, het wordt veel gemakkelijker om te zien hoeveel bewerkingen hiervoor nodig zijn. Ga de stappen nummer voor nummer af en tel de bewerkingen. De eerste is een instructie, dus het is een enkele handeling. De tweede regel is echter anders. Lussen zoals deze worden herhaald totdat aan de voorwaarde is voldaan, in dit geval eenmaal p is groter dan q. We weten dan dat we opnemen q en p in de som, dus het aantal iteraties door dit lus is gelijk aan q - (p - 1), welke is de invoergrootte voor ons algoritme.

Maar dat is slechts het aantal keren dat we door de lus herhalen, we moeten ook de bewerkingen erin tellen, en daar voegen we toe p en r en toewijzen het resultaat naar r en dan voegen we toe p en 1 en wijs het resultaat vervolgens toe aan p. Dus we treden op twee operaties voor iedere iteratie, en er zijn q - (p - 1)iteraties. Het enige wat we nu hoeven te doen is ons vermenigvuldigen 2 operaties en q - (p - 1)iteraties te krijgen 2 * (q - (p - 1)) bewerkingen voor de hele lus. Voeg de bewerkingen bij 1. en 5. toe, wat ons een laatste telling geeft van 2 * (q - (p - 1)) + 2 bewerkingen voor dit algoritme.

Dit is een lineaire functie aangezien er geen exponenten zijn, dus de groeiratio want ons sommatie-algoritme is direct verbonden met de invoer grootte, die we noemen lineaire tijdcomplexiteit. Als algemene regel geldt dat wat de term van de hoogste orde in een formule die onze tijdcomplexiteit definieert, ook de groei in de tijd kenmerkt, dus nemen we de term van de hoogste orde en schrappen de rest, waardoor q - (p - 1) overblijft, wat we zullen doen bellen n voor de eenvoud.

Lineaire tijdcomplexiteit klinkt misschien inefficiënt als u invoergroottes in de miljarden afbeeldt, maar lineaire tijd is eigenlijk niet zo slecht. We kunnen het echter beter doen.

We weten al heel lang dat de som van allemaalde nummers van 1 en q wordt gegeven door de formule (q * (q + 1)) / 2. We weten ook dat decommutatieve eigenschap van optellen vertelt ons dat het resultaat van (p-1 * (p)) / 2 afgetrokken van (q * (q + 1)) / 2 snijdt gewoon het deel van de som af dat alles omvat 1 naar p-1, waardoor de som van de nummers van p naar q achter, en dat is precies wat we willen.

Dit algoritme zou, afhankelijk van hoe het is gecodeerd, niet meer dan drie operaties. Omdat directe wiskundige bewerkingen zoals deze precies de dingen zijn die computers beter doen dan mensen, zouden we de formules kunnen samenvoegen tot een enkele wiskundige uitdrukking, en de processor zal er net zo gemakkelijk doorheen kauwen als wanneer we het in kleinere stukjes zouden breken, maar we houden ons aan drie operaties op dit moment.

1. p = (p-1 * (p)) / 2
2. q
= (q * (q + 1)) / 2
3. terugkeer ( q -p )

Nee lussen, gewoon een constant aantal bewerkingen die niet veranderen, ongeacht het verschil tussen p en q is. Dit algoritme heeft altijd drie bewerkingen nodig om uit te voeren, dus we noemen dit constante tijdcomplexiteit.

Nu, als u niet wist wat uw invoergrootte zou zijn toen je een algoritme aan het ontwerpen was, welk algoritme ga je tussen deze twee gebruiken? Het is duidelijk dat de tweede, omdat constante tijd algoritmen zijn in wezen een computationele gratis lunch voor zover het de input betreft. Dus zoals wij vergroot ons programma om mee om te gaan meer gegevens, zal hun looptijd niet merkbaar veranderen, terwijl we weten dat ons eerste algoritme precies evenveel zal groeien als onze input, wat een waarde van miljarden of meer kan zijn. Natuurlijk betekent constante tijdcomplexiteit niet altijd dat het efficiënter is, maar in dit geval is het degene die we willen.

Voordat we ooit gingen zitten om een regel code, we hebben al ontdekt welk algoritme dat was de betere optie voor onze inbreng, en we hoefden het nooit uit te voeren om erachter te komen hoe goed het werkt. Dit is waarom we tijd complexiteit, er zijn gewoon niet zoveel tools die zo effectief zijn het beoordelen van de efficiëntie van algoritmen.

Wat is de Big O-notatie?

We hebben een speciale manier om deze efficiëntie te annoteren om dingen gemakkelijker te maken, iets wat we noemen Big O-notatie. Simpel gezegd, Big O-notatie vertegenwoordigt de algoritmeefficiëntie loop door zijn in het slechtste geval. Als u een naam in een directory moest zoeken door elke naam te lezen totdat u de juiste had gevonden, is het ergste scenario dat de naam die u zoekt de allerlaatste vermelding in de directory is. Dit betekent dat je de hele directory van n namen om naar degene te gaan die u zoekt. Dus we zeggen dat dit algoritme O is (n), waar n is de hoogste orde termijn in onze bedrijfsformule.

Er zijn andere Grote notaties voor de beste geval en gemiddeld geval, maar wat er echt toe doet, is de in het slechtste geval; dat zijn degenen die uw computer kunnen laten crashen - of erger nog, jouw auto of uw vliegtuig. Ze gaan rechtstreeks naar de kern van waarom tijd complexiteit doet ertoe en wijs aan waarom sommige algoritmen kan eenvoudig een probleem niet oplossen zonder te nemen een paar miljard jaar om het te doen.

Dus hoe gebruiken we Big O-notatie? De bovenstaande tabel laat zien hoe deze verschillen Big O-notaties kijk in de praktijk, met de x-as zijn uw input en uw y-as de tijd die nodig is om te eindigen. Voor een beetje meer details vindt u een korte lijst met alle Big O-notaties die er toe doen voor nu en de tijd complexiteit zij vertegenwoordigen:

* O (1): Constante tijdcomplexiteit- Dit is de effectieve computationele vrije pas waar we het eerder over hadden. Dit betekent niet noodzakelijk dat het sneller is. Het betekent gewoon dat de tijd complexiteit is niet gerelateerd aan de grootte van de invoer.

* O (logboek n): Logaritmische tijdcomplexiteit- Deze komen het meest voor bij gebruik van een verdeel-en-heers strategie op een dataset, waarbij elke operatie een groot deel van de invoer weggooit waarvan is uitgesloten dat deze de oplossing niet heeft. Het klassieke voorbeeld is een woord opzoeken in een woordenboek: open willekeurig, controleer in welk lettergedeelte u zich bevindt, negeer vervolgens het gedeelte waarvan u weet dat uw woord niet zal staan, en herhaal de resterende gedeelten en gooi ze weg totdat u vindt jouw woord.

* Aan): Lineaire tijdcomplexiteit- Dit was vanaf het begin ons sommatie-algoritme.

* O (n log n): Linearitmische tijdcomplexiteit- Het uitvoeren van een snelle Fourier-transformatie is een O (n Log n) algoritme, net als een Mergesort.

* Aan2): Kwadratische tijdcomplexiteit- Dit wordt meestal gevonden wanneer u geneste lussen heeft. Als we in ons eerste algoritme een tweede lus binnen de eerste hadden, zou de functie kwadratische tijdcomplexiteit hebben ontwikkeld.

* Aanc, c> 1): Polynomiale tijdcomplexiteit- Polynomiale tijdcomplexiteit is erg belangrijk omdat het min of meer vertegenwoordigt de bovengrens op wat een klassieke computer kan in een praktische hoeveelheid tijd oplossen.

* O (cn, n> 1, c> 1): Exponentiële tijdcomplexiteit- Dit is waar je het Miljard jaar algoritmen. Elke keer dat een eenheid van invoer veroorzaakt u het dubbele aantal uitgevoerde bewerkingen ten opzichte van het aantal dat wordt uitgevoerd als de invoer isn-1, jij hebt exponentiële tijdcomplexiteit. Het meest voorkomende voorbeeld dat de meeste mensen gebruiken, is proberen op te sommen elke mogelijke subset van een set, maar Brute-forcing een 128-bits coderingssleutel wordt meestal in deze categorie geplaatst.

* Aan!): Factoriële tijdcomplexiteit- Dit zijn algoritmen die waarschijnlijk zouden kunnen werken tot de warmtedood van het heelal met een matig grote invoergrootte van een paar duizend. Telkens als je zoiets hebt als 'op hoeveel verschillende manieren kun je deze reeks rangschikken', heb je een permutatieprobleem en moet je met brute kracht naar een antwoord zoeken n! verschillende waarden, die wordt gegeven door het resultaat van: n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Dit zijn de algoritmen die bijna parallel lopen aan de y-as in het bovenstaande diagram.

Waarom we niet zomaar betere algoritmen kunnen bedenken

Het is niet vanwege een gebrek aan proberen. Het hele veld van theoretische informatica gaat erom het meeste te vinden efficiënt algoritme voor een bepaald probleem, maar soms kennen we de wiskunde gewoon niet. En niet alleen jij en ik, we hebben het over de winnaars van de Field's Medal die tegen een aantal problemen aanlopen, zoals de O (2n) en Aan!) en hun gok is net zo goed als die van ons.

Er is een hele catalogus van problemen die we nog niet hebben om op te lossen - we zullen daar aan het einde van de serie meer op ingaan - maar deze problemen werken als knelpunten die inefficiënties veroorzaken in het bedrijfsleven, wetenschappelijk onderzoek en andere administratieve gebieden, en er wachten veel mensen tot deze problemen eindelijk zijn opgelost. Er zijn zelfs zeer lucratieve prijzen uitgereikt aan iedereen die een aantal van deze dingen kan oplossen, maar tot nu toe heeft niemand dit kunnen doen en sommige van deze problemen blijven al tientallen jaren bestaan.

De reden waarom klassieke computers kunnen deze problemen niet efficiënt oplossen, ook is ingebouwd in de circuits van de machine; elke instructie die wordt gegeven, moet worden voltooid voordat deze met de volgende kan beginnen. Multicore-systemen of machines met meerdere processors kunnen de zaken versnellen, maar je hebt waarschijnlijk nog steeds nodig een of twee biljoen jaar om een ​​resultaat te krijgen nadat we al onze processors bij elkaar hebben gegooid en los hebben gezet op een Aan!) probleem waar n was zoiets als 500.

Computeringenieurs zien dit al decennia aankomen, maar nu komen we eindelijk aan het einde van de lijn voor wat we uit een klassieke computer. Je kunt deze gewoon niet maken operaties gaan sneller, en dat kunnen ze van nature ook Voer slechts één bewerking tegelijk uit. Als u een algoritme heeft dat vereist triljoenen operaties om te voltooien, een klassieke computer moet al deze uitvoeren operaties in volgorde. Op dat moment wordt de tijd die nodig is om een ​​resultaat te krijgen gewoon een kwestie van wiskunde en natuurkunde. Als we deze problemen gaan oplossen exponentiële tijdcomplexiteit of groter, vervolgens iets anders is nodig.

Het goede nieuws is dat we weten dat het mogelijk is, in minstens één geval, om een ​​algoritme te vinden dat efficiënt genoeg is om het antwoord op een van deze te vinden O (2n) problemen in polynomiale tijdcomplexiteit. Als het één keer kan worden gedaan, is het mogelijk om het opnieuw te doen; het duurt maar het hele "fysica" -gedoe omzeilen.

Het vierde artikel in onze serie over algoritmen en berekeningen, Hoe het algoritme van Peter Shor ervoor zorgt dat RSA-versleuteling mislukt, vind je hier.


Bekijk de video: #15 Maatregelen zijn onnodig: Professor Pierre Capel en Ab Gietelink (Mei 2022).