Какова временная сложность этого алгоритма DFS

Question

Постановка задачи : Учитывая массив неотрицательных целых чисел, вы изначально позиционируетесь в первом индексе массива. // Проблема с кодом leetcode

Я просто запутался в подсчете ее сложности. Какова сложность тике, и не могли бы вы порекомендовать какие-либо книги или учебное пособие, в которых учитывается расчет t ie сложность

   class Solution {
    public boolean canJump(int[] nums,int sum,boolean isreach[]) {
        if(sum == nums.length-1){
            return true;
        }
        if(sum >= nums.length){
            return false;
        }
        if(isreach[sum]) return true;
        int j = nums[sum];
        int k = 1;
        boolean check = false;
        while( k <= j && sum + k < nums.length ){       
           check = check || canJump(nums, sum+k,isreach);
           if(check) {isreach[sum] = check; return true;}
           k++;
        }
        return false;
    }
    public boolean canJump(int[] nums) {
        boolean isreach[] = new boolean[nums.length];
        return canJump(nums,0,isreach);
    }
 }

На мой взгляд, это n ^ 2

Answer 1

Прежде всего, это не алгоритм поиска в ширину. Я уверен, что вопрос, на который вы ссылаетесь, - это проблема Jump Game от LeetCode , оптимальным решением которой является использование Dynami c Programming, а не поиск в ширину.

Алгоритм, который вы представили выше, это просто нисходящий алгоритм динамического программирования c, который запоминает найденные решения для небольших подзадач. Время выполнения этого алгоритма равно O(N) (где N - это значение sum, которого вы хотите достичь), поскольку существует не более N различных состояний, которые вы посетите.