循环内部调用递归函数的大O表示
循环内部调用递归函数的大O表示
提问于 2017-01-27 13:52:44
我试图确定几种算法的大O复杂度，并且我很难理解如何对以下代码进行推理：
void recursiveFunc (n)
{
for(int i = 0; i < 8; i++)
{
if (n < maxN)
{
recursiveFunc (n + 1);
}
else
{
for(int j = 0; j < 8; j++)
{
// do some stuff
}
}
}
}我认为这是一个指数，因为递归函数是在循环中调用的。O(8^n)？但我有点不知道该怎么解释。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-01-27 14:27:14
你的小费是正确的。
鉴于这一守则：
var maxN = 16;
var initN = 0;
var count = 0;
function recursiveFunc (n) {
for(var i = 0; i < 8; i++) {
if (n < maxN) {
recursiveFunc (n + 1);
} else {
for(int j = 0; j < 8; j++) {
count++;
}
}
}
}
recursiveFunc(initN);第一次调用发生在n= 0：
8^1调用recursiveFunc (其中n= 1)
调用n=1然后导致: 8^2调用recursiveFunc
..。
调用n= (maxN - 1)则导致: recursiveFunc =>访问其他分支的8^maxN调用，每个调用输入“一些东西”64次。
第一次调用发生在n= 2，maxN = 4：
8^1调用recursiveFunc (其中n= 3)
调用n=3然后导致: 8^2次recursiveFunc调用(其中n= 4)
调用n=4，然后访问其他分支，每次64次。
因此，进入“一些东西”阶段的总数: 64 * (8^(maxN - initN))
O(8^n)
编辑:你可以在这里看到这一点，只需点击“运行片段”，然后点击“测试”按钮。(尝试更大的maxN值可能会使浏览器崩溃)
function test () {
var maxN = parseInt(document.querySelector("#nmax").value);
var initN = parseInt(document.querySelector("#n").value);
var count = 0;
function recursiveFunc (n) {
for(var i = 0; i < 8; i++) {
if (n < maxN) {
recursiveFunc (n + 1);
} else {
for(var j = 0; j < 8; j++) {
count++;
}
}
}
}
recursiveFunc(initN);
document.querySelector("#expectedValue").innerHTML = 64 * (Math.pow(8, maxN - initN));// 64 * (8^(maxN - initN));
document.querySelector("#realValue").innerHTML = count;
}N: <input type=number id=n value=0><br>
NMAX: <input type=number id=nmax value=5><br>
<hr>
Expected value: <span id=expectedValue></span><br>
Real value: <span id=realValue></span><br>
<button onclick="test()">Test</button>
(我还假设initN <= maxN)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41895567
复制相关文章
相似问题
腾讯云开发者
