Aufwand für Algorithmen

Also ich habe 2 Teilfragen:

1. Wenn ich einen Sortieralgorithmus gegeben habe aus was berechnet sich der Aufwand überhaupt... Anzahl der Vergleiche? oder Anzahl der Tauschoperationen oder die Summe aus beidem? irgendwie kommt es mir vor als wenn immer nur die Anzahl der Vergleiche gezählt wird.

2. Ein Algorithmus habe den Aufwand O( n log n)
ZU welcher Basis ist denn dieser Logarithmus? oder ist das nebensächlich da es eher um die Tendenz geht? Oder der 2-er Logarithmus...

ich habe nämlich in einer Mitschrift eines Freundes gelesen dass der mittlere Aufwand von Qucicksort O(n ln n) sei ... ich lese aber sonst überall n log n ohne basisangebe

SG1

shisha schrieb:

1. Wenn ich einen Sortieralgorithmus gegeben habe aus was berechnet sich der Aufwand überhaupt... Anzahl der Vergleiche? oder Anzahl der Tauschoperationen oder die Summe aus beidem? irgendwie kommt es mir vor als wenn immer nur die Anzahl der Vergleiche gezählt wird.

Anzahl der Operationen insgesamt. Da aber bei Sortieralgorithmen immer Anzahl der Vergleiche > Anzahl der Tauschoperationen gilt, kann man letztere vernachlässigen.

2. Ein Algorithmus habe den Aufwand O( n log n)
ZU welcher Basis ist denn dieser Logarithmus? oder ist das nebensächlich da es eher um die Tendenz geht? Oder der 2-er Logarithmus...

Ist nebensächlich, da es nur um die Tendenz geht.

Heinzelotto

shisha schrieb:

Also ich habe 2 Teilfragen:
2. Ein Algorithmus habe den Aufwand O( n log n)
ZU welcher Basis ist denn dieser Logarithmus? oder ist das nebensächlich da es eher um die Tendenz geht? Oder der 2-er Logarithmus...

ich habe nämlich in einer Mitschrift eines Freundes gelesen dass der mittlere Aufwand von Qucicksort O(n ln n) sei ... ich lese aber sonst überall n log n ohne basisangebe

Wenn du einen beliebigen $\log_{unbekannte\_basis}x$ hast, kannst du ihn in $\log_2x$ umwandeln, indem du durch $\log_{unbekannte\_basis}2$ teilst. Und wie du sicher weißt, fallen konstante Faktoren in der O-Notation weg, deshalb beschreiben beide logs die gleichen Mengen.
Achtung: das geht nur zufällig bei log so: $4^n$ ist eine andere komplexitätsklasse als $2^n$ , genauso wie ja $n^2$ etwas anderes ist als $n^3$ ; nicht einfach stur zahlen durch andere ersetzen