算法运行时间

Question

你能帮我计算一下这个函数的运行时间吗？

我猜是 O(n log n) n 用于 for 循环，log n 用于 while 循环。

但让我不确定的是 j = j*3。如果它是 j = j/2，那么我就会确定我的答案。

即使是 j = j*3 或 j = j/3，它是否是 log n？

Answer 1

如果是 j = j*3，那么对于 j = j*2，复杂度将只是 O(n*log_3(n)) 而不是 O(n*log_2(n))，因为它们仅相差一个常数因子，该因子将被吸收Big-O 表示法。

来到你的函数，外循环肯定是 O(n) 但内循环并不完全 log_3(n) 每次。它实际上随着每次迭代而减少。扩展将是：

log_3(n) + log_3(n-1) + log_3(n-2) + ... + log_3(1)

由于上面解释的原因忽略碱基，我们可以写成：

log(n) + log(n-1) + log(n-2) + ... + log(1)

一种评估方法是通过 log(n) 对上述每一项进行上限，即

log(n) + log(n-1) + log(n-2) + ... + log(1) <= log(n) + log(n) + log(n) + ... + log(n)
                                            <= n*log(n)

因此，复杂度可以写成O(n*log(n)).

第二种方法如下。重写上面的等式，我们有：
```
log(n) + log(n-1) + log(n-2) + ... + log(1)
= log(n*(n-1)*(n-2)...1)
= log(n!)
```
因此，复杂度当然可以写成O(log(n!))。但是 log(n!) 呢？根据Stirling's approximation、
```
log(n!) ~ n*log(n) - n + O(log(n))
```
请注意，根据维基百科：

It is a very powerful approximation, leading to accurate results even for small values of n.

因此，我可以假设对于 n 的大值（我们真正关心的情况），这将非常准确。显然，在上面的近似中，n*log(n) 的值支配其他项，因此，在 Big-O 表示法中，我可以写：
```
O(log(n!)) = O(n*log(n))
```

Answer 2

嵌套循环的时间复杂度等于innermost语句执行的次数。例如：

   for ( int i = 1; i <= n; i ++ ) {
   for ( int j = 1; j <= n; j ++ ) {
      // O(1) expressions
   }

}

在这种情况下 (log_3(n))，您可以使用像这样的小 C++ 代码对其进行测试：

int main()
{
    const int N = 10;
    int j;
    int count = 0;
    int totalCount = 0;

    for ( int i = 1; i <= N; i++ ) {
        j = i;
        while ( j <= N ) {
            j = j * 3;
            count++;
        }
        std::cout << " " << i <<"th iteration of outer loop : inner loop will iterate " << count << " times" << std::endl;
        totalCount += count;
        count = 0;
    }
    std::cout << "TOTAL COUNT is : " << totalCount << std::endl;
    return 0;
}

你在哪里得到这样的结果：

1th iteration of outer loop : inner loop will iterate 3 times
2th iteration of outer loop : inner loop will iterate 2 times
3th iteration of outer loop : inner loop will iterate 2 times
4th iteration of outer loop : inner loop will iterate 1 times
5th iteration of outer loop : inner loop will iterate 1 times
6th iteration of outer loop : inner loop will iterate 1 times
7th iteration of outer loop : inner loop will iterate 1 times
8th iteration of outer loop : inner loop will iterate 1 times
9th iteration of outer loop : inner loop will iterate 1 times
10th iteration of outer loop : inner loop will iterate 1 times
TOTAL COUNT is : 14

Answer 3

更严格的上限是 O(n)。因为总时间是 ( Sum(i=1 to n) of (log(n/i)) ) = log(n^n/n!) = O(n) 如果重要的话，运行时间实际上是 Θ(n)。

算法运行时间

Algorithm runtime

algorithm

runtime