c - 求函数 "foo"的时间复杂度

Question

我正在努力寻找这个函数的时间复杂度:

void foo(int n) {
    int i, m = 1;
    for (i = 0; i < n; i++) {
        m *= n; // (m = n^n) ??
    }
    while (m > 1) {
        m /= 3;
    }
}

好吧，第一次迭代显然是O(n^n)，对它的解释是因为m从值1开始，并且自相乘 n 次。

现在，我们从 m = n^n 开始 while 循环，每次除以 3。这意味着，(我猜)log(n^n)。

假设我到现在为止都做对了，我不确定我是否需要求和或乘法，但我的逻辑是我需要对它们求和，因为它们对每个都是“奇数”其他。

所以我的假设是:O(n^n) + O(log(n^n)) = O(n^n) 因为如果 n 很大，我们可以避免O(log(n^n))。

好吧，我在这里确实做了很多假设，我希望这是有道理的。我很想听听您对此函数的时间复杂度的看法。

Answer 1

理论上，时间复杂度是 O(n log n) 因为:

for (i=0; i<n; i++) 
   m *= n;

这将执行 n 次，最后 m=n^n

然后这个

while (m>1)
   m /= 3;

将执行 log3(n^n) 次，即 n * log3(n):

P.S. 但这只是在计算操作次数的情况下。在现实生活中，计算 n^n 需要更多时间，因为数字变得太大了。当您乘以如此大的数字时，您的函数也会溢出，并且很可能您将受到 int 最大数量的限制(在这种情况下，复杂度将为 O(n))