0 Daumen
136 Aufrufe

Aufgabe:

IMG_0432.jpeg

Text erkannt:

Gegeben ist der nachfolgende Algorithmus.
1. Beschreiben Sie kurz in eigenen Worten, was der Algorithmus macht. Geben Sie der Funktion einen passenden Namen.
2. Analysieren Sie den Algorithmus hinsichtlich der Laufzeit.
function \( f \)
// Input: \( \mathrm{G}=(\mathrm{V}, \mathrm{E}) \), a weighted and directional graph.
\( \mathrm{k}=\mathrm{IVI} \quad / / \mathrm{k} \) is the cardinality of \( \mathrm{V} \)
\( \mathrm{m}=[\mathrm{k}][\mathrm{k}] \) // a matrix with size \( \mathrm{kx} \mathrm{k} \)
for \( \mathrm{v} \) in \( \mathrm{V} \) do:
for \( w \) in \( V \) do:
if \( v \) adjacent to \( w \) :
\( m[v][w]= \) weight \( (v, w) \quad / / \) the weight from \( v \) to \( w \)
return \( \mathrm{m} \)



Problem/Ansatz:

leider keinen

Avatar von

1 Antwort

0 Daumen

zu (1) der Algorithmus erzeugt die Adjazenzmatrix \(m\) des Graphen \(G\). Siehe https://de.wikipedia.org/wiki/Adjazenzmatrix

zu (2) Die Laufzeit ist davon abhängig, wieviele \(w\)'s im Mittel in \(V\) auftreten. Läuft \(w\) in der zweiten Schleife von \(1\) bis \(k=|V|\), dann ist die Laufzeit proportional zu \(k^2\).

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community