Анализ сложности времени рекурсии - PullRequest
Новая
       10

Анализ сложности времени рекурсии

0 голосов
/ 21 мая 2018

Следующий код вычисляет детерминант с использованием рекурсии.

Для цикла "for", у которого есть O (n), мы снова вызываем функцию с n-1 элементами, поэтому мы должны умножать каждый раз, когда мывызвать функцию?что-то вроде O (n) O (n-1) ... * O (1)?

    function y = detm(A)
    n = length(A);
    y = 0;
    if n == 1
        y = A(1,1);
    elseif n == 2
        y = A(1,1).*A(2,2)-A(1,2).*A(2,1);
    elseif n > 2
        for i = 1:n
           temp = A(2:end,:);
           temp(:,i) = [];
           if mod(i,2) == 0
               y = y - A(1,i)*detm(temp);
           else
               y = y + A(1,i)*detm(temp);
           end
        end
    end
end
...