Tabela złożoności czasowych

0

Hej,
Zrobiłem tabelę która jest mi potrzebna do szybkiego szacowania złożoności czasowych dla podanych danych wejściowych i czasów.
Nie jestem jednak pewny czy dobrze do rozumuję, a szczególnie nie wiem jak to powinno wyglądać w przypadku złożoności logarytmicznych.
Chodzi o to żeby zamiast przykładowych wartości były wzory które pomogą określić złożoność do podanych danych.

n 1000 2000 3000 4000 8000 10000
O(1) x x x x x x
O(log(n)) x ? ? ? ? ?
O(n) x 2x 3x 4x 8x 10x
O(n2) x 4x 9x 16x 64x 100x
O(n3) x 8x 27x 64x 512x 1000x
O(nlog(n)) x ? ? ? ? ?

Z góry dzięki za pomoc.

1

Jeśli dobrze rozumiem o co pytasz to rozwiązanie jest proste. Musisz najpierw policzyć ile kosztuje wykonanie jednej operacji. Jeśli np. dla wejścia o rozmiarze 1000 i złozoności O(logn) czas wykonania jest M to znaczy że jedna operacja trwała średnio M/log(1000) czyli P=M/10
Teraz chcąc policzyć o ile wzrośnie czas wykonania dla wejscia rozmiaru 10x robimy standardowo log(10x) = log(x)+log(10) = M + ~3*P = M+3M/10 = 13M/10
O to chodziło?

0

Chodzi o to, że jeżeli O(log(100))=x to ile będzie wynosić O(log(200))... itd,analogicznie jak w tabelce n,n2,n3.
Cel jest taki żeby dostając powiedzmy 3 dane wejściowe i odpowiednie im czasy, łatwo określić ich złożoność.

1

Znając własności logarytmów:

\log{an} = \log{a} + \log{n} = \frac{x \log{a}}{\log{n}} + x = x \cdot \frac{1 + \log{a}}{\log{n}}

Gdzie x = O(\log{n}).

Dla O(n \log{n}) będzie analogicznie.

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