Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 12

Что из следующего является рекуррентным уравнением для наихудшей временной сложности алгоритма быстрой сортировки для сортировки n (≥ 2) чисел? В рекуррентных уравнениях, приведенных в вариантах ниже, с является константой.

(A) T (n) = 2T (n / 2) + cn
(B) T (n) = T (n — 1) + T (0) + cn
(C) T (n) = 2T (n — 2) + cn
(D) T (n) = T (n / 2) + cn

Ответ: (Б)
Объяснение: В худшем случае выбранный опорный пункт всегда размещается в угловой позиции, и выполняется рекурсивный вызов.

а) для подрешетки слева от оси, которая в худшем случае имеет размер n-1.
б) для подмассива справа от оси, который в худшем случае имеет размер 0.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 12

0.00 (0%) 0 votes