Asymptotyczna złożoność algorytmu na grafie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
radi0aktywna
Użytkownik
Użytkownik
Posty: 22
Rejestracja: 10 mar 2013, o 21:17
Płeć: Kobieta
Podziękował: 4 razy

Asymptotyczna złożoność algorytmu na grafie

Post autor: radi0aktywna »

Dzień dobry,
mam problem z oszacowaniem asymptotycznej złożoności obliczeniowej dla pewnego algorytmu:
Algorytm rozwiązuje problem o wielkości n transportując go do grafu \(\displaystyle{ G=(V,E)}\). Koszt transportu danych to \(\displaystyle{ \theta(n\log n), |V| = \theta(n\log n), |E| = \frac{|V|}{2}}\), a wykonanie algorytmu na grafie \(\displaystyle{ G}\) jest liniowe względem wielkości grafu.
Ostatnio zmieniony 30 cze 2018, o 21:46 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Punkt 2.7 instrukcji LaTeX-a. Funkcje matematyczne należy zapisywać: sinus - \sin, logarytm - \log, logarytm naturalny - \ln itd.
ODPOWIEDZ