BigO сложность алгоритма Select i, почему это неправильно? ⇐ C++

[Anonymous]

Я пытаюсь реализовать алгоритм выбора с помощью метода medianOfMedians. Вот мой код:

Код: Выделить всё

int select(int i, vector& n) {
int pivot = medianOfMedians(n);

vector k = partition(n, pivot); // k[0] is the left part of the partitioned vector, k[1] is the right

if (i == k[0].size() + 1) {
return pivot;
} else {
if (i < k[0].size() + 1) {
return select(i, k[0]);

} else {
return select(i - k[0].size() - 1, k[1]);
}
}
}

Я использовал библиотеку тестов Google, чтобы оценить сложность BigO, в результате чего получилось O(55NlgN): должно быть O(kN). Я попробовал отдельно протестировать функции mediansOfMedians (O(300N)) и part (O(3N)). Я не могу понять, какая часть алгоритма неправильная.


Подробнее здесь: https://stackoverflow.com/questions/791 ... y-is-wrong