Asymptotische Komplexität: n²-n

Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
D11
Neuling
Neuling
Beiträge: 1
Registriert: 30. Jun 2016 18:46

Asymptotische Komplexität: n²-n

Beitrag von D11 » 30. Jun 2016 19:41

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!

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Asymptotische Komplexität: n²-n

Beitrag von Prof. Karsten Weihe » 30. Jun 2016 23:08

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

Antworten

Zurück zu „AuD: Vorlesung“