Априорный и асимптотический уровень сложности

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). Максимальная глубина (четвертичного) дерева вызовов ограничена 19 в первом LOC функции:

korak увеличивается в каждом рекурсивном вызове. Если вы начнете с korak=0 и вызывать функцию не более 4 раз за каждый рекурсивный шаг, вы получите не более 4^18 рекурсивных вызовов. 4^18 не зависит от n, следовательно, функция находится в O(1).

Answer 2

Я не знаю, что вы подразумеваете под "сложностью функции", но я запустил вашу функцию на codepad ( http://codepad.org/jFUW1ATj) и получил такой результат

br_nacina_zaba (1, 0, 0) вызывали 5 раз.
br_nacina_zaba(2, 0, 0) вызывали 5 раз.
br_nacina_zaba (3, 0, 0) вызывали 9 раз.
br_nacina_zaba(4, 0, 0) вызывали 77 раз.
br_nacina_zaba (5, 0, 0) вызывали 33445 раз.
br_nacina_zaba(6, 0, 0) вызывали 1048573 раза.
br_nacina_zaba(7, 0, 0) вызывали 15530681 раз.