函数的大o

zzwlnbp8  于 2021-07-06  发布在  Java
关注(0)|答案(2)|浏览(315)
static void functionF(int n) {
     for (int i = 0; i < n; i++) {
             functionF(n-1);
     }
}

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

ivqmmu1c

ivqmmu1c1#

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

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

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

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

6yt4nkrj

6yt4nkrj2#

从复杂性的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!)跑得快

相关问题