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

Odpowiedz Nowy wątek
2011-09-02 11:40
0

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.

Pozostało 580 znaków

2011-09-02 12:01
0

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.

edytowany 1x, ostatnio: 0x200x20, 2011-09-02 12:01

Pozostało 580 znaków

2011-09-02 12:07
0

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

Pozostało 580 znaków

2011-09-02 12:09
0

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.

Pozostało 580 znaków

2011-09-02 12:10
0

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)
x2 = 10 więc ile wyniesie (x/p)2 ? (x2) / (p2) = (x^2)/16 = 10/16 = 5/8
** D^2 = 250 => D = 5 V10

edytowany 2x, ostatnio: Shalom, 2011-09-02 12:11
Gość może być z liceum, zadanie jest właśnie na takim poziomie . - 0x200x20 2011-09-02 12:12

Pozostało 580 znaków

2011-09-02 12:20
1

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ą.

"Każdy jest przekonany, że silnia jest np. określona dla liczb naturalnych, ale ja Ci powiem GUZIK!!!" - to znaczy, że nie jest określona dla liczb naturalnych? - Afish 2011-09-02 12:33

Pozostało 580 znaków

2011-09-02 12:27
licealista
0

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

Pozostało 580 znaków

2011-09-02 12:37
0

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 :)

edytowany 3x, ostatnio: Poczatkujacy21, 2011-09-02 12:43

Pozostało 580 znaków

2011-09-02 13:39
0

@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")...

Pozostało 580 znaków

2011-09-02 14:50
0
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.

Pozostało 580 znaków

2011-09-02 16:39
0

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!

Napisałeś wyraźnie że silnia nie jest zdefiniowana dla liczb naturalnych, a jest. Teraz jeszcze próbujesz obrażać innych użytkowników mimo że błąd ewidentnie był po twojej stronie. Trochę pokory... Cóż, skoro lepiej ode mnie wiesz czego się uczyłem a czego nie, to chyba nie ma sensu się w tej kwestii wypowiadać. Ale jeśli nie wiesz skąd wzięło się t=f(x)*C to znaczy ze zwyczajnie nawet 5 minut nie poświęciłeś na przeczytanie co to w ogóle jest złożoność obliczeniowa. Mówiłem, ale powtórze jeszcze raz: mijasz się z powołaniem, bo informatyka nie jest dla ciebie... - Shalom 2011-09-02 16:50

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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