algorithm - 这些函数的时间复杂度(渐近地)如何相等？

Question

我知道它们在实际运行时间上有所不同，但使用我无法确定的概念，因为代码在执行时截然不同，所以它们具有相同的时间复杂度。

怎么会

void fun(){
    int i, j;
    for (i=1; i<=n; i++){
        for (j=1; j<=log(i); j++){
            printf("GeeksforGeeks");//prin tit
        }
    }
}

和

void fun2(){
    int i, j;
    for (i=1; i<=n; i++){
        for (j=1; j<=log(n); j++){
            printf("GeeksforGeeks");//print it
        }
    }
}

渐近相同且时间复杂度为 O(logn!)?

Answer 1

fun 的步数是 O(sum of log(i) for i from 1 to n) 与 O(log(n!)) 相同。

fun2 的步数是 O(n log(n))。

现在Stirling's approximation告诉我们这其实是一样的。