Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Anzahl der Elemente key in einem Array mit log(N) Laufzeit
Hallo
Gegeben ist ein int Wert key und ein sortiertes int Array. Es soll eine Methode geschrieben werden, die herausfindet wie oft der Wert key im Array vorkommt. Die worst-case Laufzeit soll ~log(N) betragen.
Java:
public static int howMany(int key, int[] a)
{
int lo = 0;
int hi = a.length - 1;
int lowestIndex = -1;
//search for the lowest possible index for key
while(lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if(key > a[mid]) lo = mid + 1;
else if(key < a[mid]) hi = mid - 1;
else if(mid != 0 && a[mid - 1] == key) hi = mid;
else
{
lowestIndex = mid;
break;
}
}
lo = 0;
hi = a.length - 1;
int highestIndex = -1;
//search for the highest possible index for key
while(lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if(key > a[mid]) lo = mid + 1;
else if(key < a[mid]) hi = mid - 1;
else if(mid != a.length - 1 && a[mid + 1] == key) lo = mid + 1;
else
{
highestIndex = mid;
break;
}
}
return highestIndex == -1 && lowestIndex == -1 ? 0 : highestIndex - lowestIndex + 1;
}
Im Grunde genommen wird hier zweimal die Binärsuche durchgeführt, um jeweils den niedrigsten und den höchsten Index für key herauszufinden. Daraus lässt sich dann die Anzahl der Vorkomnisse berechnen. Da immer bis zum jeweils letzten Vorkomniss von key gesucht wird, ergibt sich hierbei die doppelte worst-case Laufzeit der Binärsuche.
Der worst-case in diesem Fall wäre dann 2*log(N). Darf man Konstanten bei solchen Betrachtungen vernachlässigen? Dann wäre die Laufzeit ja immer noch log(N) womit die Aufgabe gelöst wäre.
Ja, das darf man. Additive und multiplikative Konstanten können immer vernachlässigt werden. O(k*f(N) + c) ist also dasselbe wie O(f(N)) - in deinem Fall mit f(N) = log(N).
Nein. Du kennst die genaue Laufzeit nicht, denn die ist von vielen Faktoren abhängig. Nehmen wir mal an, die Laufzeit wäre eine Funktion LZ(n), die für ein System gilt. Auf einem anderen System B könnte die Laufzeit aber doppelt so hoch, also 2*LZ(n) sein. Das darf bei der Betrachtung natürlich keine Rolle spielen.
D. h. die Laufzeit ist nicht log2(n). Was Du hast, ist eine logarithmische Laufzeit, d. h. LZ(n) wächst nicht wesentlich schneller als log2(n). Die Laufzeitfunktion LZ(n) ist damit ein Element von O(log2(n)).
Nein. Du kennst die genaue Laufzeit nicht, denn die ist von vielen Faktoren abhängig. Nehmen wir mal an, die Laufzeit wäre eine Funktion LZ(n), die für ein System gilt. Auf einem anderen System B könnte die Laufzeit aber doppelt so hoch, also 2*LZ(n) sein. Das darf bei der Betrachtung natürlich keine Rolle spielen.
D. h. die Laufzeit ist nicht log2(n). Was Du hast, ist eine logarithmische Laufzeit, d. h. LZ(n) wächst nicht wesentlich schneller als log2(n). Die Laufzeitfunktion LZ(n) ist damit ein Element von O(log2(n)).
