c - 先验和渐近复杂度级别

如何确定以下程序代码的先验和渐进复杂性？

#include<stdio.h>


int br_nacina_zaba(int br_lopoca, int tren_poz, int korak) {
    if (korak == 18) return 0;
    else if (tren_poz == br_lopoca) return 1;
    else if (tren_poz <= 0 && korak != 0) return 0;
    else if (tren_poz > br_lopoca) return 0;
    else return
               br_nacina_zaba(br_lopoca, tren_poz + 2, korak + 1)
             + br_nacina_zaba(br_lopoca, tren_poz + 3, korak + 1)
             + br_nacina_zaba(br_lopoca, tren_poz - 2, korak + 1)
             + br_nacina_zaba(br_lopoca, tren_poz - 3, korak + 1);
}

所以我需要知道函数br_nacina_zaba(n,0,0)的复杂性。

最佳答案

我认为br_nacina_zaba(n,0,0)在O（1）中。 （第四个）调用树的最大深度在函数的第一个LOC中受19限制：

korak在每个递归调用中递增。如果从korak=0开始并在每个递归步骤中最多调用4次该函数，则最多将有4 ^ 18个递归调用。 4 ^ 18不依赖于n，因此该函数位于O（1）中。

关于c - 先验和渐近复杂度级别，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5670340/