| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: 
Lokacija: /sbin/init
|
 Postano: 4:05 ned, 20. 1. 2013 Naslov: |
    |
|
|
Pa, uzastopno mnozenje s brojacem koji u svakom koraku raste za 1, daje faktorijele (s obzirom na realnu aritmetiku, priblizno tocne, ali za relativno veliki argument barem daje tocnije nego cjelobrojna aritmetika). Ne znam sto je tu upitno.
Pa, uzastopno mnozenje s brojacem koji u svakom koraku raste za 1, daje faktorijele (s obzirom na realnu aritmetiku, priblizno tocne, ali za relativno veliki argument barem daje tocnije nego cjelobrojna aritmetika). Ne znam sto je tu upitno.
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: 
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
patakenjac
Forumaš(ica)
Pridružen/a: 23. 10. 2011. (17:34:05)
Postovi: (2F)16
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol:
Lokacija: /sbin/init
|
|
| [Vrh] |
|
patakenjac
Forumaš(ica)
Pridružen/a: 23. 10. 2011. (17:34:05)
Postovi: (2F)16
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol:
Lokacija: /sbin/init
|
| Postano: 3:46 uto, 29. 1. 2013 Naslov: |
|
|
|
Trenutno ne vidim moze li pametnije, a da je kolokvijski jednostavno, no i ovo ce ti dati linearnu slozenost:
[tex](n-k)! = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (n-k) = \frac{1 \cdot 2 \cdot 3 \cdot \cdots \cdot (n-k) \cdot (n-k+1) \cdot \cdots \cdot n}{(n-k+1) \cdot \cdots \cdot n} = \frac{n!}{(n-k+1) \cdot \cdots \cdot n}[/tex].
Po koracima zapisano:
[tex]\begin{align*}
n! &= n!, \\
(n-1)! &= \frac{n!}{n}, \\
(n-2)! &= \frac{(n-1)!}{n-1}, \\
&\ \vdots \\
1! &= \frac{2!}{2}
\end{align*}[/tex]
Dakle, izracunas [tex]n![/tex] (u realnoj aritmetici!) prije nego krenes s Hornerom, a onda u svakom koraku podijelis s cim vec treba:
[code:1]prod = /* tu izracunas n! u jednoj for-petlji, sto je linearno */;
for (...) { /* petlja od Hornera; ne sadrzi druge petlje pa je i to linearno */
p = /* korak Hornera koji koristi prod */
if (k) prod /= k; /* if-om izbjegavamo dijeljenje s nulom u zadnjem koraku */
}[/code:1]
Petlja [color=red]u[/color] petlji je kvadratno, ali ovdje imamo petlju [color=green]iza[/color] petlje, sto je linearno po duljini petlji, tj. po [tex]n[/tex].
P.S. Ovisno o vrijednostima [tex]x[/tex] i [tex]n[/tex], ponekad je bolje tako "izvrnuti" racunanje potencija od [tex]x-2[/tex], ali to je -- po meni -- solidno iznad razine kolokvija.
Trenutno ne vidim moze li pametnije, a da je kolokvijski jednostavno, no i ovo ce ti dati linearnu slozenost:
[tex](n-k)! = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (n-k) = \frac{1 \cdot 2 \cdot 3 \cdot \cdots \cdot (n-k) \cdot (n-k+1) \cdot \cdots \cdot n}{(n-k+1) \cdot \cdots \cdot n} = \frac{n!}{(n-k+1) \cdot \cdots \cdot n}[/tex].
Po koracima zapisano:
[tex]\begin{align*}
n! &= n!, \\
(n-1)! &= \frac{n!}{n}, \\
(n-2)! &= \frac{(n-1)!}{n-1}, \\
&\ \vdots \\
1! &= \frac{2!}{2}
\end{align*}[/tex]
Dakle, izracunas [tex]n![/tex] (u realnoj aritmetici!) prije nego krenes s Hornerom, a onda u svakom koraku podijelis s cim vec treba:
| Kod: | prod = /* tu izracunas n! u jednoj for-petlji, sto je linearno */;
for (...) { /* petlja od Hornera; ne sadrzi druge petlje pa je i to linearno */
p = /* korak Hornera koji koristi prod */
if (k) prod /= k; /* if-om izbjegavamo dijeljenje s nulom u zadnjem koraku */
} |
Petlja u petlji je kvadratno, ali ovdje imamo petlju iza petlje, sto je linearno po duljini petlji, tj. po [tex]n[/tex].
P.S. Ovisno o vrijednostima [tex]x[/tex] i [tex]n[/tex], ponekad je bolje tako "izvrnuti" racunanje potencija od [tex]x-2[/tex], ali to je – po meni – solidno iznad razine kolokvija.
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
|
