komplexitet Big O tentafrågor

Vad betyder Big O?

Big O är en notation som används för att beskriva den asymptotiska tidskomplexiteten hos algoritmer.

Vad mäter Big O?

Big O mäter hur algoritmers körningstid växer i förhållande till storleken på indata.

Exempel på Big O-notationer?

- O(1) - O(n) - O(n^2) - O(log n) - O(n log n)

Sanna eller falska: Big O kan vara negativ?

Falsk. Big O representerar en övre gräns för tidskomplexiteten, och kan inte vara negativ.

Vad beskriver O(1)?

O(1) betyder konstant tid, oavsett indata, till exempel åtkomst av ett element i en array.

Vad innebär O(n)?

O(n) betyder att tiden att köra algoritmen ökar linjärt med datastorleken.

Jämför O(n) och O(n^2).

O(n) växer linjärt, vilket är effektivare än O(n^2) som växer kvadratiskt.

Fill in the blank: O(log n) representerar __________.

effektiv sökning, som i binärsökning.

Definiera O(n log n).

O(n log n) är tidskomplexiteten för effektiva sorteringsalgoritmer som mergesort.

Vad är asymptotisk analys?

Asymptotisk analys bedömer algoritmers prestanda när indata växer mot oändligheten.

Vad är skillnaden mellan bästa och sämsta fall i Big O?

Bästa fall beskriver den snabbaste körningstiden, medan sämsta fall beskriver den längsta.

Exempel på konstant tid?

Att hämta ett element från en lista med index är O(1).

Vad är O(n^2) typiskt för?

O(n^2) är vanligt i algoritmer som använder nästlade loopar.

Vad betyder O(n) i praktiken?

Det innebär att om indata fördubblas, så fördubblas ungefär också körningstiden.

Ge ett exempel på en algoritm med O(log n).

Binärsökning är en typisk algoritm med O(log n) komplexitet.

Vad står O för i Big O?

O står för 'ordning' och beskriver tillväxtordningen för en funktion.

Tidskomplexitet

Mäter hur tiden för att köra en algoritm förändras med storleken på indata.

Big O notationen

Används för att beskriva den värsta möjliga tidskomplexiteten hos en algoritm.

O(1)

Kallas konstant tidskomplexitet. Tiden för att köra algoritmen ändras inte med datastorlek.

O(n)

Linjära tidskomplexiteten. Tiden ökar linjärt i förhållande till indata n.

O(n^2)

Kallas kvadratisk tidskomplexitet. Vanligt i algoritmer som innehåller dubbla loopar.

O(log n)

Logaritmisk tidskomplexitet, exempelvis vid binärsökning. Tiden ökar långsammare än linjärt.

O(n log n)

Förekommer i effektiva sorteringsalgoritmer som mergesort och heapsort.

Är O(n) bättre än O(n^2)?

Ja, O(n) växer långsammare än O(n^2) och är mer effektiv vid stora n.

Exempel på O(1)

Att hämta ett element från en array: array[index].

Effekter av dubbla loopar

Genererar O(n^2) komplexitet vilket gör algoritmen mycket långsammare.

O(n) vs O(log n)

O(log n) är mer effektiv än O(n) vid stora datamängder.

Tidskomplexitet och indata

Tidskomplexiteten ökar oftast med datastorlek. Det är viktigt att optimera algoritmer.

Vad påverkar tidskomplexitet?

Algoritmens struktur, val av datastrukturer, och typ av operationer.

Exempel på O(n log n)

Mergesort, som kombinerar delning och sortering av datamängden.

Är O(n^2) alltid dåligt?

Inte nödvändigtvis. För små n kan det vara acceptabelt.

Formel för linjär komplexitet

O(n) innebär att tiden är proportionell mot n.

Vad är rumskomplexitet?

Rumskomplexitet mäter den mängd minne som en algoritm kräver i förhållande till storleken på indata.

Definiera O(1) rumskomplexitet.

O(1) indikerar att algoritmen använder en konstant mängd minne, oavsett storleken på indata.

O(n) rumskomplexitet innebär:

