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

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

Я не знаю, что вы подразумеваете под "сложностью функции", но я запустил вашу функцию на кодовой панели (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.