Witam
Dostałem takie zadanie do zrobienia. Tylko za bardzo nie wiem jak się do tego zabrać
Digraf G jest dany w postaci macierzy sąsiedztwa. Zaprojektuj i zaprogramuj algorytm
działający w czasie O(n), który sprawdza, czy G zawiera źródło, czyli wierzchołek, z któ-
rego wychodzą łuki do wszystkich pozostałych wierzchołków, ale nie wchodzi do niego
żaden łuk
Prosiłbym o pomoc :)
Trzy pytania:
kosciuszkobest napisał(a):
Witam
Dostałem takie zadanie do zrobienia. Tylko za bardzo nie wiem jak się do tego zabraćDigraf G jest dany w postaci macierzy sąsiedztwa. Zaprojektuj i zaprogramuj algorytm
działający w czasie O(n)
Tu na pewno O(n)?
I co to jest n?
, który sprawdza, czy G zawiera źródło, czyli wierzchołek, z któ-
rego wychodzą łuki do wszystkich pozostałych wierzchołków, ale nie wchodzi do niego
żaden łuk
A tu na pewno chodzi o "wychodzą łuki"/"żaden łuk", a nie o "wychodzą ścieżki"/"żadna ścieżka"?
Prosiłbym o pomoc :)
Zakładając n - liczba wierzchołków.
Sprawdzasz, że wiersz zawiera n - 1 wartości nie zerowych, a kolumna same zera (n zer).
Złożoność pesymistyczna o(n^2).
MarekR22 napisał(a):
Sprawdzasz, że wiersz zawiera
n - 1wartości nie zerowych, a kolumna same zera (nzer).
Tak, ale to nie będzie w czasie O(n) -- bo musisz przejrzeć całą tablicę -- czyli O(n^2)... Chyba, że n tutaj to coś innego...
na danych rzędu O(n^2) ma wykonywac O(n) operacji
kosciuszkobest napisał(a):
na danych rzędu O(n^2) ma wykonywac O(n) operacji
Samo przejrzenie danych rzędu O(n^2) jest rzędu O(n^2), więc jak ma to zrobić w czasie O(n)?
koszalek-opalek napisał(a):
kosciuszkobest napisał(a):
na danych rzędu O(n^2) ma wykonywac O(n) operacji
Samo przejrzenie danych rzędu O(n^2) jest rzędu O(n^2), więc jak ma to zrobić w czasie O(n)?
Na tym chyba polega ten problem, jak zdecydować które dane są niepotrzebne?
enedil napisał(a):
koszalek-opalek napisał(a):
kosciuszkobest napisał(a):
na danych rzędu O(n^2) ma wykonywac O(n) operacji
Samo przejrzenie danych rzędu O(n^2) jest rzędu O(n^2), więc jak ma to zrobić w czasie O(n)?
Na tym chyba polega ten problem, jak zdecydować które dane są niepotrzebne?
Bez przejrzenia nie zdecydujesz. Więc będzie co najmniej O(n^2) zawsze...
koszalek-opalek napisał(a):
enedil napisał(a):
koszalek-opalek napisał(a):
kosciuszkobest napisał(a):
na danych rzędu O(n^2) ma wykonywac O(n) operacji
Samo przejrzenie danych rzędu O(n^2) jest rzędu O(n^2), więc jak ma to zrobić w czasie O(n)?
Na tym chyba polega ten problem, jak zdecydować które dane są niepotrzebne?
Bez przejrzenia nie zdecydujesz. Więc będzie co najmniej O(n^2) zawsze...
Proszę o dowód, że nie istnieje taki algorytm, któremu wystarczy spojrzeć na O(n) komórek tablicy.
-> przechodzisz po każdym wierzchołku i sprawdzasz czy nie posiada n-1 łuków ( dla n-ilość wierzchołków)
-> Jeżeli tak, to sprawdzasz czy każdy łuk należy do innego wierzchołka ( może być tak, że kilka łuków prowadzi do tego samego wierzchołka.). Jeżeli tak jest to znalazłeś źródło.
No i jest to pesymistyczne n^2, bo lecimy po kazdym wierzchołku i jak znajdziemy to musimy to powtórzyć w celu sprawdzenia łuków.
enedil napisał(a):
koszalek-opalek napisał(a):
enedil napisał(a):
koszalek-opalek napisał(a):
kosciuszkobest napisał(a):
na danych rzędu O(n^2) ma wykonywac O(n) operacji
Samo przejrzenie danych rzędu O(n^2) jest rzędu O(n^2), więc jak ma to zrobić w czasie O(n)?
Na tym chyba polega ten problem, jak zdecydować które dane są niepotrzebne?
Bez przejrzenia nie zdecydujesz. Więc będzie co najmniej O(n^2) zawsze...
Proszę o dowód, że nie istnieje taki algorytm, któremu wystarczy spojrzeć na O(n) komórek tablicy.
Żartujesz? Ale w razie czego @Czitels dał porządny szkic tego dowodu... W drobnym uzupełnieniu -- jeśli nie ma źródła, ale są same "prawia źródła" (bez jednego niezera) lub też jest źródło, ale przeglądane jako ostatnie (a wcześniej "prawie źródła"), to może być sytuacja, że musisz przejrzeć każdy element tablicy, żeby się o tym przekonać. Stąd pesymistyczne O(n^2).