Algoritmes classificeren

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

  1. 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: 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.

  1. Geen Afbeelding
    Gebruik het Geen Afbeelding 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.
    1. Geen Afbeelding
    2. Geen Afbeelding

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.

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.

  1. Bekijk enkele algoritmen die je hebt gebouwd. Bepaal of deze algoritmes in constante tijd, sublinear, lineaire, kwadratische of onredelijke tijd loopt.
  1. 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.
  2. 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?
  1. 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
    Data Opslaan
    Data Doorzoeken
    Data Sorteren
  2. 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.
Terug Volgende