Twierdzenie o rekurencji uniwersalnej

0

Mam problem ze zrozumiem notacji asymptotycznych
np. T \left( n \right) =2T \left( \frac{n}{2} \right) +n \cdot \lg n

To wtedy jak badamy dla notacji O

Rozumiem że n \cdot \lg n jest wyżej w hierarchii niż n
To mamy n \cdot \lg n \le c \cdot n^{1-e}
i widzimy że f \left( x \right) \not\in O \left( n ^{1-e} \right) dla \exists c,e>0

ale dlaczego no bo jak c=n^2 e=1
to wtedy już jest ok jakie ograniczenia mam nanieść nac i e
No i dlatego nie widzę sensu używania tego c i e więc oczywistym jest że czegoś nie rozumiem
?

3

Nie wiem co próbujesz z robić lub udowodnić bo to co robisz jest bez sensu. Pod c nie możesz wstawić n2 bo c to stała, możesz tam w pisać co cokolwiek np c=10000000000000000000, a ponieważ to c jest stałe to bez problemu można znaleźć odpowiednio duze n by nierówność była prawdziwa, np. c +1. Nie można uzależniać c od n :).

1

@masterkwi c to stała więc z zasady jest NIEZALEŻNA od rozmiaru danych n.

1 użytkowników online, w tym zalogowanych: 0, gości: 1