是否存在真正的 O(n^n) 算法？

发布于 2024-11-09 20:33:51 字数 370 浏览 4 评论 0原文

有没有真正的时间复杂度为 O(n^n) 的算法，而不仅仅是一个噱头？

我可以创建这样一个算法，例如在 O(n^n) / θ(n^n) 中计算 n^n：（

long n_to_the_power_of_m(int n, int m) {
    if(m == 0) return 1;
    long sum = 0;
    for(int i = 0; i < n; ++i)
        sum += n_to_the_power_of_m(n, m-1);
    return sum;
}

需要超过 4 分钟来计算 10^10）

或者其他方式：是否存在任何问题，其中不能比 O(n^n) 更好地解决吗？

原文

Is there any real Algorithm with a time complexity O(n^n), that isn't just a gimmick?

I can create such an Algorithm, like computing n^n in O(n^n) / Θ(n^n):

long n_to_the_power_of_m(int n, int m) {
    if(m == 0) return 1;
    long sum = 0;
    for(int i = 0; i < n; ++i)
        sum += n_to_the_power_of_m(n, m-1);
    return sum;
}

(needs more than 4 minutes to compute 10^10)

Or other way around: Are there any Problems, which cannot be solved better than in O(n^n)?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

離殇 2024-11-16 20:33:58

也许不是最实际的应用，但仍然很有趣：如果您绘制 n^n 个点（当然是 O(n^n)），并满足以下条件：

形成一个具有 n 个顶点的多边形
从每个顶点开始，形成另一个（较小的）具有 n 个顶点的多边形
重复步骤 2 进行 n 次迭代
仅在第 n 次迭代中绘制点，

您最终会得到一个非常整洁的分形图案，具体取决于用于减小每次迭代的多边形大小的比例因子。

如果 n = 6，这个简单的点绘制算法会生成一个图案，该图案会在点之间的负空间中绘制科赫雪花分形的许多实例（您可以在示例Processing.js 程序中看到这一点）

尝试使用不同的 n 值进行实验和比例因子（尽管由于浏览器性能限制，您可能会被限制在 n = 8 或 9 左右的上限），并且您可以获得此处描述的一些其他分形：https://en.wikipedia.org/wiki/N-flake#Hexaflake

(示例中的六边形称为谢尔宾斯基六边形）

<!DOCTYPE html>

<html>
 <head>
    <title>Sierpinski Hexagon</title>
    <style>
        body {
            background-color: darkblue;
        }
        #canvasDiv {
            margin-left: 1%;
            margin-right: 1%;
            text-align: center;
        }
    </style>
</head>

<body>
    <div id="canvasDiv">
        <canvas id="_canvas"></canvas>
    </div>
</body>
 
<script src="https://cdn.jsdelivr.net/processing.js/1.4.8/processing.min.js"></script>
 
<script>
    var canvasWidth = 900;
    var canvasHeight = 800;
    
    var X = canvasWidth/2;
    var Y = canvasHeight/2;
    
    var N = 6;
    var R = 250;
    
    // For N = 6, Koch snowflake fractal pattern is most clearly visible with scaleDown = 0.42
    // 0.5 is just a plain hexagon
    // 0.45, 0.48, and 0.7 are interesting
    // 0.33 is very crisp, but many dots overlap
    var scaleDown = 0.42;
    
    
    var toRadians = function(degrees) {
        return degrees * Math.PI / 180;
    };
    
    var polygonVertices = function(p, n, centerX, centerY, r, clr) {
        p.strokeWeight(1);
        p.stroke(clr[0], clr[1], clr[2]);
        var theta = 360/n;
        for (var v = 0; v < n; v++) {
            p.point(centerX + r * Math.cos(toRadians(theta * v)), centerY + r * Math.sin(toRadians(theta * v)));
        }
    };
    
    var hyperfactorial = function(p, n, centerX, centerY, r, scaleDownFactor, depth) {
        if (depth == n) {
            polygonVertices(p, n, centerX, centerY, r, [Math.abs(X - centerX) * 500 / canvasWidth, Math.abs(Y - centerY) * 500 / canvasWidth, 255]);
            return
        }
        else {
            var theta = 360/n;
            for (var i = 0; i < n; i++) {
                hyperfactorial(p, n, centerX + r * Math.cos(toRadians(theta * i)), centerY + r * Math.sin(toRadians(theta * i)), r*scaleDownFactor, scaleDownFactor, depth + 1);
            }
        }
    };
    
    var applyProcessing = function(p) {
        p.setup = function() {
            p.size(canvasWidth, canvasHeight);
            p.background(0, 0, 40);
            hyperfactorial(p, N, X, Y, R, scaleDown, 1);
        };
    };
    
    var canvas = document.getElementById("_canvas");
    var pInstance = new Processing(canvas, applyProcessing);
    
 </script>

