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
#2 09. 06. 2011 14:21 — Editoval TomDlask (09. 06. 2011 17:41)
Re: výpočet složitosti algoritmu
Ahoj, časová složitost by ti měla říkat jak rychle bude daný algoritmus probíhat v závislosti na velikosti vstupu (proměnných).
a)
"první" for cyklus proběhne celkem n*n-krát, pokaždé v něm také proběhne ten "druhý", ten proběhne:
poprvé (i=1) jednou
podruhé (i=2) dvakrát
potřetí (i=3) třikrát
...
po n*n-té (i=n*n) n*n-krát
Samotné přiřazení součtu tedy proběhne (1+2+3+4+...+n*n)-krát.
platí: (1+2+3+4+...+n^2)=0.5*n^2*(n^2+1)=n^4 (asymptoticky)
takže asymtotická časová složitost bude podle mne O(N^4)
Jsem omylný, proto ne vše, co jsem napsal, je zaručeně správně.
468
Offline
#3 09. 06. 2011 17:53
Re: výpočet složitosti algoritmu
b)
Při prvním proběhnutí for cyklu bude j=1, při druhém bude j=4, při třetím j=27, ..., při n-tém j=n^2. V dalším cyklu (while) se j zmenšuje po jednom, takže musí proběhnout jednou, dvakrát, třikrát, čtyřikrát, ..., n^2-krát. Takže:
1+4+27+...+n^2=(1/6)*n*(n+1)*(2n+1), což je n^3 asymptoticky
Takže v druhém případě bude asymptická časová složitost O(N^3)
c)
i se tady vždy zvětší na dvojnásobek, takže roste exponenciálné a čísla n tedy dosáhne za O(log(N))
----
Nejsem si ale stoprocentně jist, zda-li je to správně, kdyžtak by mne tu snad někdo opravil. Na ty ostatní se ještě podívám.
Jsem omylný, proto ne vše, co jsem napsal, je zaručeně správně.
468
Offline
#4 10. 06. 2011 20:27 — Editoval TomDlask (10. 06. 2011 20:27)
Re: výpočet složitosti algoritmu
d) vypíšu si jaké hodnoty proměnné mají a tak určím jak rychle roste i (jak rychle dosáhne n)
i=1
j=1
i=i+j=2
j=1+1=2
i=i+j=4
j=j+1=3
i=i+j=7
j=j+1=4
i=i+j=11
j=j+1=5
i=i+j=16
...
atd.
i tedy roste kvadraticky a dosáhne tak nějakého čísla n v O(sqrt(n)), kde sqrt() značí odmocninu
Bohužel jsem se řešit úlohy, kde se má určit časová složitost, ještě neučil, takže tyto další (pro mne složitější) příklady už nejspíše nedám nějakou jednoduchou úvahou. Mohl bych v nich také udělat chyby (stejně jako v těch úlohách a-d, ale tady by už byly pravděpodobnější). Snad poradí někdo jiný.
Jediná možnost, co mne napadá, je dané algoritmy spustit a pro různé velká n počítat počet průchodů toho nejvíce zanořeného cyklu. Tak se ale podobné úlohy nejspíše neřeší.
Jsem omylný, proto ne vše, co jsem napsal, je zaručeně správně.
468
Offline