函数的大o

zzwlnbp8 于 2021-07-06 发布在 Java

关注(0)|答案(2)|浏览(296)

static void functionF(int n) {
     for (int i = 0; i < n; i++) {
             functionF(n-1);
     }
}

我计算过：
如果n=2，则该函数将再被调用4次。如果n=3，则会多调用15次。如果n=4，则会多调用64次。我正在努力解决一个大的时间复杂性。

2条答案

通过每次调用一个公共静态变量来测试这个函数。如果你想检查某件事做了多少次，你可以在将来这样做。
以（1，4，15，64，325，…）开头的模式是：

a(n) = n(a(n-1) + 1)

或

a(n) = n(a(n-1)) + n

这是一个很奇怪的函数，因为它的递归特性。然而，这是准确的。你也可以从你提供的数字中搜索这个模式。

从复杂性的Angular 来看，完成->o（n！）需要阶乘时间
因为每一步，都会运行上一步指定的次数。注意你的函数和：

function alpha(n){
    for(int i = 0; i < n; n++){
        //Do some stuff
        alpha(i)
    }
}

或

function alpha(n){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // Do some stuff
        }
    }
}

第一个我真的猜不出它的时间，但是比o（n！）第二个是简单的o（n）²), 在任何实际情况下都比o（n！）跑得快