Matematické Fórum

aGr · 04. 06. 2014 20:35 — Editoval aGr (04. 06. 2014 20:36)

Snažím se přijít na řešení rekurentní rovnice $t(n) = 4 t(\lfloor \frac{n}{7} \rfloor) + n+7$ , zadání vyžaduje použití iterační metody.

Můj postupu vede k $\Theta(n \cdot n^{\log_7{4}})$ , avšak správné řešení je $\Theta(n)$ .

Ještě poznámka k poslednímu řádku. Došel jsem k $n^{\log_7{4}} + n \cdot n^{\log_7{4}} - n$ . Protože $\log_7{4} \doteq 0.71$ usoudil jsem, že největší z těchto čísel bude $n \cdot n^{\log_7{4}}$ a ostatní členy jsem zanedbal.

//forum.matweb.cz/upload3/img/2014-06/06307_x.jpg

Předem díky za radu.

vnpg · 05. 06. 2014 10:02 — Editoval vnpg (05. 06. 2014 10:19)

Zdravím,

myslím, že je chyba v té druhé (a tím pádem i třetí) rovnosti. Mělo by být $t(n) = 4 t(\lfloor \frac{n}{7} \rfloor) + n+7 = 4 \left( 4 t( \lfloor \frac{\lfloor\frac{n}{7}\rfloor}{7} \rfloor ) + \lfloor \frac{n}{7} \rfloor + 7 \right) + n + 7 = \cdots$ .

Jeden způsob řešení mě napadá, akorát si nejsem jistý, zda se pro něj dá použít označení „iterační metoda“. Jde o to, že napíšeme $t(n)$ jako teleskopickou řadu $t(n) = t(0) + \sum_{k=1}^n t(k) - t(k-1)$ . Diference $t(k) - t(k-1)$ vycházejí poměrně pěkně, protože závisejí jen na hodnotě $t(0)$ a na tom, jaká je nejvyšší mocnina 7 dělící číslo $k$ a zda existují i jiní dělitelé čísla $k$ než 7.

Rumburak

↑ aGr:

Dejme tomu, že máme počáteční podmínku $t(0) := a$ .
Připadá mi důležité uvědomit si, že na "úseku" $n \in \{7k , 7k+1, ..., 7k+6\}$ je

$4 t(\lfloor \frac{n}{7} \rfloor) + n+7 = 4 t(k) + n+7$ ,
tedy
$t(n) = 4 t(k) + n+7$ ,

což unožní řešit to po těch úsecích.

Bati · 05. 06. 2014 11:26 — Editoval Bati (05. 06. 2014 13:30)

↑ Rumburak:↑ vnpg:
Ahoj,
postup ↑ aGr: je dle mého názoru správně až na drobné nepřesnosti jako, že místo $4^{\log_7{n}}$ by tam mělo být $4^{\lceil\log_7{n}\rceil}$ , nebo rovnou psát $\sim$ místo $=$ . Každopádně platí $\lfloor\frac{\lfloor\frac{n}{7}\rfloor}{7}\rfloor=\lfloor\frac{n}{49}\rfloor$ , $4^{\log_7{n}}=n^{\log_7{4}}$ je také ok, geom. řada ok...vyšlo mi to prostě stejně, tedy $\sim n^{1+\log_74}$ . EDIT: Přehlédl jsem podstatnou věc, viz příspěvek níže.

Tím něříkám, že by se to nedalo řešit přehledněji nebo že by se to nedalo převést na klasickou diferenční rovnici (zavedením jiné vhodné posloupnosti).
EDIT: Nejsnáze asi zavedením $u(k):=t(7^{k+1})$ , vyřešením ( $u(k)=C\cdot 4^k-\frac73(7^k+1)$ ) a vrácením se k původní proměnné , tj. $k=\log_7{n}-1$ .

vnpg · 05. 06. 2014 13:17

↑ Bati:
Ahoj,

díky za upozornění, že $\lfloor\frac{\lfloor\frac{n}{7}\rfloor}{7}\rfloor=\lfloor\frac{n}{49}\rfloor$ . Z nějakého důvodu jsem předpokládal, že je to špatně, což ve skutečnosti není. Pořád ale v řešení od ↑ aGr: vidím problém v tom, že $\lfloor\frac{n}{7}\rfloor \neq n$ pro $n > 0$ . Pokud někde nedělám chybu, tak mi vychází $\Theta(n)$ , takže bych tipoval, že záměna $\lfloor\frac{n}{7}\rfloor$ za $n$ není korektní.

Ve svém postupu jsem nejprve vypočítal diference. Pro $k > 1$ splňující $7 \nmid k$ platí $t(k) - t(k-1) = 1$ , jak plyne i z příspěvku od ↑ Rumburak:.

Nyní uvažujme případ $k = 7^m q$ , kde $m = m(k) \geq 1$ a $q = q(k) \geq 1$ jsou přirozená čísla jednoznačně určená podmínkou $7 \nmid q$ . Potom

$t(k) - t(k - 1) = 4 \left( t(\frac{k}{7}) - t(\frac{k}{7} - 1) \right) + 1$ ,

odkud indukcí podle $m$ získáme

$t(k) - t(k - 1) = 4^m \left( t(\frac{k}{7^m}) - t(\frac{k}{7^m} - 1) \right) + \frac{4^m - 1}{3}$ ,

