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