Big-O примера функции

Question

У меня есть эта функция:

function void myFoo(int num, int count) { 
    if (num == 0) return;

    for (int x = 0; x < count; x++) {
        for (int y = x; y < count; y++) {
            for (int z = y; z < count; z++) {
                //O(1) computation
            }
        }
        num--;
        myFoo(num, count);
    }
}

и мне просто интересно, насколько сложна эта функция, Биг-о (n!)?

Answer 1

Я предполагаю, что num и count оба неотрицательны.Время выполнения T (m, n), где m, n это размеры num и count (то есть log (num), log (count)), задается как

T(m, n)=sum(T(log(2^m-1), n)+sum(sum(O(1), z=y..2^n-1), y=x..2^n-1), x=0..2^n-1)

, что упрощается до

T(m, n)=2^n*T(log(2^m-1), n)+2^n/3+2^(2n-1)+2^(3n-1)/3

, давая

T(m, n)=2^n*T(log(2^m-1), n)+O(2^(3n))

Наблюдая, что это не зависит от m, за исключением того, что оно рекурсивно применяется 2 ^ m раз, мы получаем

T(m, n)=sum(2^(k*n)*O(2^(3n)), k=0..2^m-1)

, что совпадает с

T(m, n)=O((8^n*(-1 + 2^(2^m*n)))/(-1 + 2^n))=O(2^((2^m+2)n))=O(2^(2n)*2^(2^m*n))

Итак, измеряя входные данные как размеры каждого числа (и обобщая, чтобы учесть произвольно заданные целые числа), сложность хуже, чем двойная экспонентав м.