2013-07-16 3 views
0

Я прочитал много нового о алгоритме Чернослив и поиска, и я даже попросил его подтвердить.Временная сложность чернослива и поиска

This - отличный источник. Однако некоторые вещи мне трудно понять. Как временной сложности Прюн и Поиск:

Image

Может кто-то дать краткое объяснение этому?

+0

Это временная сложность конкретного алгоритма поиска и черновика. Вы должны описать алгоритм и то, что вы не понимаете в этом вычислении. – hivert

+0

@hivert Это, вероятно, алгоритм медианы медианов. –

+0

@DavidEisenstat Да, тот, который находит медиану. Это смущает. –

ответ

0

Они решают повторяемость 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. 

 Смежные вопросы

  • Нет связанных вопросов^_^