Jakie problemy na wykresach są szybsze (w sensie big-O) do rozwiązania z wykorzystaniem macierzy danych macierzy częstości występowania zamiast bardziej rozpowszechnionych macierzy sąsiedztwa?Macierz padania zamiast macierzy przyległości
złożoność przestrzennych strukturach są:
przylegania: O (V^2) wydajność: O (VE)
w związku z czym struktura częstość oszczędza przestrzeń, gdy istnieje wiele więcej wierzchołków niż krawędzie.
Możesz zajrzeć złożoności czasowej niektórych typowych operacji wykresie:
Znajdź wszystkie wierzchołki przyległe do wierzchołka: Adj: O (V) Inc: O (VE)
Sprawdź, czy dwa wierzchołki są przyległe: ADJ: o (1) Inc: o (E)
Policzyć wartościowości wierzchołku: ADJ: o (V) Inc: o (E)
I tak dalej. W przypadku dowolnego algorytmu można użyć bloków konstrukcyjnych, takich jak powyższe, do obliczenia, która reprezentacja zapewnia lepszą ogólną złożoność czasu.
W ostatecznym rozrachunku użycie jakiejkolwiek matrycy jest wyjątkowo nieefektywne pod względem przestrzennym dla wszystkich wykresów z wyjątkiem gęstych. Polecam, aby nie używać żadnej z nich, chyba że świadomie odrzuciłeś alternatywy, takie jak listy przyległości.
Mam bardzo gęste wykresy, z prawie każdym połączeniem. – psihodelia
Czy nie ma sposobów na wydajne przechowywanie macierzy rzadkiej? – CMCDragonkai
Osobiście nigdy nie znalazłem prawdziwego zastosowania matrycy częstości występowania w konkursie programistycznym lub problemie badawczym. Myślę, że może to być przydatne do udowodnienia niektórych twierdzeń lub do niektórych bardzo szczególnych problemów. Jedna książka podaje przykład "liczenia liczby drzew opinających" jako problem, w którym ta reprezentacja jest przydatna.
Kolejną kwestią związaną z tym odwzorowaniem jest to, że nie ma sensu go przechowywać, ponieważ bardzo łatwo jest obliczyć go dynamicznie (aby odpowiedzieć na to, co zawiera dana komórka) z listy krawędzi.
Może się to wydawać bardziej przydatne w hiper-wykresach, ale tylko wtedy, gdy jest gęsty.
Tak więc moja opinia jest - jest przydatna tylko do prac teoretycznych.
Nie jestem pewien, czy łatwo jest znaleźć górną granicę obliczeniową na podstawie reprezentacji. Większość algorytmicznej złożoności będzie pod względem liczby _ krawędzi lub wierzchołków, a nie reprezentacji podstawowej. Każda dolna granica złożoności ma zastosowanie, niezależnie od tego, czy jest zaimplementowana na papierze i ołówku, czy na komputerze. Czy sądzisz, że jeśli masz na myśli specyficzne klasy problemów, to może wspomniałeś o nich i możemy spróbować to rozgryźć? – Gian
Macierz zachorowalności to MxN, a matryca przyległości to NxN, jeśli N jest bardzo duże, a wykres jest bardzo nieliczny, otrzymamy MxN