Witam,
Załóżmy, że jest algorytm i potrzebuje on 1 sek. na wyznaczenie wyniku dla rozmiaru danych podanych na wejście wynoszące n = 10. Jak wyliczyć dla tego algorytmu czas potrzebny na obliczenie dla danych n=20 ? Potrzebuję to wyliczyć dla dwóch przypadków tj. "log2n" a także "n". Prosiłbym o napisanie jak wykonać obliczenia dla tych rozwiązań.
Dziękuje za pomoc.
Pozdrawiam,
Mikos32
Regulamin mówi o zakazie zlecania na forum wykonania pracy domowej.
Ale masz tu hinta ode mnie:
jeśli złożoność pewnego algorytmu wynosi O(n2) to dla k-krotnie większych danych wykonuje się on k2 razy dłużej.
To znaczy że jeśli dla danych X wykonuje się 1 sekundę, to dla danych 2*X wykonuje się 2^2 = 4 razy dłużej.
Shalom napisał(a)
Regulamin mówi o zakazie zlecania na forum wykonania pracy domowej.
Ale masz tu hinta ode mnie:
jeśli złożoność pewnego algorytmu wynosi O(n2) to dla k-krotnie większych danych wykonuje się on k2 razy dłużej.
To znaczy że jeśli dla danych X wykonuje się 1 sekundę, to dla danych 2*X wykonuje się 2^2 = 4 razy dłużej.
Dzięki ale postępując tym tokiem myślenia dla logarytmu otrzymam takie równanie 
czyli 1 raz szybciej i tutaj mam pytanie bo to będzie 1 sekunda * 1 = 1 sekunda czy o 1 razy dłużej czyli dla tego przypadku 1+1=2 sekundy. Odpowiedz pierwsza wydaje mi się poprawna, a jak jest w rzeczywistości ?
Dzięki za odpowiedź, pozdrawiam
Mikos32
Ech, przełóżmy to więc na ilość operacji wiodących. Jeśli złożoność wynosi n, to znaczy że tyle jest operacji wiodących w zależności od danych wejściowych.
Oznacza to ze dla 2 razy większych danych wejściowych mamy n2 operacji wiodących, ergo 2 razy większy czas.
Jesli więc ilość operacji wiodących wynosi log2(n) to dla danych 2 większych mamy operacji wiodących log2(n*2) = log2(n) + log2(2) = 1 (z danych) + 1 = 2
Shalom napisał(a)
Ech, przełóżmy to więc na ilość operacji wiodących. Jeśli złożoność wynosi n, to znaczy że tyle jest operacji wiodących w zależności od danych wejściowych.
Oznacza to ze dla 2 razy większych danych wejściowych mamy n2 operacji wiodących, ergo 2 razy większy czas.
Jesli więc ilość operacji wiodących wynosi log2(n) to dla danych 2 większych mamy operacji wiodących log2(n*2) = log2(n) + log2(2) = 1 (z danych) + 1 = 2
Skoro tak to dlaczego dla n2 nie zrobiliśmy analogicznie do tego co napisaleś czyli (n*2)2 ?
Co podstawiłeś pod log2(n) że wyszło Ci 1 ? log2(10) ani log2(20) to nie jest 1, a więc ?
:)
o_O Ty chyba coś bierzesz. Dla n^2 zrobliśmy identycznie:
Ilość operacji dla danych n wynosi n^2, czas wykonywania takiej ilości operacji to 1 sekunda, więc dla dwa razy większych danych mamy
(n2)2 = 4 n</sup>2 operacji, czyli 4 razy więcej operacji niż było dla danych n, więc wykona się 4 razy dłużej.
Nie wiem jak prościej to wyjaśnić...
A co do log2(n) to napisałem wyraźnie że biorę to z danych zadania:
algorytm i potrzebuje on 1 sek. na wyznaczenie wyniku dla rozmiaru danych podanych na wejście wynoszące n
Bo złożoność pozwala ci wyznaczyć jedynie to jak zmieni się czas wykonania przy zmianie ilości danych, ale musisz mieć jakis punkt odniesienia.
Przecież my tutaj nie liczymy bezpośrednio log2(10) czy log2(20), bo log2(x) określa nam rząd ILOŚCI OPERACJI wiodących dla danych pewnego rozmiaru. Dodatkowo daną mamy informację o tym ile czasu potrzeba na wykonanie takiej ilości operacji. Nie myl czasu z iloscią operacji.