Seite 1 von 1

Asymptotische Komplexität: n²-n

Verfasst: 30. Jun 2016 19:41
von D11
Hallo, ich habe folgende Frage:

Ein Algorithmus erhält als Input eine quadratische Matrix \(n \ x \ n\) und erzeugt damit irgendeinen Output. Während der Erzeugung des Outputs werden alle Instruktionen einmalig oder konstant häufig ausgeführt, nur eine Instruktion / Rechnung wird durch zwei ineinander verschachtelter Schleifen immer k-mal ausgeführt mit \(k = 0.5 \cdot n^2 - 0.5 \cdot n\).

In der Vorlesung wurde einmal (hier vereinfacht) der Satz

\(\max \left \{ f(n),g(n) \right \} \le \ f(n) + g(n) \le 2 \cdot \max \left \{ f(n),g(n) \right \}\)

thematisiert. Damit wurde begründet, dass sich das Maximum zweier Funktionen sowie die Summe zweier Funktionen in der gleichen Komplexitätsklasse befinden. Daraus folgt dann: Ist die Anzahl der ausgeführten Instruktionen abhängig von einem eindimensionalen Polynom, so richtet sich die Komplexitätsklasse nur nach dem größten Exponenten und kleinere Monome werden ignoriert.

Daher würde ich dem Algorithmus die Komplexitätsklasse \(\Theta(n^2)\) zuordnen, da \(0.5 \cdot n² = \max\{0.5 \cdot n², 0.5 \cdot n\}\) ist für alle \(n \in \mathbb{N}\) (bzw. weil 2 der größere Exponent ist) und es sich bei k um eine Summe dieser beiden Funktionen erweitert um jeweils einen Proportionalitätsfaktor handelt. Richtig ist allerdings wohl \(\Theta(n² -n)\). Ist dies so, weil wir es bei \(k = 0.5 \cdot n^2 - 0.5 \cdot n\) nicht mit einer Summe sondern mit einer Differenz / Subtraktion zu tun haben? Oder wodurch ist das begründet?

Für Hilfe vielen Dank im Voraus!

Re: Asymptotische Komplexität: n²-n

Verfasst: 30. Jun 2016 23:08
von Prof. Karsten Weihe
D11 hat geschrieben: Daher würde ich dem Algorithmus die Komplexitätsklasse \(\Theta(n^2)\) zuordnen ... Richtig ist allerdings wohl \(\Theta(n² -n)\).
Beides ist richtig, denn \(\Theta(n² -n)=\Theta(n^2)\). 8)

D11 hat geschrieben: Ist dies so, weil wir es bei \(k = 0.5 \cdot n^2 - 0.5 \cdot n\) nicht mit einer Summe sondern mit einer Differenz / Subtraktion zu tun haben?
Nein, Addition oder Subtraktion macht keinen Unterschied.

KW