Anzahl der Elemente key in einem Array mit log(N) Laufzeit

[lennero]

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.

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.

 

[httpdigest]

Darf man Konstanten bei solchen Betrachtungen vernachlässigen?

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).

 

[mihe7]

Dann wäre die Laufzeit

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)).

 

[lennero]

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)).

Ok danke für den Hinweis, dann habe ich wohl die Laufzeit mit der Zeitkomplexität durcheinander gebracht?

 

[mihe7]

Vermutlich, wobei Zeitkomplexität auch als asymptotische Laufzeit bezeichnet wird 😉