Определить правильные рекуррентные функции для алгоритмов «разделяй и властвуй» - PullRequest
Новая
       83

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

0 голосов
/ 25 марта 2019

Я давно пытаюсь понять природу повторений. Мне особенно любопытно, как создаются функции (T (n)) для повторений. Например, в сортировке слиянием утверждается, что временная сложность может быть названа T (n) = 2T (n / 2) + cn. Я не вижу связи между этим и рекурсивными вызовами в сортировке слиянием.

Я понимаю концепцию теории мастера. a должно быть числом рекурсивных вызовов, b должно быть фактором, с помощью которого ввод сокращается при каждом вызове, а d является работой, выполняемой вне рекурсивного алгоритма. Я просто не понимаю, как любая работа в сортировке слиянием выполняется вне рекурсивного алгоритма, учитывая, что вся работа, выполняемая алгоритмом, так или иначе порождается одним из рекурсивных вызовов. 

slice1 = Arrays.copyOfRange(u_arr, 0, half); // this takes O(n) time, better method?
slice2 = Arrays.copyOfRange(u_arr, half, u_arr.length);
        arr1 = this.mergesort(slice1);
        arr2 = this.mergesort(slice2);
        return this.merge(arr1, arr2);
    }

За исключением базового случая, некоторой инициализации и функции слияния, как любая работа, выполняемая этим алгоритмом, может быть выполнена вне рекурсивного вызова? И учитывая, что время выполнения за пределами рекурсивных вызовов может быть определено, является ли рекурсия по существу просто функцией шаблона для включения характеристик алгоритмов «разделяй и властвуй» так, что T (n / b) + O (n ^ d)? Учитывая соответствующие a, b и d.

...