prog3 Flashcards
Vad är en algoritm?
En algoritm är en ändlig följd av väldefinerade beräkningssteg, som typiskt tar ett eller flera inputvärden och ger ett resultat
Vad är en specifikation av en algoritm? Vad kännetecknar en fullständig specifikation?
En specifikation av en algoritm är en beskrivning av vad den förväntas åstadkomma (och inte hur). Oftast genom att beskriva förhållandet mellan indata och resultat.
Fullständig specifikation anger resultat för alla tänkbara indata.
Vad menas med algoritmkomplexitet?
Komplexiteten av en algoritm är tiden som funktion av indatans storlek. Alltså hur omfattande och resurskrävande en algoritm är.
Varför går det mycket fortare att undersöka om ett element finns i en mängd än om det finns i en lista?
Mängder använder hashning vilket gör det extremt effektivt att testa om ett element finns i en mängd. Listor använder inte hashning, dessutom kan inte duplikat förekomma i mängder vilket det kan i listor.
Vad är binärsökning och vilken komplexitet har den?
Binärsökning är en algoritm för att avgöra om en mängd innehåller ett givet element. Sökningen utförs i flera steg och i varje steg skall man utesluta att halva den kvarvarande mängden innehåller elementet och därmed kunna koncentrera sig på den andra halvan
Olog n
Vad är en slice och hur uttrycks det i python?
En slice är en delsträng, den kan uttryckas som s[x:y] och det är då en del av strängen s som börjar vid index x och slutar vid index y-1.
Vad är immutable och mutable?
Immutable innebär att en typ inte innehåller delar som kan uppdateras som strings och ints tex.
Mutable innebär att en typ innehåller delar som kan uppdateras som listor och dictionaries.
Vad innebär det att en metod beräknar ett resultat in place?
Det innebär att metoden ändrar objektet direkt istället för att skapa en ny kopia av objektet med förändringen.
Vad är nycklar och värden i en uppslagslista?
Skickar du in en nyckel får du ut ett värde i en uppslagslista, nyckeln är alltså en markör som du kan använda för att få fram värdet vilket är nyckelns associerade värde
