Hoofdstuk 5 Les 3: Tijdexperimenten, Pagina 3

Algoritmes classificeren

Op deze pagina, ga je leren dat sommige correcte algoritmes te langzaam zijn om goed kunnen gebruiken.

Als hij nog niet open staat, open dan het project H5L3-timer van de vorige pagina. Je gaat experimenteren met time function met de volgende invoerfuncties:
- (zoals je zag bij Hoofdstuk 3 Les 4: Een diagram-app maken)
- (zoals je zag bij Hoofdstuk 5 Les 1: Algoritmes om lijsten te verwerken)
- (zoals je zag bij Hoofdstuk 5 Les 3: Algoritmes vergelijken)
Wat gebeurt er voor elke invoer met de looptijd als je de grootte van de invoer verdubbelt?
Wat betekent het om de grootte van de invoer voor getallen van () tot () te verdubbelen?

Je kan algoritmen classificeren op basis van de tijd die ze nodig hebben om te worden uitgevoerd.

Gebruik het blok om de volgende twee blokken in Snap ! te bouwen. Bepaal vervolgens welk algoritme binnen een redelijke tijd kan worden uitgevoerd en welke niet.
De lijst met 2-cijferige nummers gaat van 10 tot 99. Je kan het ^-blok in het Functies-plaet gebruiken om machten van 10 te berekenen.

Om een algoritme te classificeren, kijk je naar het aantal stappen dat nodig is om het algoritme te voltooien, vergeleken met de grootte van de invoer.

Redelijke tijd: als het aantal stappen kleiner is dan of gelijk aan een macht van de grootte van de invoer, wordt het algoritme uitgevoerd in polynomiale tijd .

Polynomiale tijd omvat constante ( n ⁰), sublinear, lineair ( n ¹), kwadratische ( n ²), kubieke ( n ³), enz. functies:

algoritme-efficiëntie	Als je de grootte van de invoer verdubbeld,, dan...	voorbeeld-algoritme
constant	blijft de tijd hetzelfde (vermenigvuldigt met 2⁰ wat gelijk is aan 1)
sublineair	vermenigvuldigt de tijd met een getal tussen de 1 en 2 (tussen 2⁰ en 2¹)	binaire zoekopdracht: `positie van () in een gesorteerde lijst`
lineair	vermenigvuldigt de tijd met 2 (wat 2¹ is)	lineair zoekopdracht: `positie van () in een ongesorteerde lijst`
kwadratisch	vermenigvuldigt de tijd met 4 (wat 2² is)	sommige zoekalgoritmes
kubiek	vermenigvuldigt de tijd met 8 (wat 2³ is)	sommige algoritmes om genen in kaart te brengen

Het is zeldzaam om polynomiale algoritmes te vinden die meer dan kubieke ( n ³) tijd kosten.

Wat als een algoritme een hoeveelheid tijd kost die tussen twee categorieën valt?

Deze categorieën zeggen dat een algoritme hoogstens zoveel tijd kost. Dus een algoritme voor constante tijd is dus ook een algoritme voor lineaire tijd, en ook een algoritme voor polynomiale tijd. Maar meestal als iemand zegt dat een algoritme "kwadratische tijd kost", bedoelen ze dat het meer dan lineaire tijd maar niet meer dan kwadratische tijd kost.

Onredelijke tijd: als het aantal stappen groter is dan welke macht dan ook van de grootte van de invoer (dat wil zeggen, meer dan een polynomiale functie), dan werkt het algoritme in een onredelijke tijdshoeveelheid.
Het klassieke voorbeeld van een algoritme met onredelijke tijd is er een die exponentiële (2 ⁿ ) tijd gebruikt. 1 toevoegen aan de invoergrootte ( n ) verdubbelt het aantal stappen! Dus zo'n algoritme zal twee keer zo lang doen over het oplossen een probleem met als invoer 5 elementen, dan met een invoer van 4 elementen.

