Czas działania algorytmu, jak obliczać?

Question

Załóżmy że mamy algorytm o złożoności:
T(n) = O(n^2) i wykonuje zadanie n = 10 w 0.1 sek.
Jaki będzie czas działania dla n = 30?
Czy idąc na logikę 0.3 sek czy należy inaczej to rozwiązać?

Answer 1

Sądzę, że T(n) to po prostu czas wykonania tego algorytmu, więc podstawiasz dane do wzoru.

Edit: Znalazłem coś takiego (prostym językiem): http://edu.i-lo.tarnow.pl/inf/utils/010_2010/0216.php.

Comments

czyli czas to będzie 0.3 sek czy 30 * 30 = 900 czyli 0.9 sek?

---

Napisałem, że wstawiasz to n do wzoru. Nie wiem, co oznacza to O, ale jak je pominiesz, to przy n = 30 masz 30^2 = 900, więc przy T(10) = 0.1 sekundy, T(30) = 0,9 sekundy.

---

Dziękuję, O (omikron) znaczy że funkcja jest ograniczona z góry i to n^2 jest złożonością w przypadku pesymistycznym. Inaczej mówiąc gorzej nie będzie niż n^2