złożoność czasowa

Question

Witam, mam do wypełnienia tabelę a nie mam pojęcia jak się do tego zabrać. Nie wiem jak wypełnić chociaż pierwszą część dla lg(n), czyli zlożoności logarytmicznej, a mam mało czasu na zrobienie tego zadania. Mógłby ktoś wytłumaczyć, chociaż ten pierwszy przykład, żebym dalej mógł już to sam wypełnić? Bardzo dziekuję

Comments

Jeszcze raz.

Algorytm rozwiązania wymaga czasu f(n) mikrosekund.

Dla jakiego N czas wykonania algorytmu o złożoności N będzie wynosił minutę?

Dla N=10, algorytm o złożoności N zajmuje 10 mikrosekund. Dla jakiego N, zajmie mu całą minutę?

Dla N=10, algorytm o złożoności N^2 zajmuje 100 mikrosekund. Dla jakiego N, zajmie mu całą minutę?

etc etc.

---

czyli np. dla 1 sekundy

skoro

1 sekunda to jest 1000000 mikrosekund

więc układam proporcję

10 (czyli moje n)  - 10 mikrosekund
n                            -  1000000

i z tego wychodzi n=100000

dobrze?

---

...nie? Dla algorytmu o złożoności N, wejście o rozmiarze 100 000... zajmuje 100 000us. Nie trzeba tutaj żadnych proporcji liczyć (bo jest dosłownie 1:1), w dodatku jakimś cudem zrobiłeś to źle :( A moje 10 to przecież był tylko przykład.

I w moim przykładzie nie pytałem o sekundę, tylko o minutę.

W każdym razie... dokładnie do tego się to zadanie sprowadza.

Dla jakiego N, algorytmowi o złożoności N problem zajmie ponad godzinę?

Dla jakiego N, algorytmowi o złożoności N^2 problem zajmie ponad minutę?

Dla jakiego N, algorytmowi o złożoności N! problem zajmie ponad rok?

etc

---

mógłbyś wypełnić tą tabelkę dla samego n? w sensie sam drugi wiersz, bo jakoś ciężko mi to zrozumieć, przepraszam, wtedy może lepiej to zrozumiem

---

Nie, najwyżej jeden losowy przykład: złożoność n^3 i 1 godzina. Rozmiar problemu który da się rozwiązać w godzinę to 3301. (bo 3302^3 da ponad 1h w mikrosekundach)