Store-O notation (færdig)

Question 1

Hvad er store-O?

Answer 1

Hvis f(x) er Og(x) —(altså store O af g(x)), så er g(x) den øvre grænse for f(x). (for et funktionsudtryk)

Man ser bort fra unødvendige konstanter, så det er lettere at sammenligne med.

f(x) er O(g(x)) hvis man kan finde vidner (C,k) sådan at (den numeriske værdi af f(x)..):
findes uendelig mange vidner

|f (x) | ≤ C |g(x)| for alle x > k

C * g(x) betyder at det overhaler når vi kommer tilpas langt ud.

Question 2

Hvad er tidskompleksitet?

Answer 2

Tidskompleksitet er et tal for hvor hurtig en algoritme er. Det siger noget om hvor lang tid det tager for algoritmen givet en bestemt størrelse input.

Altså også indblik i hvor svært problemet er.

(fx ved at tælle sammenligninger)

Question 3

Hvad er store omega? Ω

Answer 3

Betegnes Ω.

Giver en nedre grænse på et funktionsudtryk.

Minder meget om store O, bare omvendt ulighedstegn.
|f (x) | ≥ C |g(x)| for alle x > k, c skal være positiv

Question 4

Hvad er store theta? Θ

Answer 4

Betegnes Θ.

Store omega (Ω) og Store O ligger på hver sin side af ens funktionsudtryk. Store theta lukker mellemrummet.

f(x) er Θ (g (x)) hvis f(x) er både O(g(x)) og Ω(g(x))

f.eks. x^2 er O(x^2)
x^2 er Ω(x^2)
x^2 er Θ(x^2)

det handler om hvilken ORDEN de tilhører - i dette tilfælde den samme, fordi det er x^2 (tror jeg….)

Question 5

Hvordan kan man bruge store-O notation ift. tidskompleksitet?

Answer 5

Til at få forståelse for hvor hurtig en algoritme er til at udføre sine kommandoer, så man kan sammenligne forskellige algoritmer og bedømme hvilken en der er bedst.

Bruger ofte worst-case scenario udregning.

Question 6

Hvad er en algoritme?

Answer 6

En række instrukser/kommandoer til er udføre en beregning eller løse et problem.

I matematik skrives det i pseudokode.

Question 7

Hvad er størst - eksponentiel kompleksitet eller potens/polynomie?

Answer 7

Altid eksponentiel.

Question 8

Hvad er bedst: når en algoritme kører i polynomiel tid eller i eksponentiel tid?

Answer 8

Polynomiel tid.