Определение временной сложности рекурсивного вызова функции из цикла

Question

Я не уверен, что этот вопрос ранее задавался в ТАК или нет.Ну, я проверял частоту символа в массиве.Я довольно слаб в определении сложности, поэтому я подумал, что это сообщество может помочь мне понять смысл!Мне очень жаль, если я выложу это с какой-то абстракцией!Если кто-нибудь может мне помочь, это будет здорово!

Вот мой код:

class SearchAChar{
private static int getOccurance(char [] a, char k, int l, int r, int count){
    if(l == r) return count;

    if(a[l] == k){a[l]='0';count++;}

    return getOccurance(a, k, l+1, r, count);   
}
public static void main(String [] args){
    char [] arr = {'a', 'e', 'b', 'c', 'b', 'c', 'd','a'};

    for(int i=0; i<arr.length; i++){
        if(arr[i] == '0') continue;
        System.out.println("Occurance of : " +arr[i] + " is "+ getOccurance(arr, arr[i], i, arr.length, 0) +" times!");
    }
}
}

Какой должна быть сложность во время выполнения этих проблем ??

Answer 1

Давайте попробуем разложить;Я говорю о худшем сценарии сложности.

n = length of the array

1. for(int i=0; i<arr.length; i++){} - это не зацикливается n раз, потому что вы обновляете массив, устанавливая видимый символ в 0 в рекурсивномфункция.И если символ 0, вы продолжаете.Так что O(n/2).

2. getOccurance(a, k, l+1, r, count) - повторяется по каждому символу до тех пор, пока длина не будет равна == инкремент.Лучший способ представить стек рекурсивных вызовов функций - это дерево.Например, это изображение показывает, как строится стек вызовов, вычисляя Фибоначчи.

Но ваша функция getOccurance не вызывает себя дважды, как на картинке функции Фибоначчи.Таким образом, мы могли бы сказать, что он вызывает как в одной ветви дерева.Другими словами, здесь мы видим последовательность вызовов стека, как 0,1,2... n-1, поэтому мы могли бы вычислить сложность O(n).

Если мы соединим эти два шага, мы получим.O(n/2 * n)

Но также, как упомянул @Coderino - Недоминантные термины не учитываются в худшем случае.

В заключение, сложность приведенного выше кода составляет O(n^2).

Некоторые полезные ресурсы - https://users.cs.duke.edu/~ola/ap/recurrence.html

Сложность рекурсивной факториальной программы

Answer 2

Поскольку существует цикл for, а внутри цикла for есть рекурсивная функция, которая имеет сложность времени выполнения O (n), что делает сложность наихудшего времени O (n ^ 2), где n - длинамассив символов.