Minne som ökar linjärt med storleken på indata. - Exempel: En lista med n element.

Fill in the blank: O(n²) innebär att minnet ökar ______ med indata.

kvadratiskt

Vad betyder asymptotisk analys?

Analys av algoritmers beteende när indata växer mot oändligheten, vilket fokuserar på dominerande termer.

True or False: Rumskomplexitet och tidskomplexitet är alltid likadana.

False. De mäter olika aspekter: minnesanvändning vs. tidsanvändning.

Exempel på O(log n) rumskomplexitet.

Binär sökning: Använder logaritmisk minnesanvändning genom att dela indata i halvor.

Vilken rumskomplexitet har rekursiva algoritmer generellt?

O(n) eller O(n log n), beroende på hur många rekursiva anrop som görs.

Jämför O(n) och O(n log n).

O(n) är linjär medan O(n log n) växer snabbare, särskilt vid stora n.

Vad påverkar rumskomplexiteten mest?

Antalet variabler och datatyper som används i algoritmen.

Ge ett exempel på O(n³) rumskomplexitet.

En algoritm som använder tre nästlade loopar över n element.

Vad är minnesläckage?

En situation där minne inte frigörs efter att det inte längre används, vilket ökar rumskomplexiteten.

Förklara betydelsen av datatyper.

Olika datatyper påverkar rumskomplexiteten; till exempel, en lista kräver mer minne än en int.

Vad är stackminne?

Minnet som används för att lagra lokala variabler och funktionsanrop, vilket kan påverka rumskomplexiteten.

Vad innebär O(n + m)?

Rumskomplexiteten är summan av två datamängder, n och m, i algoritmen.

Nämn en metod för att minska rumskomplexitet.

Använd in-place algoritmer som förändrar data utan att behöva extra minne.

O(1) vs O(n)

O(1) är konstant tid, medan O(n) är linjär tid. O(1) är alltid snabbare än O(n).

Sanna eller falska: O(n^2) är snabbare än O(n log n).

Falska. O(n log n) växer långsammare än O(n^2) när n ökar.

Vad innebär O(n!)?

O(n!) innebär att algoritmen växer mycket snabbt, exempelvis i permutationsproblem. Mycket ineffektiv för stora n.

O(log n) vs O(n^2)

O(log n) är logarithmisk och mycket effektivare än O(n^2) när n ökar. O(n^2) växer kvadratiskt.

Fyll i luckan: O(n) är ___ än O(2^n).

mycket snabbare. O(2^n) växer exponentiellt, vilket gör den långsam för stora n.

Ge exempel på O(n log n) algoritm.

Exempel: Quicksort och Mergesort. Båda är effektiva sorteringsalgoritmer.

Vad är skillnaden mellan O(n) och O(n^2)?

O(n) är linjär och växer proportionellt, O(n^2) är kvadratisk och växer mycket snabbare med ökande n.

Sanna eller falska: O(1) och O(log n) är lika.

Falska. O(1) är konstant och alltid snabbare än O(log n) för stora n.

Beskriv O(n^3) typ av algoritm.

O(n^3) är kubisk tid. Exempel: vissa bruteforce-algoritmer för tredimensionella problem.

O(n) är snabbare än ___?

O(n^2) och O(2^n). Det växer långsammare än dessa.

Ge exempel på O(log n) algoritm.

Exempel: Binärsökning. Effektiv sökning i sorterade listor.

Vad innebär O(n^k)?

O(n^k) där k är en konstant, indikerar polynomisk tid. Ju högre k, desto långsammare.

Jämför O(n) och O(log n).

O(log n) är mer effektiv än O(n) för stora n, minimal ökning i tid.

Sanna eller falska: O(n^2) är alltid snabbare än O(n).

Falska. O(n) är snabbare än O(n^2) för alla n > 1.

Ge exempel på en algoritm med O(n^2) komplexitet.

Exempel: Bubbel sortering. Kontrollerar varje element med alla andra.

Vad är den bästa komplexiteten i Big O?

Den bästa komplexiteten i Big O är O(1), konstant tid oavsett input storlek.