Эффективный способ вычисления суммы k наибольших чисел в списке?

Question

Я читал некоторые вопросы интервью с практикой, и у меня есть вопрос об этом. Предположим, что список случайных чисел каждый между 1 & 100, вычислить сумму k наибольших целых чисел? Обсудите пространственную и временную сложность и изменится ли подход, если каждое целое число находится между 1 & m, где m изменяется?

Моя первая мысль - отсортировать массив и вычислить сумму самых больших k чисел. Затем я подумал, что если я использую двоичную древовидную структуру, где я могу смотреть, начиная с нижнего правого дерева. Я не уверен, изменится ли мой подход, будут ли цифры от 1 до 100 или от 1 до m? Любые мысли о наиболее эффективном подходе?

Answer 1

Наиболее эффективным способом может быть использование чего-то типа randomized quickselect. Он не выполняет этап сортировки до завершения и вместо этого выполняет только шаг раздела с быстрой сортировкой. Если вы не хотите, чтобы k наибольших целых чисел в каком-то определенном порядке, это было бы так, как я бы пошел. Это требует линейного времени, но анализ не очень прост. м не повлияет на это. Кроме того, вы можете написать код таким образом, чтобы сумма вычислялась при разбиении массива.

Time: O(n) 
Space: O(1) 

---

Альтернативного сортирует используя что-то вроде counting sort который имеет линейную гарантию времени. Как вы говорите, значения являются целыми числами в фиксированном диапазоне, это будет работать очень хорошо. С ростом m увеличивается потребность в пространстве, но вычисление суммы довольно эффективно в пределах ковшей.

Time: O(m) in the worst case (see comments for the argument) 
Space: O(m) 

Answer 2

Я бы сказал, что сортировка, вероятно, не нужна. Если k невелик, тогда вам нужно только сохранить отсортированный список, который обрезает элементы за пределами элемента k.

Каждый шаг в этом должен быть O(k) в худшем возможном случае, когда элемент добавлен максимально. Тем не менее, средний сценарий случая намного лучше, после определенного количества элементов большинство должно быть просто меньше последнего элемента в списке, а операция будет O(log(k)).

Answer 3

Один из способов - использовать min-heap (implemented as a binary tree) максимального размера k. Чтобы увидеть, принадлежит ли новый элемент в куче или нет, это только O (1), так как это мини-куча, а поиск минимального элемента - это операция с постоянным временем. Каждый шаг вставки (или не вставка ... в случае элемента, который слишком мал для вставки) по списку O (n), равен O (log k). Окончательный шаг обхода дерева и суммирования равен O (k).

Общая сложность:

O (n log k + k) = O(n log k))

Если у вас есть несколько ядер, работающих на вашем компьютере, в этом случае, параллельные вычисления является вариант, суммирование должно быть сделано только в конце. «На лету» вычисляет дополнительные этапы расчета, не уменьшая при этом сложную временную сложность (на самом деле у вас будет больше вычислений). Вы всегда должны будете суммировать k элементов, так почему бы не избежать дополнительных шагов сложения и вычитания?