Question

Laufzeitkomplexität von Algorithmen

Aufrufe: 519 Aktiv: 09.03.2023 um 17:20

0

Hallo ich habe bei einer Aufgabe zur Laufzeitkomplexität von Algorithmen ein Problem. Ich habe Folgenden Algorithmus als Pseudocode gegeben:

Input: n ∈ Z, mit n = 2^m

Output: eine gewisse Ausgabe

1: i ← n

2: j ← 1

3: k ← 0

4: while i > 0 do

5: while j < n do

6: while k < j do

7: Eine von {i, j, k} unabhängige Operation;

8: k ← k + 1

9: end while

10: j ← 2 · j

11: end while

12: i ← i − 1

13: end while

14: return Liste der Ergebnisse

Ich soll zeigen das die Laufzeitkomplexität Θ(n^2)

Ich sehe das die erste Schleife O(n) ist da die erste Schleife unabhängig von der zweiten und dritten ist müssten die zweite und dritte also O(n) sein damit der gesamte Algorithmus O(n^2) ist dies sehe ich jedoch noch nicht so wirklich kann mir vielleicht jemand behilflich sein und erklären warum die zweite und dritte Schleife, welche ja nicht unabhängig voneinander sind O(n) ist ?

Teilen Diese Frage melden

gefragt 27.02.2023 um 16:13

henry_99
Punkte: 10

Kommentar schreiben

2 Antworten

mikn · Answer 1 · 2023-02-27T17:12:46Z

0

Erstmal hab ich keine Ahnung, was Du mit "erste Schleife" usw. meinst. Dafür sind die statements ja numeriert, damit man sich da klar und unmissverständlich drüber unterhalten kann.

Ist bei mir zu lange her: Was wird für die Laufzeit gezählt? Nur die Zuweisungsstatements?
Du sollst die Laufzeitkomplexität herleiten, da steht übrigens Theta(n^2), nicht O(n^2). Du sollst nicht von der Lösung rückschließen auf die Laufzeit von Teilen des Algorithmus.

Teilen Diese Antwort melden Link

geantwortet 27.02.2023 um 17:12

mikn
Lehrer/Professor, Punkte: 30

Zu 1. Es geht darum die Laufzeit abzuschätzen in dem man schaut wie viele durchläufe die einzelnen Schleifen brauchen.
Zu 2. ja weiß ich aber spiel das dabei eine Rolle ?

─ henry_99 27.02.2023 um 18:06

Der blöde Editor hat meine Punkte selbst neu numeriert. Es waren Punkt 1,2,3.
Ok, Anzahl Durchläufe = (soweit ich sehe) Anzahl der Zuweisungsstatements. Wären in einer Schleife zwei Statements, wäre das nicht so.
Natürlich spielt theta oder 0 eine Rolle, denn dann geht es eben nicht um abschätzen, sondern genaueres.
Und den Punkt vor 1. ("Erstmal...") hast Du noch nicht geklärt.
Erläutere also Deine Vorüberlegungen unmissverständlich.

─ mikn 27.02.2023 um 18:15

Dann sollten wir denke ich O bestimmen und nicht theta. Aber zu 1. kann ich es dir auch nicht besser sagen ich bin ja selber etwas ratlos. Aber warum ich darauf komme das die erste While Schleife, also die aus Zeile 4, aus O(n) ist liegt daran das sie die Gleichung n-x=0 erfüllen muss wobei x die Anzahl der Schleifen durchläufe ist und damit gilt x = n und sie ist in O(n). aber wie kann ich das in der Art und weise für denn rest begründen?

─ henry_99 27.02.2023 um 18:24

Du kannst es sehr wohl besser sagen, indem Du, wie von mir angeregt, Dich auf die Statement-Nummern beziehst, und zwar "von...bis".
Sinnvollerweise fängt man mit der innersten Schleife an, nicht mit der äußersten.

─ mikn 27.02.2023 um 18:30

Ja aber genau die stellt ja das Problem da

─ henry_99 27.02.2023 um 20:01

Solange Du nicht konkret sagst, was Dein Problem ist, ist es schwer zu helfen.

─ mikn 27.02.2023 um 20:10

Kommentar schreiben

hansenausberlin · Answer 2 · 2023-03-09T17:20:31Z

Es ist sogar O(n^2 * log(n)) und nicht O(n^2). Begründung: Die äußere Schleife läuft n mal, weil i = n und i mit jedem Durchlauf um 1 dekrementiert wird. Die mittlere Schleife hat logarithmische Komplexität, weil j mit jedem Durchlauf verdoppelt wird. Die innere Schleife läuft wiederum (maximal) n mal, weil die Abbruchbedingung k = j = n ist und jeweils um 1 inkrementiert wird. Dadurch ergibt sich eine Komplexität von O(n * log(n) * n) = O(n^2 * log(n)) Ausschlaggebend ist letztlich die Anzahl der Aufrufe im innersten Loop im Worst Case Szenario. Da die hier erwähnte Operation in der inneren Schleife von den Variablen unabhängig ist und am Ende nur die Rückgabe einer Liste erfolgt, können diese (zeitkonstanten) Operationen in der Berechnung vernachlässigt werden. Cool wäre s wenn du nächstes mal den Pseudocode etwas besser formatierst. Konnte man sich in dem Fall ja herleiten wenn man davon ausgeht das du keine Endloschleifen erzeugen willst, aber schön is nicht. ;-)