Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм быстрой оболочки - Сложность алгоритма

Сложность алгоритма состоит из сложности построения двух подмножеств рассматриваемого множества O и сложностей решения подзадач для каждого из подмножеств: T = T + T + O.

В лучшем случае, когда задача разбивается на две равномощные подзадачи, сложность алгоритма является решением рекурсивного уравнения:

T = 2 T + O =>

T = O.

В худшем случае:

T = T + T + O =>

T = O.

Лемма Решением уравнения является функция Пусть N = 2k. Тогда T = 2 T + C 2k ; T = 2 T + C 2k 1 => T = 4 T + 2 °C 2k 1 + С 2k = 4 T + 2 °C 2k => T = 2m T + m С 2k При m = k алгоритм заканчивает работу: T = N T + C logN N = O