Złożoność algorytmów - zadanie z treścią

Niech Alg będzie algorytmem, którego złożoność wyraża się pewną funkcją f(n), gdzie n jest rozmiarem danych wejściowych. Czas wykonania algorytmu Alg dla danych rozmiaru x na komputerze K wynosi t sekund.

(*) Ile czasu zajmie wykonanie algorytmu Alg dla danych p krotnie mniejszego na komputerze K?
(**) Jaki jest maksymalny rozmiar danych, jakie algorytm Alg może przetworzyć na komputerze K w ciągu t' sekund?

gdzie:

a) f(n) = lg(n), x=128, t=7, p=2, t'=20, p'=8, x'=512
b) f(n) = n^2, x=4, t=10, p=4, t'=250, p'=5, x'=50

Proszę o wskazówkę czy cokolwiek.

Wyprowadzasz wzór na t:
t = f(x)*C, gdzie C to pewna stała
czyli C = t/f(x)
Obliczasz nowe t dla danych p razy mniejszych
t' = f(x/p)*C
Podstawiasz C
t' = (f(x/p)*t) / f(x)
Czyli w pierwszym przypadku czas zmniejszy się do 6.

Rozumiem, że to są ogólne wzory, które mam zastosować???? Czy można się dowiedzieć gdzieś coś więcej na ich temat?

W zadaniu masz powiedziane, że algorytm ma złożoność f(n).
To oznacza, że czas jego wykonania dla danych o rozmiarze n wynosi C*f(n), gdzie C to pewna stała. To jest jedyny wzór, reszta to tylko przekształcenia.

o_O chłopie mam wrażenie że minąłeś sie z powołaniem. Skoro nie potrafisz tego zrobić to daruj sobie tą informatykę bo to nie dla ciebie, nie ma sie co męczyć nad czymś co cię nie interesuje.
Te zadania wymają jedynie znajomości proporcji, dodawania, odejmowania, mnożenia i dzielenia...

a) * lg(x) = 7 więc ile wyniesie log(x/p) ? log(x/p) = lg(x) - lg(p) = 7-1=6
** lg(D) = 20 => D = 20^2
b) * x^{2 = 10 więc ile wyniesie (x/p)}2 ? (x^{2) / (p}2) = (x^2)/16 = 10/16 = 5/8
** D^2 = 250 => D = 5 V10

Shalom coś chyba jest z Tobą nie tak. Na pewno nie minąłem się z powołaniem to raz. Studia nie robią z człowieka góru zwłaszcza, że tego typu zadań nigdy nie robiliśmy, ani nie widzieliśmy na oczy. Druga strona medalu to taka, że skoro widzisz coś po raz pierwszy to na pewno tego nie potrafisz zrobić, szukasz pomocy bo Einteinem to Ty nie jesteś, a i jemu żona pomagała. Jedyne co zrobiliśmy na ALG to asymptotyczne tempo wzrostu, ale to już raczej nie do mnie pretensje chyba? Nim coś napiszesz nie mierz każdego jedną miarą. Własności logarytmów znam, z matematyki nie omieszkam stwierdzić, że i Ciebie bym czegoś nauczył bo naprawdę moim zdaniem uwierz że wiesz niezbyt wiele jakbym miał coś Ci zarzucić do rozwiązania.

O wzór pytałem, ale jak już pisałem - NIE MIAŁEM TEGO I WIELU RZECZY więc skąd mam wiedzieć. Każdy jest przekonany, że silnia jest np. określona dla liczb naturalnych, ale ja Ci powiem GUZIK!!!

Pozdrawiam i proszę wstrzymywać się z krytyką.

@Poczatkujacy21, stary, to nie algorytmy tylko prosta matematyka, funkcje jednej zmiennej i proporcje są już w gimnazjum. Maturę Giertychowi zawdzieczasz?

