Das große O berechnen

[NicoBec]

Hi,
ich versuche mir gerade die groß-O Notation beizubringen bzw. in den verschiedenen Algorithmen zu erkennen. Bei ein paar Beispielcodes bin ich mir aber nicht ganz sicher:

    private int indexOf(char[] needle, char[] hay) {
        // Iterate over all possible positions where needle could be found in hay and
        // check if it is indeed there
        for (int i = 0; i <= hay.length - needle.length; i++) {
            if (startsAt(needle, hay, i)) {
                return i;
            }
        }

        // We haven't found anything
        return -1;
    }

Hier hätte ich mit der O(N) Notation gearbeitet, da die Laufzeit nach meinem Verständnis linear von dem Wert hay.length-needle.lengeht abhängt.

public static void sort(int[] arr) {
    for (int i = arr.length - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

Bei diesem Code würde ich sagen, dass es O(N^2) ist, da das ja nichts anderes als eine doppelte for-Schleife ist, nur das die erste runterzählt.

public static int sortedIndexOf(int needle, int[] hay) {
    int lowerBound = 0;
    int upperBound = hay.length - 1;

    while (lowerBound <= upperBound) {
        int mid = (lowerBound + upperBound) / 2;

        if (hay[mid] < needle) {
            lowerBound = mid + 1;
        } else if (hay[mid] > needle) {
            upperBound = mid - 1;
        } else {
            return mid;
        }
    }

    return -1;
}

Bei diesem Code bin ich mir nicht ganz sicher. Intuitiv hätte ich auf O(N) getippt, weil die Performance ja scheinbar linear von der hay.length abhängt. Nach mehrmaligem Testen würde ich allerdings sagen, dass es O(1) ist, da sich die Differenz zwischen lowerBound und upperbound ja mit jedem Durchlauf verringert, also auch nie die gesamte Differenz für die while Schleife genutzt wird. Das Programm gibt zumindest bei einer Array Länge von 200000000 für jeden Wert direkt den jeweiligen Index zurück, ohne Verzögerung.

Ich würde mich freuen, wenn ihr mir eine kurze Einschätzung zu meinem Gedankengang da lasst.
LG

 

[mrBrown]

Hier hätte ich mit der O(N) Notation gearbeitet, da die Laufzeit nach meinem Verständnis linear von dem Wert hay.length-needle.lengeht abhängt.

Ja

Bei diesem Code würde ich sagen, dass es O(N^2) ist, da das ja nichts anderes als eine doppelte for-Schleife ist, nur das die erste runterzählt.

Ja

Bei diesem Code bin ich mir nicht ganz sicher. Intuitiv hätte ich auf O(N) getippt, weil die Performance ja scheinbar linear von der hay.length abhängt. Nach mehrmaligem Testen würde ich allerdings sagen, dass es O(1) ist, da sich die Differenz zwischen lowerBound und upperbound ja mit jedem Durchlauf verringert, also auch nie die gesamte Differenz für die while Schleife genutzt wird. Das Programm gibt zumindest bei einer Array Länge von 200000000 für jeden Wert direkt den jeweiligen Index zurück, ohne Verzögerung.

In jedem Durchlauf teilst du N durch 2, und das so lange, bis 0 ist (außer, der Wert wird eher gefunden).
Das entspricht log(N)

 

[NicoBec]

In jedem Durchlauf teilst du N durch 2, und das so lange, bis 0 ist (außer, der Wert wird eher gefunden).
Das entspricht log(N)

Ahh... vielen Dank, das war das letzte Teil, was mir fehlte. (Y)