Algoritmusok futási ideje

Minimum: \(\, mT(n,m)\)

Maximum: \(\, MT(n,m)\)

Gráf bejáró algoritmusok

\(n = |G.V|\) (csúcsok száma)

\(m = |G.E|\) (élek száma)

\(mT(n,m) = \bf{\Theta(n)}\)

\(MT(n,m) = \bf{\Theta(n + m)}\)

\(mT(n,m) = MT(n,m) = \bf{\Theta(n + m)}\)

\(\bf{\Theta(n + m)}\)

Első lépése, a gráf f tömbjének visszafele olvasása, és az alapján való kiírása egy Veremből

\(mT(n,m) \in \bf{\Theta(n)}\)

\(MT(n,m) \in \bf{\Theta(n + m)}\)

Ritka gráf: \(\; T_{Prim}(n,m) \in \bf{O(m \cdot \log n)}\)

Sűrű gráf: \(\; \bf{\Theta(n^2)}\)

Fibonacci kupaccal: \(\; \bf{O(m + n \cdot \log n)}\)

\(T(n,m) \in \bf{O(m \cdot \log n)}\)

ahol a findSet \(\in O(\log n)\) és a makeSet és union \(\in \Theta(1)\)

Listával: \(MT(n,m) \in \bf{O(n^2)}\)

Fibonacci kupaccal: \(\bf{O(n \cdot log(n + m))}\)

\(MT(n) \in \bf{O(n \cdot m)}\)

\(mT(n) \in \bf{\Theta(n^2)}\)

\(MT(n) \in \bf{\Theta(n^3)}\)

\(\bf{\Theta(n^3)}\)

n: szöveg

m: minta

Ha a minta 1. karaktere egyáltalán nem szerepel a szövegben vagyis minden eltolásnál 1 összehasonlítás:

\(mT(n,m) \in \bf{\Theta((n-m+1) \cdot 1)}\)

Akkor ha minden eltolásnál a minta utolsó karakterénél romlik el az illeszkedés:

\(MT(n,m) \in \bf{\Theta((n-m+1) \cdot m)}\)

Ha a szöveg és a minta diszjunktak:

\(mT(n,m) \in \bf{\Theta\left(\dfrac{n}{m+1}+m\right)}\)

Ha \(T = AA...A \,\) és \(\, P = A...A\):

\(MT(n,m) \in \bf{\Theta((n-m+2) \cdot m)}\)

\(MT(n) = mT(n) = \bf{\Theta(n)}\)