Versuchen Sie, eine Funktion mit Cubed-Protokolllaufzeitkomplexität $ O (\ log ^ 3 n) $ zu schreiben

  • Ich lerne jetzt Datenstrukturen und Algorithmen. Ich habe eine praktische Frage, in der ich gefragt wurde, ob ich eine Funktion mit O schreiben möchte (log 3 n) ) * log (n) * log (n).

     public void run(int n) {
        for (int i = 1; i < n; i *= 2) {
            for (int j = 1; j < n; j *= 2) {
                for (int k = 1; k < n; k *= 2) {
                    System.out.println("hi");
                }
            }
        }
    }
     

    Ich bin mit dieser Lösung gekommen, aber es scheint nicht richtig zu sein. Bitte hilf mir raus.

    19 June 2012
    GillesTimeless
2 answers
  • Ihr Programm ist korrekt. Sie könnten auch Math.Log(n)*Math.Log(n)*Math.Log(n) mal iterieren. Nicht sicher, ob dies als Betrug angesehen wird.

    15 June 2012
    usr
  • Das Folgende ist trivial in der Komplexitätsklasse $ O (\ log ^ 3 n) $:

     public void run (int n) {
        return;
    }
     

    Aber hier ist eine Lösung mit durchschnittlichem und schlechtem Fall von $ O (\ log ^ 3 n) $:

     // O(log(n)), n = |orderedVals|
    int findClosest (int needle, int[] orderedVals) {
        // binary search for closest value and return it
    }
    
    // O(log(n)^3), n = |orderedVals|
    int weirdSum (int initialNeedle, int[] orderedVals) {
        int sum = 0;
        int needle1 = initialNeedle;
        int needle2 = findClosest(needle1, vals);
        for (int i = 0; i < needle2; ++i) {
            int needle3 = findClosest(needle2, vals);
            for (int j = 0; i < needle3; ++j) {
                sum += findClosest(needle2, vals);
            }
        }
        return sum;
    }
     
    20 June 2012
    Thomas Eding