Я прочитал много нового о алгоритме Чернослив и поиска, и я даже попросил его подтвердить.Временная сложность чернослива и поиска
This - отличный источник. Однако некоторые вещи мне трудно понять. Как временной сложности Прюн и Поиск:
Может кто-то дать краткое объяснение этому?
Они решают повторяемость T (n) < = T (n/5) + T (3n/4) + Cn (C - постоянная большого О) через какой-то странный метод, который я не распознаю , В модуле отсутствующего базового футляра и операторов пола и потолка мы можем решить его через Akra–Bazzi или метод подстановки (этот ответ).
Индуктивное предположение состоит в том, что T (n ') < = 20Cn' для всех n '< n. Тогда
T(n) <= T(n/5) + T(3n/4) + Cn
<= 20C(n/5) + 20C(3n/4) + Cn
= 20C(4n/20) + 20C(15n/20) + Cn
= 4Cn + 15Cn + Cn
= 20Cn.
Это временная сложность конкретного алгоритма поиска и черновика. Вы должны описать алгоритм и то, что вы не понимаете в этом вычислении. – hivert
@hivert Это, вероятно, алгоритм медианы медианов. –
@DavidEisenstat Да, тот, который находит медиану. Это смущает. –