Złożoność obliczeniowa

Noran · Post autor: **Noran** » 16 paź 2011, o 15:30

Cześć. Mam dwa algorytmy, z czego pierwszy ma złożoność obliczeniową na poziomie \(\displaystyle{ O( 100n^{2} )}\), a drugi \(\displaystyle{ O( 2^{n} )}\). Kiedy pierwszy z nich będzie wykonywał się szybciej od drugiego? Dostałem brzydką nierówność, a nie pamiętam sztuczek potrzebnych do jej rozwiązania. Pomóżcie.

\(\displaystyle{ 100n^{2} < 2^{n}}\)

abc666 · Post autor: **abc666** » 16 paź 2011, o 15:40

Tak oryginalnie brzmiało zadanie? Bo z tego, że te algorytmy mają takie złożoności wcale nie wynika, że pierwszy będzie szybszy dla \(\displaystyle{ n}\) będących rozwiązaniem tej konkretnej nierówności. Algorytm wykonujący \(\displaystyle{ 1000000\cdot n^2}\) operacji też jest \(\displaystyle{ O(n^2)}\)

edit
chyba, że tam zamiast \(\displaystyle{ O}\) miało być coś innego?

Noran · Post autor: **Noran** » 16 paź 2011, o 15:59

Oryginalne brzmienie jest inne. Cytuję: Jaka jest najmniejsza wartość n dla której algorytm o złożoności \(\displaystyle{ 100n^{2}}\) działa (na tej samej maszynie) szybciej od algorytmu o złozoności \(\displaystyle{ 2^{n}}\)?

W praktyce więc, jak rozumiem, można sprowadzić to do powyższej nierówności. Próbowałem ją rozwiązać przy pomocy funkcji Omega (Lamberta), ale na nic się to zdało. Algorytm o złożoności 2^{n} zawsze będzie wolniejszy od tego pierwszego, pytanie jedynie - dla jak wielkich liczb.

Xitami · Post autor: **Xitami** » 16 paź 2011, o 19:06

14..16

Noran · Post autor: **Noran** » 16 paź 2011, o 19:36

Nie chodzi o empiryczne sprawdzenie...-- 18 paź 2011, o 00:04 --nikt nie potrafi tego rozwiązać? :/