Określ złożoność pesymistyczna

Michaju · Post autor: **Michaju** » 29 mar 2011, o 17:40

Określ złożoność pesymistyczna
a) \(\displaystyle{ 3*n\log (n)+\lg (n)}\)

Errichto · Post autor: **Errichto** » 29 mar 2011, o 17:58

\(\displaystyle{ n \cdot log(n)}\)

Michaju · Post autor: **Michaju** » 29 mar 2011, o 19:05

czy dobrze rozumiem:
pesymistyczna złożoność bedzie \(\displaystyle{ O(n\log (n))}\) bo \(\displaystyle{ n\log (n)}\) 'rosnie' szybciej niż \(\displaystyle{ \lg (n)}\) dlatego dla bardzo dużych wartosci n \(\displaystyle{ \lg (n)}\) oraz stała 3 nie będzie miało znaczenia i się je pomija, tak?

Errichto · Post autor: **Errichto** » 29 mar 2011, o 19:14

Stałe się pomija (poza wyjątkami). Jeśli chcesz liczyć stałą musisz też wiedzieć, jak działa np. pierwiastkowanie, itd. czyli ile czasu wszystko się wykonuje, to co piszesz - z ilu elementarnych operacji się składa. Czyli pomijaj.

Dobrze rozumiesz.
Poza tym dla np. \(\displaystyle{ n=1000}\), wyrażenie \(\displaystyle{ nlog}\) będzie rzędu tysięcy, a \(\displaystyle{ lg}\) będzie rzędu dziesiątek. Czyli to pierwsze już dla \(\displaystyle{ n=1000}\) będzie (około, nie obchodzą nas dokładne wartości) sto razy większe.

Michaju · Post autor: **Michaju** » 29 mar 2011, o 19:16

ok, wielkie dzięki