先验且渐进的复杂度级别

Question

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

#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)的复杂度。

Answer 1

在我看来，br_nacina_zaba(n,0,0) 的时间复杂度为 O(1)。在函数的第一个 LOC 中，（四元）调用树的最大深度限制为 19：

korak 在每次递归调用中递增。如果您从 korak=0 开始，并在每个递归步骤中最多调用该函数 4 次，则最多会有 4^18 次递归调用。 4^18 不依赖于 n，因此该函数的复杂度为 O(1)。

Answer 2

我不知道你的意思是“函数的复杂性”，但我在键盘上运行你的函数（ http://codepad.org /jFUW1ATj ）并得到这个结果

br_nacina_zaba(1, 0, 0) was called 5 times.
br_nacina_zaba(2, 0, 0) was called 5 times.
br_nacina_zaba(3, 0, 0) was called 9 times.
br_nacina_zaba(4, 0, 0) was called 77 times.
br_nacina_zaba(5, 0, 0) was called 33445 times.
br_nacina_zaba(6, 0, 0) was called 1048573 times.
br_nacina_zaba(7, 0, 0) was called 15530681 times.