złożoność obliczeniowa n!

[nowakq]

Witam,
mam problem z zadaniem \(\displaystyle{ f\left( n\right) = \left( n!\right)}\)
czy złożoność obliczeniowa będzie \(\displaystyle{ O\left( n\right)}\) ponieważ \(\displaystyle{ n!= C \cdot n}\)
czy może \(\displaystyle{ O\left( n!\right)}\)?

[Kartezjusz]

\(\displaystyle{ O(a_{n})=b_{n}}\)oznacza,że \(\displaystyle{ b_{n}}\) ma taką samą granicę jak
\(\displaystyle{ a_{n}}\) i tak samo szybko będzie ją osiągał. Czyli ta druga możli wości,bo n! rośnie szybciej niż n...

[Xitami]

czy f(n) = n! ?
to znaczy, czy masz oszacować koszt liczenia silni?
Jeżeli tak, to żadna z odpowiedzi nie jest prawdziwa
Prawda jak to zwykle, leży gdzieś pośrodku.

[pawels]

\(\displaystyle{ O(a_{n})=b_{n}}\)oznacza,że \(\displaystyle{ b_{n}}\) ma taką samą granicę jak
\(\displaystyle{ a_{n}}\) i tak samo szybko będzie ją osiągał. Czyli ta druga możli wości,bo n! rośnie szybciej niż n...

Pytanie tylko co znaczy sformułowanie "będzie ją tak samo szybko osiągał". Jest kilka konwencji stosowania tej notacji, ale ta chyba najbardziej powszechna mówi że \(\displaystyle{ f=O(g)}\) (lub \(\displaystyle{ f\in O(g)}\) gdy istnieje taka stała \(\displaystyle{ c>0}\), że dla dostatecznie dużych argumentów \(\displaystyle{ n\quad f<cg}\).

Co do czasu liczenia silni to uczono mnie że złożonością algorytmu nazwiemy liczbę N operacji mających tę cechę, że wszystkie pozostałe wykonamy co najwyżej kN razy dla pewnego ustalonego k (zależy tylko do algorytmu a nie od rozmiaru danych).

Jeżeli będziesz stosował zwykły rekurencyjny algorytm to operacją dominująca będzie mnożenie, więc wykonasz około n mnożeń więc złożoność wyniesie \(\displaystyle{ n=O(n)}\). Jeżeli natomiast chcesz liczyć bardzo duże silnie tylko z jakąś dokładnością np. za pomocą wzoru Stirlinga to złożoność będzie inna (można np. potęgować szybciej niż w najbardziej narzucający się sposób).

[Xitami]

koszt przybliżonych obliczeń to O(1) bo zmiennoprzecinkowe potęgowanie, pierwiastek czy logarytm wykonuje żelastwo w czasie niezależnym od argumentu
w metodach dokładnych O(n) dokładniej O(n-1) ale tylko wtedy, gdy n! mieści się w słowie maszynowym, ale jeżeli tak to nie warto tego robić mnożąc tylko wykonać to w O(1) (LUT)
jeżeli jednak n! nie "mieści się", o to sprawa się dramatycznie komplikuje
bo wtedy koszt zależy od metody, a najgorszą jest mnożenie kolejnych liczb

naiwny algorytm
\(\displaystyle{ \begin{tabular}{rrl}
n&liczba mnożeń\\ \hline
2 &1&\\
4 &3&\\
8 &7&\\
16 &24&\\
32 &99&\\
64 &452&\\
128 &2 142&\\
256 &102 15&\\
512 &480 91&\\
1 024 &222 562&\\
2 048 &1 013 750&\\
4 096 &4 554 262&\\
8 192 &20 225 416&\\
16 384 &88 958 248\end{tabular}}\)

wygląda na \(\displaystyle{ O\left(n^2\right)}\) bo to naiwny algorytm był

[abc666]

O(n) dokładniej O(n-1)

Ogólnie bardzo ciekawe rzeczy tworzysz w tym wątku.

[Xitami]

jeśli bzdurzę to wskaż i sprostuj proszę, a co do tego -1 to oj czepiasz się

[pawels]

Cóż nie wiem czy w jakimkolwiek standardzie działania zmiennoprzecinkowe wykonują się zawsze tak samo wolno, jednak nie ma to nic wspólnego z problemem ponieważ tutaj powinien być analizowany konkrety algorytm. Wcale nie jest powiedziane w jakiej postaci mają być dane wejściowe- jeżeli jest to zwykła zmienna to możemy robić z nią rożne rzeczy- np. bezmyślnie mnożyć nie przejmując się, że taka implementacja nie będzie bardzo funkcjonalna. Z drugiej strony możemy przechowywać sobie jakieś dane na temat n w jakiś dziwny sposób i jakoś na nich manipulować (np potęgować jakieś liczby, co paradoksalnie może dziać się nie w czasie kwadratowym tylko logarytmicznym). Przede wszystkim złożoność jest cechą algorytmu a nie problemu (chyba że mamy na minimalną, cokolwiek to znaczy, złożoność wszystkich algorytmów rozwiązujących problem, albo coś podobnego).

O(n) dokładniej O(n-1)

(?) Wcale nie dokładniej, bo według definicji z której korzystam \(\displaystyle{ O(n)=O(n-1)}\), przy czym jeżeli posługujesz się inną to chyba warto to zaznaczyć.

[Xitami]

Za minus jeden na klęczkach przepraszam.

czyli poza dzieleniem włosa na czworo to w zasadzie się zgadzamy.