Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Laufzeitkomplexität von Insertion Sort
Autor
Universität/Hochschule Laufzeitkomplexität von Insertion Sort
Makde
Junior Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2020
Mitteilungen: 20
  Themenstart: 2022-07-06

Hallo, ich habe ein Verständnis Problem. In diesem Beispiel wird der Code für eine Sortierfunktion gegeben und auch die minimale, durchschnittliche und maximale Laufzeitkomplexität. Ich kann nachvollziehen, dass die Anzahl von vergleichen bei dem Best-Case Scenario n-1 ist. Ab da, kann ich nicht nachvollziehen, wo die Komplexitäten herkommen. Ich habe auch ein Video zu Laufzeitkomplexität zu genau diesem Algorithmus geguckt, aber die genaue Komplexität (nicht O-Notation) scheint eine andere zu sein. Könnte mir jemand bitte erklären, wo die T_Cm (Laufzeitkomplexität der Vergleiche) und die T_Mv (Laufzeitkomplexität der Bewegungen) herkommt? Ein Fall reicht aus, die anderen versuche ich selbst nachzuvollziehen. Link zu dem Video: https://www.youtube.com/watch?v=0hiSJFeUhj4 https://matheplanet.at/matheplanet/nuke/html/uploads/b/54017_Matdroids1.jpg https://matheplanet.at/matheplanet/nuke/html/uploads/b/54017_matdroids2.jpg MfG Makde


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 3960
  Beitrag No.1, eingetragen 2022-07-07

\quoteon(2022-07-06 21:11 - Makde im Themenstart) Könnte mir jemand bitte erklären, wo die T_Cm (Laufzeitkomplexität der Vergleiche) und die T_Mv (Laufzeitkomplexität der Bewegungen) herkommt? \quoteoff Die $T_{Cm}$ werden ja breits im Text über den Formeln erläutert: In allen Fällen führt die for-Schleife über $i$ zu$$ T_{Cm} = \sum_{i=2}^n C(j) \;, $$wobei $C(i)$ die Zahl der Ausführungen des "$x


   Profil
Makde
Junior Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2020
Mitteilungen: 20
  Beitrag No.2, vom Themenstarter, eingetragen 2022-07-07

Hi Zippy, vielen Dank für deine Antwort, ich glaube, ich habe das jetzt nachvollzogen. Kommt die +2 in dem Text vielleicht aus der Zuweisung, die noch in Zeile 5 stattfindet? MfG Makde


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 3960
  Beitrag No.3, eingetragen 2022-07-07

\quoteon(2022-07-07 20:41 - Makde in Beitrag No. 2) Kommt die +2 in dem Text vielleicht aus der Zuweisung, die noch in Zeile 5 stattfindet? \quoteoff Dann müsste man konsequenterweise auch i++ und j-- mitzählen und käme auf $D(i)=2(C(i)-1)+4=2C(i)+2$.


   Profil
Makde hat die Antworten auf ihre/seine Frage gesehen.

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-2022 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]