Insertion-sort: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) |
Thomas (Diskussion | Beiträge) |
||
| Zeile 57: | Zeile 57: | ||
<math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math> | <math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math> | ||
Für sehr große n können wir den niederwertigen Term cn/2 | Für sehr große n können wir den niederwertigen Term <math>cn/2 </math> und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt: | ||
Der InsertionSort liegt hier in der Komplexitätsklasse O(n2) | Der InsertionSort liegt hier in der Komplexitätsklasse <math>O(n2)</math> | ||
=== Best Case === | === Best Case === | ||
Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. O(n)). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen. | Die optimale Eingabe ist ein bereits sortiertes Array. In diesem Fall hat Insertion Sort eine lineare Laufzeit (d. h. O(n)). Während jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem Element ganz rechts des sortierten Unterabschnitts des Arrays verglichen. | ||