Komplexität

[Maggus]

Die nebenstehende
Methode implementiert
die DCT für einen
quadratischen
Ausschnitt eines Bildes
mit n*n Pixeln. Welche
Ordnung hat dieser
Algorithmus bezogen
auf n (Anzahl Pixel pro
Zeile bzw. Spalte)?

public static void dctTransformation(double[][] a,double[][] b){
int n=a.length;
for(int u=0; u<n; u++)
for(int v=0; v<n; v++)
b[u][v] = dctWert(a,u,v);
}
private static double dctWert(double[][] a, int u, int v){
int n=a.length;
double f=0.0;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
f+=a[i][j]*Math.cos(0.5*Math.PI*(double)(u*(2*i+1))/(double)n)
*Math.cos(0.5*Math.PI*(double)(v*(2*j+1))/(double)n);
return f;
}

[/code]

Es sind ja eigentlich vier Schleifen inenander, also dpch eigentlich N^4 oder? Unser Prof meint aber N^2, hat es aber leider nicht mehr erklärt...

Kann mir jemand helfen wie er auf die Lösung kam? Danke!

 

[SlaterB]

also ich stimme dir zu, sieht nach n^4 aus,
Test:

public class Test
{

    public static void main(String[] args)
        throws Exception
    {
        System.out.println("Start");
        test(50);
        test(60);
        test(50);
        test(60);
    }

    static void test(int k)
    {
        double[][] a = new double[k][k];
        double[][] b = new double[k][k];
        int n = a.length;
        for (int u = 0; u < n; u++)
            for (int v = 0; v < n; v++)
                a[u][v] = 1;

        long time = System.currentTimeMillis();
        System.out.println("Test " + k);
        dctTransformation(a, b);
        System.out.println("Ende " + k + ": Zeit: " + (System.currentTimeMillis() - time));
    }

    public static void dctTransformation(double[][] a, double[][] b)
    {
        int n = a.length;
        for (int u = 0; u < n; u++)
            for (int v = 0; v < n; v++)
                b[u][v] = dctWert(a, u, v);
    }

    private static double dctWert(double[][] a, int u, int v)
    {
        int n = a.length;
        double f = 0.0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                f += a[i][j] * Math.cos(0.5 * Math.PI * (double)(u * (2 * i + 1)) / (double)n)
                     * Math.cos(0.5 * Math.PI * (double)(v * (2 * j + 1)) / (double)n);
        return f;
    }
}

Ausgabe bei mir:
Start
Test 50
Ende 50: Zeit: 2266
Test 60
Ende 60: Zeit: 4563
Test 50
Ende 50: Zeit: 2203
Test 60
Ende 60: Zeit: 4703

etwa doppelte Zeit und so habe ich die Zahlen gewählt:
50^4 = 6.25 Mio
60^4 = 13 Mio.

 

[Maggus]

Danke für den schnellen Test. Gruß!