licealista, lepiej zdradź swój prawdziwy nick. Nie mówimy o rozwiązaniu chyba tylko o idei, a Ty komu zawdzięczasz maturę z Polskiego? Do Afisk - nie tylko dla liczb naturalnych. Widzę, że szybko tutaj określacie przyszłość. Zapomniało źrebie jak cielęciem było ;) Ja myślałem, że forum służy do pomocy, a nie do afiszowania się swoimi umijętnościami i gardzeniem innymi. Ale guzik z tym :)

@Poczatkujacy21 pierwszy raz w życiu widzę takie zadania na oczy a jakoś nie miałem problemu z jego rozwiązaniem (na moich studiach widocznie uznali ze takie rzeczy są na tyle oczywiste że nie warto czegoś takiego rozwiązywać). Co więcej głowe dam że bardziej rozgarnięty licealista też nie miałby problemu. Ale jak widać to juz takie czasy ze ludzie nie potrafią myśleć. Rozumiem że z góry zakładasz że jeśli nigdy danego typu zadania nie widziałeś to znaczy ze nie jesteś w stanie go rozwiązać? W ogóle próbowałeś czy po prostu przybiegłeś od razu na forum? To już twój chyba 5 temat w tym dziale i każdy z serii "mam poprawkę z ASD a nic nie umiem..."
dygresja: forum służy do DYSKUSJI, a nie "do pomocy". Do pomocy sluży helpdesk...

Nie znasz mnie a już stwierdziłeś ze niewiele wiem? Czy moze wnisokujesz to moim poście który starałem się uprościć na tyle żebyś nawet ty dał radę zrozumieć?
Szybko określamy przyszłość? To nie jest trudne kiedy widzi się kogoś kto studiuje informatykę a jednocześnie nie umie/nie chce mu się szukać odpowiedzi na pewne pytania na własną rękę. W tym zawodzie to jest niestety umiejętność niezbędna. Tak samo jak rozwiązywanie problemów nieszablonowych (tak tak, to są takie rzeczy o których można powiedzieć że "NIE MIAŁEM TEGO I WIELU RZECZY")...

Poczatkujacy21 napisał(a)

Każdy jest przekonany, że silnia jest np. określona dla liczb naturalnych, ale ja Ci powiem GUZIK!!!

Eee, czyli że co? Że silnia nie jest określona dla liczb naturalnych niby :O? Ba, istnieje nawet coś takiego jak funkcja gamma, która rozszerza silnie na rzeczywiste i nawet zespolone.

Nawet nie jesteś pinternet na tyle rozgarnięty aby właśnie wywnioskować z mojego zdania fakt, że NIE TYLKO dla NATURALNYCH.Shalom po raz kolejny mówię, nie szukałem rozwiązania, a wskazówki. Dla mnie akurat oczywiste nie jest że t=f(x)*C i pewnie logicznie można to wyprowadzić/udowodnić za co wezmę się wieczorem. Druga sprawa - napisać, że tego nie miałeś to sobie możesz, ale rzeczywistość jest inna.

Pozdrawiam!

Mylisz się, informatyka jest dla mnie. Nie Tobie oceniać co jest dla mnie. Jeżeli masz problemy z posadą i sam się do niczego nie nadajesz nie obrażaj innych.

Jedno zadanie nie przekreśla powołania. Informatyka to także sieci komputerowe etc. Ale ty tylko widzisz jedno. Skończmy to bo to już jest naprawdę nudne. Dziękuję i pozdrawiam.

Widać, że jesteś beznadziejnym człowiekiem z zewnątrz i wewnątrz po tym co piszesz. Ahhh te niespełnienie zaowodwe prawda?? Kończę ;) Pa

rofl... perełka? "Nie potrafię, bo nie braliśmy tego/nie robiliśmy takich zadań" - tak to może powiedzieć gimnazjalista/licealista, a nie student(niezależnie od kierunku studiów). Studia nie polegają na wkuwaniu, ale na nauce rozwiązywania problemów, wnioskowania, rozwijaniu umiejętności.