Wat is polynomiale tijd in gewone mensentaal?
Met andere woorden wat wordt hiermee bedoeld in de context van algoritmes.
4.4K
4.4K keer bekeken
Geef jouw antwoord
Antwoorden (1)
Dat wil zeggen dat als het aantal elementen van de invoer x keer zo groot word, de tijd die de rekenregels nodig hebben om te worden uitgevoerd niet meer zal toenemen dan x^k.
Dat noemen we dan meestal "snelle" algoritmes
Voorbeeld:
* De kleinste waarden zoeken in een lijst kost in een lijst die 2 keer zo lang is maximaal 2 keer zoveel tijd.
* Het sorteren van een lijst (met bubblesort) die 2 keer zo lang is, kost 2^2 = 4 keer zoveel tijd.
Als de benodigde tijd van een rekenregel sneller dan x^k toeneemt, dan zal in de praktijk bij grotere problemen de benodigde tijd veel te lang worden om praktisch bruikbaar te zijn.
Dat noemen we dan meestal "snelle" algoritmes
Voorbeeld:
* De kleinste waarden zoeken in een lijst kost in een lijst die 2 keer zo lang is maximaal 2 keer zoveel tijd.
* Het sorteren van een lijst (met bubblesort) die 2 keer zo lang is, kost 2^2 = 4 keer zoveel tijd.
Als de benodigde tijd van een rekenregel sneller dan x^k toeneemt, dan zal in de praktijk bij grotere problemen de benodigde tijd veel te lang worden om praktisch bruikbaar te zijn.
Verwijderde gebruiker
12 jaar geleden
Deel jouw antwoord