</html>

Maybe not the most practical application, but still interesting: if you draw n^n dots (which of course is O(n^n)), with the following criteria:

Form a polygon with n vertices
Starting at each of these vertices, form another (smaller) polygon with n vertices
Repeat step 2 out to n iterations
Only draw dots on the nth iteration

you will end up with a really neat fractal pattern, dependent on the scale factor used to decrease polygon size each iteration.

If n = 6, this simple dot-drawing algorithm produces a pattern which draws many instances of the Koch snowflake fractal in the negative space between the dots (you can see this in the example Processing.js program)

Try experimenting with different values of n and scale factors (although you'll probably be limited to upper bound of around n = 8 or 9 by browser performance constraints) and you can get some of the other fractals described here: https://en.wikipedia.org/wiki/N-flake#Hexaflake

(The one in the example is called a Sierpinski hexagon)

<!DOCTYPE html>

<html>
 <head>
    <title>Sierpinski Hexagon</title>
    <style>
        body {
            background-color: darkblue;
        }
        #canvasDiv {
            margin-left: 1%;
            margin-right: 1%;
            text-align: center;
        }
    </style>
</head>

<body>
    <div id="canvasDiv">
        <canvas id="_canvas"></canvas>
    </div>
</body>
 
<script src="https://cdn.jsdelivr.net/processing.js/1.4.8/processing.min.js"></script>
 
<script>
    var canvasWidth = 900;
    var canvasHeight = 800;
    
    var X = canvasWidth/2;
    var Y = canvasHeight/2;
    
    var N = 6;
    var R = 250;
    
    // For N = 6, Koch snowflake fractal pattern is most clearly visible with scaleDown = 0.42
    // 0.5 is just a plain hexagon
    // 0.45, 0.48, and 0.7 are interesting
    // 0.33 is very crisp, but many dots overlap
    var scaleDown = 0.42;
    
    
    var toRadians = function(degrees) {
        return degrees * Math.PI / 180;
    };
    
    var polygonVertices = function(p, n, centerX, centerY, r, clr) {
        p.strokeWeight(1);
        p.stroke(clr[0], clr[1], clr[2]);
        var theta = 360/n;
        for (var v = 0; v < n; v++) {
            p.point(centerX + r * Math.cos(toRadians(theta * v)), centerY + r * Math.sin(toRadians(theta * v)));
        }
    };
    
    var hyperfactorial = function(p, n, centerX, centerY, r, scaleDownFactor, depth) {
        if (depth == n) {
            polygonVertices(p, n, centerX, centerY, r, [Math.abs(X - centerX) * 500 / canvasWidth, Math.abs(Y - centerY) * 500 / canvasWidth, 255]);
            return
        }
        else {
            var theta = 360/n;
            for (var i = 0; i < n; i++) {
                hyperfactorial(p, n, centerX + r * Math.cos(toRadians(theta * i)), centerY + r * Math.sin(toRadians(theta * i)), r*scaleDownFactor, scaleDownFactor, depth + 1);
            }
        }
    };
    
    var applyProcessing = function(p) {
        p.setup = function() {
            p.size(canvasWidth, canvasHeight);
            p.background(0, 0, 40);
            hyperfactorial(p, N, X, Y, R, scaleDown, 1);
        };
    };
    
    var canvas = document.getElementById("_canvas");
    var pInstance = new Processing(canvas, applyProcessing);
    
 </script>

</html>

回复收藏 0 原文