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.
Lehrer/Professor, Punkte: 30
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.
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:24Du 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.
Ja aber genau die stellt ja das Problem da
─ henry_99 27.02.2023 um 20:01Solange Du nicht konkret sagst, was Dein Problem ist, ist es schwer zu helfen.
─ mikn 27.02.2023 um 20:10
Markdown wird unterstützt.
Zu 1. Es geht darum die Laufzeit abzuschätzen in dem man schaut wie viele durchläufe die einzelnen Schleifen brauchen.
─ henry_99 27.02.2023 um 18:06Zu 2. ja weiß ich aber spiel das dabei eine Rolle ?