for 循环内部调用的递归函数的大 O 表示法

Question

我正在尝试确定几种算法的大 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）？但我对如何推理它有点迷茫。

Answer 1

你的提示是正确的。

给定代码：

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) then cause: 8^maxN calls of recursiveFunc => visiting else branch, each call enters "some stuff" 64 times

第一次调用发生在 n = 2，maxN = 4 时：

8^1 次 recursiveFunc 调用（其中 n = 3）

调用 n = 3 然后导致：8^2 次调用 recursiveFunc（其中 n = 4）

调用 n = 4 然后访问 else 分支，每次 64 次。

因此进入"some stuff"阶段的总次数：64 * (8^(maxN - initN))

O(8^n)

编辑：您可以在此处看到它的工作，只需单击 "Run the snippet"，然后点击 "Test" 按钮。（尝试更大的 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）

for 循环内部调用的递归函数的大 O 表示法

Big O notation of recursion function called inside for loop

recursion

big-o