06. december 2004 - 22:35Der er
5 kommentarer og 2 løsninger
Big-O, forklaring ønskes på bevis
Jeg har svært ved at forstå hvad konstanterne "witnesses" C og k gør i denne sammenhæng
"let f and g be functions from the set of integers or the set of real numbers to thge set of real numbers. We say that f(x) is O(g(x)) if there are constants C and k such that |f(x)| <= C|g(x)| whenever x > k.(this is read as "f(x) is big-oh of g(x)."
et eksempel kunne være at bevise at ---------------------------------------------------- x^4 + 9x^3 + 4x + 7 <= O(x^4)
Jeg mener nu nok jeg kan finde big-O for en funktion, algoritme osv.. men jeg kan virklig ikke se hvor k og c spiller en rolle.. det samme eksempel med k sat som noget andet ville måske hjælpe på min forståelse men jeg kan ikke rigtigt finde nogen konkrete eksempler på nettet så det ville være rart hvis der er nogen her der kan banke det ind i hovedet på mig :)
Der eksisterer: - et tal k - et tal C hvor det gælder at hvis x > k så vil |f(x)| <= C|g(x)|
D.v.s. at k er et tal hvor den mest betydende del af f(x) begynder at slå igennem og C er bare den proportionalitets faktor som man ikke bruger i big O
tænk på logaritmefunktionerne. for enhver logaritmefunktion er big-oh til enhver anden logarimefunktion logN(x) = C *ln(x) det er samme C-værdi for enhver x så vi behøver ikke angive nogen k-værdi. På den anden side vil C have forskellige værdier altefter hvilken base (N-værdi) vi bruger i logN()
big-oh proportional størrelsesorden indenfor et givet interval C angiver proportionen for de aktuelle 2 funktioner k angiver intervallet hvor de 2 funktioner er proportionale
i logaritme eksemplet ovenfor er proportionen perfekt. det behøver den ikke at være, og der vi bruger det er som ofter i situationer hvor vi ønsker at bruge en simpel funktion (eller blot et sæt værdier) tilnærmer sig en 'ideal' funktion (som desværre ville være et helvede at regne med:-)).
fx: g() er 3 punkter (x,y): (1,4) (2,2) (4,1) forbundet f() er hyperbelen y = 4/x
så f(x) <= 1 * g(x) i intervallet 1..4 //shift nulline og brug absværdier for at gøre intervallet til et enkelt tal (spejlet over nul)
den ene funktion ligner den anden lidt i det område, så nu kan vi begynde at tegne hende der toombraiders højre arm med løftet sværd (det ligner også en hyperbel lidt)
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
