Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Big O ausrechnen
Autor
Universität/Hochschule Big O ausrechnen
arhzz
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.10.2020
Mitteilungen: 129
  Themenstart: 2021-06-20

Hallo! \sourceon Java int a3(int n) { m = 1000 r = 0 for (i = 0 .. n-1) { j = m while (j > 0) { k = n while (k > 0) { r = r + 1 k = k - 1 } j = j / 2 } k = m while (k > 0) { r = r + 1 k = k / 2 } } return r } \sourceoff Also ich soll hier die Laufzeitkomplaxitet ausrechen (Big O) Ich habe schon 3 Laufzeitkomplaxiteten gegeben und ich soll die berechung selben machen und die Laufzeitkomplaxiteten entsprechen zuteilen. Also hier habe ich so gerechnet. for loop -> O(n) while loop -> O(log(m)) while loop -> O(log(n)) while loop -> O(log(m)) Da die 2 erten while loops geschachtelt sind muss ich sie multiplizieren und die letzte muss sich addieren.Da der schnellste Wachstum zahlt sollte die letzte while loop wegfallen also O(n x log(m) x log(n)) Allerdings habe ich so eine Lsg nicht.Die gegebenen Lsg sehen so aus \(O(n × m × log^2(m))\) \(O(n^2 × log(m))\) \(O(n^2\) Also ich habe 3 solche kleine codes und das einzige das mir ubrig bleibt ist dieses \(O(n^2 × log(m))\),die anderen zwei codes habe ich nachgerehcnet und komme auf das selbe.Weiss jemand was ich falsch mache,habe ich ja die anderen zwei vermutlich auch falsch ausgerechnet. Hier die anderen 2 Codes \sourceon Java int a1(int n) { m = 1000 r = 0 for (i = 0 .. n-1) { j = m while (j > 0) { for (k = 0 .. n-1) { r = r + 1 } j = j / 2 } } return r } \sourceoff \sourceon Java int a2(int n, int m) { r = 0 for (i = 0 .. m-1) { for (j = 0 .. n-1) { k = m while (k > 0) { l = m while (l > 0) { r = r + 1 l = l / 2 } k = k / 2 } } k = n while (k > 0) { r = r + 1 k = k / 2 } } return r } \sourceoff bei a1 habe ich \(O(n^2 × log(m))\) zugewisen und bei a2 \(O(n × m × log^2(m))\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
sonnenschein96
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.04.2020
Mitteilungen: 507
  Beitrag No.1, eingetragen 2021-06-20

Hallo arhzz, beachte, dass in der inneren while-Schleife \(k=k-1\) steht und nicht \(k = k/2\). Diese ist somit in der Klasse \(O(n)\) und nicht \(O(\log_2(n))\). Das Ergebnis wäre somit nicht \(O(n\cdot\log_2(m)\cdot\log_2(n))\), sondern \(O(n\cdot\log_2(m)\cdot n)\), falls man \(m\) als Variable auffasst. Da \(m\) hier aber auf \(1000\) gesetzt ist, ist die korrekte Antwort demnach wohl \(O(n^2)\). Analoges gilt für \(a1\). Für \(a2\) ergibt sich dann \(O(m\cdot n\cdot\log_2^2(m))\).


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
arhzz
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.10.2020
Mitteilungen: 129
  Beitrag No.2, vom Themenstarter, eingetragen 2021-06-20

Hallo! Du hast das toll erklart,eine Frage habe ich allerdings.Dann sollte die Komplexitat bei a1 auch O(n^2) sein? Da hier auch m auf 1000 gesetzt ist.Kann es sein dass ich die angabe falsch verstanden habe,weil sie lautet so "Gegeben ist sind mehrere Algorithmen und Komplexitätsklassen. Teilen Sie (i) die jeweiligen Komplexitätsklassen den jeweiligen Algorithmen zu (in Abhängigkeit der jeweiligen Problemgröße) und (ii) überprüfen Sie diese durch eine eigene Berechnung. Weiters, (iii) Dokumentieren Sie Ihre Berechnung in vollständigen Sätzen" Die Komplexitat Klassen sind wie ich schon angegeben habe im Post #1 EDIT: Unser Tutor hat meine Frage beantwortet,es muss nicht unbedingt in der form sein wie in der angabe somit ist es klar. Danke!


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6878
Wohnort: Niedersachsen
  Beitrag No.3, eingetragen 2021-06-22

\quoteon(2021-06-20 21:15 - sonnenschein96 in Beitrag No. 1) Das Ergebnis wäre somit nicht \(O(n\cdot\log_2(m)\cdot\log_2(n))\), sondern \(O(n\cdot\log_2(m)\cdot n)\), falls man \(m\) als Variable auffasst. Da \(m\) hier aber auf \(1000\) gesetzt ist, ist die korrekte Antwort demnach wohl \(O(n^2)\). \quoteoff Achtung, hier gibt es eine kleine Fallgrube. Wenn $m$ eine Konstante größer 1 ist (hier 1000), dann ist \(O(n\cdot\log_2(m)\cdot n)\) und \(O(n^2)\) genau das gleiche. Je nach Kontext könnte man geneigt sein, die eine oder die andere Antwort als "richtiger" anzusehen. Tatsächlich beinhalten beide Komplexitätsklassen aber genau die gleichen Funktionen.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
sonnenschein96
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.04.2020
Mitteilungen: 507
  Beitrag No.4, eingetragen 2021-06-22

@Kitaktus: Mir ist bewusst, dass \(O(\log_2(1000)\cdot n^2)=O(n^2)\) gilt. Ich finde nur, dass die Notation \(O(\log_2(m)\cdot n^2)\) suggeriert, dass man \(O((m,n)\mapsto\log_2(m)\cdot n^2)\) und nicht etwa \(O(n\mapsto\log_2(m)\cdot n^2)\) meint. Ein Problem der Kurznotation ist meiner Meinung nach, dass gar nicht mehr ersichtlich ist, welche Funktion man eigentlich genau betrachtet, da man nur den Wert reinschreibt.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6878
Wohnort: Niedersachsen
  Beitrag No.5, eingetragen 2021-06-22

Es ist nicht unüblich, dass Parameter einer Funktion auch in der O-Notation auftauchen, z.B.: "Wenn k konstant ist, gibt es einen offensichtlichen Algorithmus mit Laufzeit O(nk), um zu entscheiden, ob ein Graph mit n Knoten eine Clique der Größe k enthält." Also obwohl k in diesem Fall keine Variable der Funktion ist, ist es sinnvoll k mit in die O-Notation aufzunehmen. Oder anders formuliert: Nicht alle "Buchstaben", die in einem Funktionsterm auftauchen, müssen unbedingt Eingangsvariablen der Funktion sein (und umgedreht). Mir ging es in meinem Kommentar hauptsächlich darum, dass die Schreibwese $O(n^2\log{m})$ mit $m>1$ konstant, in diesem Fall _nicht falsch_ ist. Wenn man verstanden hat, warum das so ist, hat man auch was gelernt.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]