Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

Stránky: 1

 

#1 03. 10. 2012 21:25

mb305
Příspěvky: 126
Pozice: nadšený student, který se má více učit
Reputace:   3 
 

Asymptotická těsná mez

Dobrý večer,

nevím zda jsem správně pochopil princip asymptotické těsné meze. Definice říká:

$(\exists C_1, c_2) (\exists n_0 \in N^+) (\forall n > n_0): c_1 * g(n) \le f(n) \le  c_2 * g(n)$

Jak mohu těsnou mez aplikovat na algoritmy? Například hledání maximálního prvku v matici zabere (při dvojnásobné interaci) - pro tu je tedy těsná mez jasná a také rovna .

Jak to bude s algoritmem pro vyhledávání prvku např. opět v matici (s vyhodnocením je / není prvek v matici) může trvat či také celých . Pro tento algoritmus poté neexistuje těsná mez?

Offline

  • (téma jako vyřešené označil(a) mb305)

#2 11. 10. 2012 20:53

JohnPeca18
Příspěvky: 651
Škola: MFF UK
Pozice: Absolvent 2014
Reputace:   81 
 

Re: Asymptotická těsná mez

I kdyz to je tesna mez, stejne odhadujes ten nejhorsi pripad. Jenom ho odhaduje presneji. V tvych pripadech co si napsal, tak i odhad $O(n^3)$ by byl pravdivy ale nebyla by to tesna mez.

Offline

 

 

Stránky: 1

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson