Komplexität Algorithmus

[Maultäschle]

Hey🙂

Ich hab diesen Algorithmus bekommen und soll davon die Komplexität angeben, leider bin ich mir nicht so sicher, deshalb wäre ich froh zu hören, was ihr so habt🙂

public void alg2(int n) {
  int result = 1;
  while (result < n) {
    if (result >= n / 2) {
      result = n;
    } else {
      result = result * 2;
    }
  }
}

 

[Maultäschle]

ich han da 0(log (n))

 

[Xyz1]

Deine Vermutung bestätigt sich:

    public static void main(String[] args) {
        System.out.println("alg2   Llog(n)L");
        for (int i = 0; i < 100_000; i++) {
            System.out.println(alg2(i) + "   " + Math.round(Math.log(i) / Math.log(2)));
        }
    }

    public static int alg2(int n) {
        int r = 0;
        int result = 1;
        while (result < n) {
            if (result >= n / 2) {
                result = n;
            } else {
                result = result * 2;
            }
            r++;
        }
        return r;
    }

Exakt geht's leider nicht, da Funktion etwas springt.

 

[Xyz1]

strike, es geht doch exakt, aber das ist schon nicht mehr so toll:

    public static void main(String[] args) {
        System.out.println("alg2   Llog(n)L");
        for (int i = 3; i < 100_000; i++) {
            double d = Math.ceil(Math.log(i - Double.longBitsToDouble(Double.doubleToLongBits(1) - 1)) / Math.log(2));
            System.out.println(alg2(i) + "   " + d);
        }
    }

    public static int alg2(int n) {
        int r = 0;
        int result = 1;
        while (result < n) {
            if (result >= n / 2) {
                result = n;
            } else {
                result = result * 2;
            }
            r++;
        }
        return r;
    }

Alles baut auf Math.log() auf. Also an deiner Antwort ändert das nix, diese ist richtig.

 

[Maultäschle]

Hey🙂
Und noch zu diesem Algorithmus. Ich hab da n*log(n). Passt des?

public int alg5(int n) { 2 if (n == 0) {
}
int i= 1;
intj= n;
while(i<j){
i=i+ 1;
j=j- 1;
}

return alg5(i - 1)+1; 14
}

 

[Xyz1]

Formatier doch bitte richtig. 😉
14?
Auf den ersten Blick ist das nicht zu erkennen.
Rekursion ist im Spiel.
Deswegen nimm das Mastertheorem.

 

[Xyz1]

Bearbeitung: n*log(n) könnte stimmen.

 

[Xyz1]

Moin, n wäre richtig, wenn ich das richtig aufgefasst habe. Hier die Bestätigung:

    static int k = 0;

    public static void main(String[] args) {
        System.out.println("alg5   LnL");
        for (int i = 3; i < 100000; i++) {
            System.out.println(alg5(i) + "  " + k + "  " + ((i / 2 + i / 2) / 2 * 2));
            k = 0;
        }
    }

    static int alg5(int n) {
        if (n == 0) {
            return 0;
        }
        int i = 1;
        int j = n;
        while (i < j) {
            i = i + 1;
            j = j - 1;
            k++;
        }
        return alg5(i - 1) + 1;
    }

Mastertheorem: 1*T(n/2)+n , wäre das. Ich weiß aber nicht, welcher case. 🙁

Sorry, für das, was ich gestern verzapft habe!

 

[Xyz1]

Erklärung steht hier: https://www.quora.com/How-do-I-get-an-upper-bound-for-T-n-T-n-2-+-n