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

Nie masz do tego zadania wykresu? Spójrz na wykres, zobacz do jakiego N wykres nie przekracza 1 minuty, zapisz i tyle?

---

właśnie nie mam wykresu, czyli mam go sobie sam stworzyć? np. dla logarytmicznej będzie mniej więcej taki jak ten czarny(rysunek wzialem z internetu). I teraz właśnie pytanie co mam wpisać w tej pierwszej rubryce czyli lg(n) bo to jest uzależnione od n, a nie mam podanego n, tylko czas(1 sekunda, 1 minuta itd.)

---

a nie mam podanego n

Tak, bo Ty masz podać N. Przeczytaj jeszcze raz treść zadania.

---

okej, widzę że muszę policzyć n, tylko jak to odczytać z wykresu, skoro go nie mam? :/

---

tylko jak to odczytać z wykresu, skoro go nie mam? :/

Ale masz wszystkie funkcje zapisane.

Jeszcze raz, treść zadania (jeśli sam ją dobrze rozumiem):

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

Więc dla N=10, algorytm o złozoności N zajmie 10 mikrosekund, a algorytm o złożoności N^2 zajmie 100 mikrosekund.

---

rozumiem, ale tutaj mam podać największy rozmiar n problemu, czyli jakby to n maksymalne, czyli ono chyba nie będzie wynosiło 10? Jak mam wyliczyć to n dla każdego z tych podpunktów?

---

czyli ono chyba nie będzie wynosiło 10?

...?

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

---

dla n=1?

---

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)