Mam pewne pytanie dot. algorytmów:) Otóż, mam kilka zadań z algorytmiki, w których wypadałoby oszacować złożoność i powiedzieć, na jakiej podstwie twierdzę, że złożoność jest akurat taka a nie inna. Nigdy nie robiłam tego typu rzeczy, mógłby mi ktoś pomóc, jak w ogole zacząć ? Dla przykładu - powiedzmy mam alg. grafowy, niech będzie Dijkstra. Mam też określoną reprezentację grafu no i algorytm który używa konkretnych struktur danych. Teraz pytanie - jak to udowodnić, że napisałam program, który ma dokładnie taką złożoność ? :)
0
0
Podam Ci wytłumaczenie "na chłopski" rozum, jeśli chcesz. Po prostu od studiów się w to nie bawiłem i w głowie mam tylko resztki.
Złożoność to innymi słowy informacja "ile razy algorytm przemieli dane zanim skończy", albo "ile dany algorytm wykonuje porównań",
na przykład gdy masz nieposortowany ciąg liczb i algorytm znajduje maksimum mniej więcej tak:
liczby = [2,4,1,3,6,7,3,2,4,6,34,2,43,6,5,3,....];
maks = liczby[0];
for(i=1; i<rozmiar_tablicy(liczby); i++){
if(liczby[i] > maks){
maks = liczby[i];
}
}
print maks
Jeśli prześledzisz działanie to zauważysz, że lecimy przez tablicę dokładnie raz w jedną stronę, więc algorytm ma złożoność liniową "n", oznaczamy to O(n), wykonuje n (n to rozmiar tablicy) porównań.
Inny przykład - ta sama tablica, ale tym razem musimy ją posortować. Jeśli zastosujesz na przykład sortowanie bąbelkowe, to w pierwszym przebiegu wykona n porównań, w drugim n-1, czyli złożoność czasowa wygląda tak: n+(n-1)+(n-2)+... . Jednak w złożoności nie chodzi o dokładny wynik, ale raczej o klasę złożoności w jakiej algorytm się mieści i w tym przypadku niewiele się zmienia, jeśli pominiesz stałe i napiszesz n+n+n... (n razy) czyli n2, czyli O(n2)
Jeśli masz dalej pytania - podaj może przykładowy algorytm z zadania.
0
Na chłopski rozum - czemu nie ;) Dla mnie najważniejsze jest, żeby jak najlepiej to zrozumiała :) Więc tak - pytałeś o przykład, jedno z 8 zadań dotyczyło Dijkstry i należało ją zaimplementowac w taki sposób, aby otrzymać złożoność O(|E|* log|V|) - (V = l.wierzchołków, E = l. krawędzi). Nie chciałabym umieszczać tu swojego kodu, podam może tylko pseudokod, moje przemyślenia, i może ktoś oceni, czy dobrze to zrozumiałam :p
- Wrzuć do kolejki priorytetowej pierwszy wierzchołek (startowy)
- Dopóki kolejka nie jest pusta wykonuj poniższe podpkty:
a) zdejmij z kolejki wierzchołek "u" o najmniejszej wadze krawędzi (następnie usuń ten wierzchołek z kolejki)
b) jeśli zdjęty wierzchołek był nieodwiedzony
- w pętli for, idąc po jego sasiadach, jeśli nie byli odwiedzeni i spełniona jest zależność
typowa dla alg. Dijkstry - dokonaj relaksacji wierzchołków - wrzuć na kolejkę wierzchołek - sasiada wierzchołka "u", który nie był odwiedzony i na którym dokonaliśmy relaksacji
c) oznacz wierzchołek "u" jak odwiedzony
Więc wg mnie - zaimplementowałam teg alg. w sposób poprawny - wszystkie użyte operacje na kolejce priorytetowej (pop,push,top) wykonywane są w czasie stałym - więc o to za bardzo nie muszę się martwić. W pętli for idę po sasiadach, czyli de facto po krawędziach, ponieważ mam strukturę przechowującą numer sąsiada i wagę. (więc mam już O(|E|). Dalej - wierzchołki "obrabiam" nie wszystkie, tzn. tylko te nieodwiedzone - stąd sprowadzam problem rozmiaru |V| do rozmiaru mniejszego + pewna stała liczba działań (relaksacja). => stąd dostajemy O(|E| * log|V|), ponieważ pętla "po krawędziach" jest wewnątrz pęli while kolejka pusta, dlatego mnożymy.
Oczywiście graf należy repreentowac za pomoca listy sąsiedztwa, ponieważ przy uzyciu macierzy sasiedztwa dla krawędzi miałabym złożoność kwadratową (2 pętle)
Czy takie tłumaczenie jest poprawne ? Prosze o wyrozumiałość i poprawki - nigdy nie musiałam udowadniać złożoności swojego algorytmu ;)
0
Zakładamy, że używamy kopca binarnego - wtedy dostaniemy złożoność o którą pytano.
http://en.wikipedia.org/wiki/Heap_(data_structure)
Na początku tworzymy kopiec, ale wszystkie wierzchołki mają wagę MAX więc można to zrobić liniowo, tzn łączymy wierzchołki w pary, potem pary w pary, itd.
Każda relaksacja to wykonanie operacji decreaseKey zajmującej O(lg n) gdzie n = |V| (czyli nie jest to operacja o stałym czasie), a takich operacji jest co najwyżej tyle co wszystkich krawędzi w grafie czyli |E|.
Wyciągnięcie wierzchołka ze szczytu stosu do operacja extractMin = findMin + deleteMin zajmujące w sumie O(lg n), wszystkich wierzchołków jest n, a więc w sumie samo usuwanie trwa O(n lg n), a skoro n = |V| to wychodzi nam O(|V| lg |V|) na usuwanie wierzchołków z góry.
Sumując dostajemy O(|V| lg |V| + |E| lg |V|) = O(|E| lg |V|).
0
Ale ja muszę użyć (właściwie już użyłam) kolejki priorytetowej, nie kopca. Korzystałam z kolejki priorytetowej z STL'a, gdzie mam podaną złożoność dla konkretnych operacji na takiej kolejce, wszystkie używane przeze mnie mają złożoność stałą :>
0
Kopiec jest jedną z implementacji kolejki priorytetowej:
http://pl.wikipedia.org/wiki/Kolejka_priorytetowa
Bardzo słabo u Ciebie ze znajomością struktur danych ;/
0
Hm, ja wiem, że kolejkę można implementować za pomoca kopca,tablicy, kopca fibonacciego ale przecież nie o to pytam ...
0
To dowiedz się za pomocą czego jest ta kolejka zaimplementowana. Bo kolejka priorytetowa to tylko nakładka na inną strukturę danych.
0
http://www.cplusplus.com/reference/stl/priority_queue/ + inf. o tym, że operacje na niej są w czasie stąłym - czy wtedy mój "sposób" na udowodnienie złożoności będzie poprawny ?
0
Ale gdzie masz info że są w czasie stałym? Jeśli by tak było to priority_queue musiałoby używać jakiegoś supertajnego algorytmu ;p no i wtedy złożoność byłaby mniejsza bo wynosiłaby O(|E|).
Ja tam np widzę na cplusplus.com:
Priority queues are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are popped from the "back" of the specific container, which is known as the top of the priority queue.
The underlying container may be any of the standard container class templates or some other specifically designed container class. The only requirement is that it must be accessible through random access iterators and it must support the following operations:
front()
push_back()
pop_back()
Pisze jak byk, że wydajność priority_queue zależy od wydajności kontenera pod spodem.
A na http://www.sgi.com/tech/stl/priority_queue.html na dole pisze:
Notes
[1] Priority queues are a standard concept, and can be implemented in many different ways; this implementation uses heaps.
0
No ja mam coś takiego:
priority_queue<element, vector<element>,strukturaSortujaca> Q;
A przy operacji np. top() dla priority_queu, przy założeniu, że standardowo używa się wektora, :
Complexity: Constant
0
Podaj linka.
Poza tym przy użyciu wektora czas wzrasta do O(|V| ^ 2).
0
Spoko. Tu się zgadzam. Ale:
http://www.cplusplus.com/reference/stl/priority_queue/pop/ napisał:
Complexity
Constant (in the priority_queue). Although notice that pop_heap operates on logarithmic time.
Operacja pop zajmuje czas stały + czas na wykonanie pop() na wewnętrznym kontenerze. Tak samo push.
Wyciąg z stl_queue.h:
/**
* Returns a read-only (constant) reference to the data at the first
* element of the %queue.
*/
const_reference
top() const
{
__glibcxx_requires_nonempty();
return c.front();
}
/**
* @brief Add data to the %queue.
* @param x Data to be added.
*
* This is a typical %queue operation.
* The time complexity of the operation depends on the underlying
* sequence.
*/
void
push(const value_type& __x)
{
c.push_back(__x);
std::push_heap(c.begin(), c.end(), comp);
}
/**
* @brief Removes first element.
*
* This is a typical %queue operation. It shrinks the %queue
* by one. The time complexity of the operation depends on the
* underlying sequence.
*
* Note that no data is returned, and if the first element's
* data is needed, it should be retrieved before pop() is
* called.
*/
void
pop()
{
__glibcxx_requires_nonempty();
std::pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
0
Już się gubię ;-P ale powoli ...
Podsumowując to jakoś, odwiedzenie wierzchołków sasiadów zajmuje mi O(|E|) (relaksacja), natomiast usunięcie wierzchołka top to log(|V|) - nie musimy szukac topa, bo jest zawsze na początku, dzięki strukturze wyznaczającej priorytet kolejki. Czy tak ? Więc wychodzi na to, że ten log wcale nie bierze się z tego, że utrzymuje tablice odwiedzonych/nieodwiedzonych wierzchołków, ale z czegoś innego ... (wcześniej napisane) pff .. rozumiem już to dobrze ? :d
Aha ! ->
The time complexity of the operation depends on the underlying sequence.
więc o to chodzi
0
Nie rozumiesz.
Top to odwołanie do najmniejszego / największego elementu (zależy jak chcemy). Przy kopcu zajmuje zawsze czas O(1) bo ten element jest na początku. Jeśli chcemy go usunąć to zajmie nam to czas O(lg n) ponieważ musimy go zastąpić elementem z końca a potem przesunąć w dół tak, aby wszedł na właściwe miejsce. Wysokość kopca to lg n, a więc czas tej operacji to O(lg n). Operacja push i pop zajmują także po O(lg n) czasu. Relaksacja z tego co się orientuję to będzie najpierw pop(), potem zmiana klucza, a na końcu push() z powrotem.
Jeśli korzystamy z wektora, to operacja top() na wektorze to raczej zajmuje czas liniowy, a nie stały. Reszta operacji zajmuje wtedy czas stały. No chyba, że to będzie posortowany wektor, wtedy top() zajmie czas stały, ale za to reszta operacji zajmie czas liniowy.
EDIT:
Aha ! ->
The time complexity of the operation depends on the underlying sequence.
więc o to chodzi
Uff, wreszcie :)
Przeczytałem post z góry:
W pętli for idę po sasiadach, czyli de facto po krawędziach, ponieważ mam strukturę przechowującą numer sąsiada i wagę. (więc mam już O(|E|). Dalej - wierzchołki "obrabiam" nie wszystkie, tzn. tylko te nieodwiedzone - stąd sprowadzam problem rozmiaru |V| do rozmiaru mniejszego + pewna stała liczba działań (relaksacja). => stąd dostajemy O(|E| * log|V|), ponieważ pętla "po krawędziach" jest wewnątrz pęli while kolejka pusta, dlatego mnożymy.
To się totalnie kupy nie trzyma. Możesz powiedzieć o co Ci tutaj chodziło? Ten log |V| tutaj wzięłaś z kapelusza.
0
Oj ;-P mówiłam, że robię to pierwszy raz ;)
Ale dzięki Tobie chyba już zaczynam rozumieć:
Relaksacja - należy zrelaksowac wszystkie wierzchołki, więc mamy O(|E|)
Dostep do elem. o max priorytecie - O(1)
Usunięcie elem. o max priorytecie - O(lg(n))
Ponieważ zdejmujemy wierzchołek z góry, należy: znaleźć element o nawiększym priorytecie (O(1)), nastepnie usunąć go - O(lg(n)) ( - czyli w rzeczywistości O(1) * O(lgn)).
Jeśli zrobimy to dla wszystkich wierzchołków - a tak nalezy zrobić - będzie to O(n) * O(lgn), czyli O(n lg n).
Nie bardzo moge jednak jeszcze zrozumieć, dlaczego we wzorze, który podałeś jest : O(|V| lg |V| + |E| lg |V|) = O(|E| lg |V|). Chodzi mi dlaczego pomija się |V| lg |V| i czemu należy wymnożyć |E| lg |V| ?
0
Relaksacja pojedyńczego wierzchołka zajmuje czas O(log |V|) ponieważ musimy przeprowadzić operację decreaseKey zajmującą czas O(lg n) względem wielkości kopca. Relaksacji jest co najwyżej tyle co krawędzi czyli O(|E|). Mnożąć ilość relaksacji O(|E|) przez czas pojedyńczej relaksacji czyli O(log |V|) dostajemy złożoność całego algorytmu.
Jeśli mamy złożoność O(a + b) i a należy do O(b) to złożoność tej sumy należy zapisać jako O(b).
Inaczej rzecz biorąc. O(x) to zbiór funkcji rosnących asymptotycznie nie szybiej niż x. A więc O(a + b) = O(a) + O(b) i jeśli O(a) zawiera się w O(b) to nie ma sensu pisać tego O(a) bo i tak nie zmieni naszej sumy zbiorów.
0
Przeciez masz wyraźnie napisane. Każda relaksacja kosztuje cię O(log|V|) a relaksacji masz tyle co krawędzi, więc O(|E|*log|V|)
Czemu O(|V| lg |V| + |E| lg |V|) = O(|E| lg |V|) ?
Bo z reguły |E| jest znacznie większe od |V| i można wtedy uznac ze |E|+|V| jest prawie równe |E|
0
Ok, chyba już rozumiem :) Jeśli przez relaksację rozumieć operacje push i pop wierzchołków (+ zmiany wag) - odpowiednio O(logn) dla tych operacji, jak pisałeś, więc O(log|V|) - wykonujemy je na wszystkich wierzchołkach , a ponieważ relaksujemy wszystkie krawędzie, a jest ich |E|, stąd O(|E|*log|V|) (Wiem, że przytoczyłam tu znaczną część Waszych postów, ale jak sobie napiszę "swoimi słowami", to jakoś lepiej to rozumiem ;) )
Ok w razie pytań będę pisać w temacie :)
0
Sory ze sie wcinam w temat - ale czy robiac tak jak kolezanka mowi, nie otrzyma innej zlozonosci ? Przeciez musi raz usunac wierzcholek (to juz jest O(lgn), a potem znow dodac, przy relaksacji - ponownie O(lgn), bo trzeba w obu przypadkach przywrocic wlasnosc kopca) - nie wyjdzie O((lg|V| + lg|V|)*|E|) ?
0
O(c * f(x)) = O(f(x))
Poczytaj co to znaczy złożoność.
Przy relaksacji trzeba wierzchołek wyciągnąć, zrelaksować i włożyć z powrotem, czyli trzeba tak robić dla potencjalnie każdej krawędzi. Czyli każdy wierzchołek jest wyciągany ze stosu max 1 raz + tyle razy ile ma wchodzących krawędzi. Oczywiście tyle samo razy jest wkładany, no bo z pustego to i Salomon nie naleje.
0
Dlatego implementacja Dijkstry na stercie Fibonacciego ma mniejszą złożoność - tam relaksacja wierzchołka to O(1) (jeśli już wcześniej był na stercie).