a v důsleku toho

$|t(k) - t(k - 1)| \leq 4^m C$ ,

kde $C$ je konstanta nezávisící na $k$ . Můžeme vzít např. $C := \max\{1, |t(1) - t(0)|\} + 1/3$ .

Na základě mezivýsledků o diferencích, které jsme právě odvodili, platí

$|t(n)| &= \left| t(0) + \sum_{k=1}^n t(k) - t(k-1) \right| \\ &\leq |t(0)| + nC \left(1 + \frac{4}{7} + \frac{4^2}{7^2} + \cdots \right) \\ &= |t(0)| + \frac{7C}{3} n$ ,

což napovídá tomu, že výsledek je $\Theta(n)$ . Je to jen hrubý postup, ale myslím, že by to mělo fungovat. Ještě by to chtělo několik důležitých věcí doplnit. Zejména je třeba ještě dokázat existenci konstanty $C_1 > 0$ takové, že $t(n) \geq C_1 n$ pro všechna dostatečně velká $n$ .

Brano · 05. 06. 2014 13:20 — Editoval Brano (05. 06. 2014 13:21)

Master Theorem
hovori, ze ked mame $f(n)=n+7\in\Omega(n)$ t.j. $c=1>\log_7 4=\log_b a$ tak potom $t(n)\in\Theta(f(n))=\Theta(n)$ .

Bati · 05. 06. 2014 13:28 — Editoval Bati (05. 06. 2014 13:28)

↑ vnpg:
To, že nahradil $\lfloor\frac{n}7\rfloor$ za $n$ jsem zas přehlédl já a máš tedy pravdu, což jsem si ověřil asi trochu snadněji než ty (viz EDIT). Díky za doplnění.

Brano · 05. 06. 2014 13:48 — Editoval Brano (05. 06. 2014 13:50)

v postupe ↑ aGr: je v hrubych rysoch chyba, ze tam nedelil siedmimi aj n-ka vpravo
takto nejak (nebudem sa zabavat celymi castami a tu zbytocnu konstantu +7 tiez nebudem pisat)

$t(n)=4t(n/7)+n=4(4t(n/49)+n/7)+n=4(4(4t(n7^{-3})+n7^{-2})+n7^{-1})+n=...=$
$=4^{\log_7n}t(1)+n(1+(4/7)+(4/7)^2+...+(4/7)^{\log_7 n})=An^{\log_7 4}+Bn(1-n^{\log_7(4/7)})=$
$=Bn+(A-B)n^{\log_7 4}\in\Theta(n)$

aGr · 05. 06. 2014 15:29 — Editoval aGr (05. 06. 2014 15:35)

Díky všem za příspěvky. Vidím nyní zásadní chybu v tom, že jsem $n$ nedělil 7 stejně jako jsem to dělal v argumentu. Také se mi líbí trik v postupu od ↑ Brano:, kde zahodil celé části i 7.

↑ Brano: Vím, že bych mohl použít Master Theorem, ale zadání vyžadovalo iterační metodu.

Zde tedy můj opravený postup, doufám si tvrdit, že správný:

$t(n) = 4 t(\lfloor \frac{n}{7} \rfloor) + n+7$

Nyní se nejedná o přesné rovnosti (možná bych měl psát $\sim$ ), avšak pro zjištění asymtotické složitosti jsou tyhle změny v pořádku.

$t(n) = 4 t( \frac{n}{7}) + n$

$t(n) = 4 ( 4 t( \frac{n}{7^2} ) + \frac{n}{7} ) + n$

$t(n) = 4 ( 4 ( 4 t( \frac{n}{7^3} ) + \frac{n}{7^2}) + \frac{n}{7} ) + n$

$t(n) = 4 ( 4 ( 4 ... t(0) + \frac{n}{7^{log_7 n}} ) + .... + \frac{n}{7} ) + n$

Předpokládejme, že t(0) = 1.

$t(n) = 4^{log_7 n} + n + 4 \frac{n}{7} + 4^2 \frac{n}{7^2} + ... + 4^{log_7 n} \frac{n}{7^{log_7 n}}$

$t(n) = 4^{log_7 n} + n ( \frac{4}{7} + \frac{4^2}{7^2} + ... + \frac{4^{log_7 n}}{7^{log_7 n}} )$

$t(n) = n^{log_7 4} + n D$

Protože $log_7 4 < 1$ můžu levou část zanedbat a výsledek je:

$t(n) = \Theta(n)$

Brano · 05. 06. 2014 17:20 — Editoval Brano (05. 06. 2014 17:22)

↑ aGr:
btw ak by si chcel to zahodenie konstanty zdovodnit nejak poriadne tak sa to da napr. takto

uvazujme $s(n)=t(n)+k$ kde $k$ je nejaka fixna konstanta, potom
$t(n)=4t(n/7)+n+7$ a teda $s(n)-k=4s(n/7)-4k+n+7$ teda $s(n)=4s(n/7)+n+7-3k$ cize ak zvolime $k=7/3$ tak konstantny clen vypadne a potom vyjde $s(n)\in\Theta(n)$ a teda aj $t(n)\in\Theta(n)$ .

a len taka poznamocka - trochu viac na mieste je podla mna pisat $t(1)$ ale da sa obhajit aj zmysluplnost $t(0)$ tak pouzivaj to co ste mali na prednaske.