Datastrukturer och algoritmer - Tidskomplexitet
Hej!
Jag har en (egentligen två varav den andra frågan kommer att ställas i ett annat inlägg) fråga angående tidskomplexitet för en funktion. Frågan lyder:
Antag funktionen
g(n) = 2.4nlogn + 16.3n + 45.6logn + 7.1
Markera vilket/vilka av följande alternativ som är korrekta.
a. Ο(n^2)
b. Θ(nlogn)
c. Ο(logn)
d. Ω(1)
e. Θ(logn)
f. Ω(n^2)
De rätta svaren är a, b och d. Mina frågor är ifall ett alternativ t.ex. g. O(nlogn) hade funnits med, hade både a. och g. varit korrekta då? Min andra fråga är hur man ska tänka kring theta, Θ? Jag förstår att theta är en funktion som för vissa värden på n ska befinna sig ovanför g(n) och för andra värden på n så ska den befinna sig nedanför g(n) men vad gör b. mer korrekt än e.? Finns det något generellt tillvägagångsätt på hur man ska tänka kring Θ i liknande frågor?
Jättetacksam för svar!
(har uppdaterat inlägget, uppdateringen är markerat i fetstil)
Det saknas information om hur själva frågan är formulerad.
Yngve skrev:Det saknas information om hur själva frågan är formulerad.
Frågan är att jag har en funktion g(n) = 2.4nlogn + 16.3n + 45.6logn + 7.1. Jag ska välja vilka av dessa alternativ som är korrekt:
a. O(n^2)
b.theta(nlogn)
c. O(nlogn)
d. omega(1)
e. theta(logn)
f. omega(n^2)
De rätta svaren är a, b och d. Det jag undrar är hur det hade sett ut om O(nlogn) hade funnits med, varför b alternativet är mer korrekt än e och hur man ska tänka kring theta generellt i liknande uppgifter.
Korrekt i vilket avseende?
Att du har en funktion är ingen fråga.
Det saknas en frågeställning.
