Найти i-й величайший элемент

Question

Я хочу использовать процедуру Divide-and-Conquer для вычисления i-го величайшего элемента в строке целых чисел и анализировать асимптотическую сложность времени алгоритма.

Algorithm ith(A,low,high){ 
    q=partition(A,low,high); 
    if (high-i+1==q) return A[q]; 
    else if (high-i+1<q) ith(A,low,q-1); 
    else ith(A,q+1,high); 
} 

Правильно ли это? Если да, то как мы можем найти его временную сложность?

Сложность времени описывается следующим рекуррентным соотношением:

Т (п) = Т (NQ) + T (Q-1) + Θ (п)

Но как мы можем решить эту проблему рекуррентное отношение, не зная значения q?

Или существует алгоритм с меньшей временной сложностью, который вычисляет i-й наибольший элемент в строке целых чисел?

Answer 1

Это вариант алгоритма quick select (который находит наименьший элемент i-th, а не i-th наибольший элемент). Он имеет время работы O(n^2) в худшем случае и O(n) в среднем случае.

Чтобы увидеть наихудший случай, предположим, что вы ищете самый большой элемент nth, и бывает так, что алгоритм всегда выбирает q как самый большой элемент в остальном диапазоне. поэтому вы будете называть функцию ithn раз. Кроме того, подпрограмма раздела занимает O(n), поэтому общее время работы O(n^2).

Чтобы понять анализ среднего случая, проверьте объяснение, данное профессором Тимом Roughgarden here.