Was für Komplexität hätte ein effizienter Algorithmus, um eine Videodatei bei der Bilder nach Zufall vermischt wurden, wieder in Ordnung zu bringen?
2 Stimmen
2 Antworten
Ich glaube wen man einfach stumpf jede Möglichkeit durch guckt, wäre es n!...
Allerdings gibt es ja bei solch einen Problem auch die Möglichkeit effizienter Ran zu gehen und einfach immer die 2 Bilder zu vergleichen.. dann wäre es n^2.
Was ich meine mitmein 2. Ansatz auf zahlen basiert:
Du hast die Rheinfolge: 2,5,3,1
Dann kannst du ja erst mal die ersten Beine vergleichen 2<5, also bleibt das so, dann die nächste 5>3 und Dan änder sich die reginfokge zu 2,3,5,1...
Es gibt diverse Sortieralgorithmen die eine Laufzeit von n*log(n) haben. Quick Sort zum Beispiel:
https://www.studysmarter.de/schule/informatik/algorithmen-und-datenstrukturen/quicksort/
Wenn sich die Fotos eindeutig zuweisen lassen, dann klar. Aber Gegenfrage: Wenn es das nicht kann, welcher Suchalgorithmus könnte dann sinnvoll entscheiden, an welcher Stelle welches Bild gehört?
Effiziente Sortieralgorithmen haben eine Komplexität von O(n*log(n)). Ich weiß aber nicht, ob es in deinem Beispiel eine sinnvolle Definition von "größer als" gibt.
Das wäre aber eine sehr ineffiziente Sortierung.