Een soort probleem waarvan de oplossing vaak onredelijk is, is een optimalisatieprobleem (zoals "vind de beste" of "vind de kleinste").

Het is belangrijk om te begrijpen dat een onredelijketijd-algoritme een probleem nog steeds correct oplost . Onredelijketijd-algoritmes kunnen soms worden vervangen door een heuristiek , dat is een polynomialetijd-algoritme dat het probleem niet precies oplost, maar een goede benadering biedt.

Een reden waarom het de moeite waard is om deze categorieën te leren, is dat je bij het schrijven van programma's vaak een probleem moet oplossen waarvoor al oplossingen zijn bedacht. Je hebt bijvoorbeeld geleerd dat het zoeken naar iets in een ongeordende lijst lineaire tijd vergt, maar als de lijst gesorteerd is, kun je deze sneller doorzoeken (in sublineaire tijd). Dus als je een programma schrijft dat herhaaldelijk in een lijst moet zoeken, weet je dat het de moeite waard is om de lijst te sorteren voordat je gaat zoeken. Als je weet welke standaardalgoritmen er al zijn, kan dat helpen met het bedenken van nieuwe algoritmes.

Bekijk enkele algoritmen die je hebt gebouwd. Bepaal of deze algoritmes in constante tijd, sublinear, lineaire, kwadratische of onredelijke tijd loopt.

Voor de manier waarop Alex gehele getallen toevoegt, maak je een grafiek met het aantal gehele getallen op de horizontale as en de looptijd op de verticale as. Genereer gegevens voor het diagram door time function uit te voeren met grote invoeren voor Alex' manier (bijvoorbeeld veelvouden van 100). Gebruik vervolgens de technieken van Les 2 om het diagram te maken.
Welke informatie vertelt dit diagram je over het algoritme van Alex? Kost het constante tijd, lineaire tijd, andere polynomiale tijd of is het onredelijke tijd?

De onderstaande tabel toont de computertijd die nodig is om verschillende taken op de gegevens van steden van verschillende grootte uit te voeren.

Taak	Klein Dorp (bevolking 1.000)	Gemiddeld Dorp (bevolking 10.000)	Groot Dorp (bevolking 100.000)
Data Invoeren	2 uren	20 uren	200 uren
Data Opslaan	0,5 uur	5 uren	50 uren
Data Doorzoeken	5 uren	15 uren	25 uren
Data Sorteren	0,01 uur	1 uur	100 uren

Op basis van de informatie in de tabel, welke van de volgende taken neemt waarschijnlijk de langste hoeveelheid tijd in beslag wanneer deze wordt opgeschaald voor een stad met 1.000.000 inwoners.

Data Invoeren

Omdat de populatiegrootte wordt vermenigvuldigd met 10, wordt de benodigde tijd voor het invoeren van gegevens ook vermenigvuldigd met 10, dus voor een populatie van 1.000.000 zou dit ongeveer 10 * 200 = 2000 uur duren.

Data Opslaan

Als de populatiegrootte met 10 wordt vermenigvuldigd, wordt de tijd die nodig is om een back-up van gegevens te maken met 10 vermenigvuldigd, dus voor een populatie van 1.000.000 zou dit ongeveer 10x50 = 500 uur duren.

Data Doorzoeken

Het doorzoeken van de gegevens lijkt te stijgen met ongeveer 10 uur elke keer dat de populatie wordt vermenigvuldigd met 10, dus voor een populatie van 1.000.000 zou het ongeveer 35 uur duren .

Data Sorteren

Correct! Omdat de populatiegrootte wordt vermenigvuldigd met 10, wordt de benodigde tijd voor het sorteren van gegevens vermenigvuldigd met 100. Dus voor een populatie van 1.000.000 ongeveer 100*100 = 10.000 uur.

Schrijf een stuk tekst waarin je het verschil uitlegt tussen algoritmen die binnen een redelijke tijd worden uitgevoerd en algoritmen die onredelijke tijd vereisen om te worden uitgevoerd.