Я знаю, что это можно сделать, отсортировав массив и взяв большие числа, пока не будет выполнено требуемое условие. Это займет как минимум nlog(n) времени сортировки.
Есть ли улучшения по сравнению с nlog(n).
Можно считать, что все числа положительные.
Вот алгоритм, который O(n + size(smallest subset) * log(n)). Если наименьшее подмножество намного меньше массива, это будет O(n).
Прочтите http://en.wikipedia.org/wiki/Heap_%28data_structure%29 если мое описание алгоритма неясно (в нем мало деталей, но все детали есть).
O(n).O(size(smallest subset) * log(n)).Это почти наверняка тот ответ, на который они надеялись, хотя его отсутствие не должно нарушать условия сделки.
Изменить. Вот еще один вариант, который часто работает быстрее, но может быть и медленнее.
Walk through elements, until the sum of the first few exceeds S. Store current_sum.
Copy those elements into an array.
Heapify that array such that the minimum is easy to find, remember the minimum.
For each remaining element in the main array:
if min(in our heap) < element:
insert element into heap
increase current_sum by element
while S + min(in our heap) < current_sum:
current_sum -= min(in our heap)
remove min from heap
Если мы сможем отклонить большую часть массива, не манипулируя нашей кучей, это может быть в два раза быстрее, чем предыдущее решение. Но также можно работать медленнее, например, когда последний элемент в массиве больше, чем S.
Предполагая, что числа являются целыми числами, вы можете улучшить обычную n lg(n) сложность сортировки, потому что в этом случае у нас есть дополнительная информация о том, что значения находятся в диапазоне от 0 до S (для наших целей целые числа, превышающие S, совпадают с S).
Поскольку диапазон значений ограничен, вы можете использовать несравнительный алгоритм сортировки, такой как сортировка Pigeonhole. или Сортировка по основанию, чтобы перейти ниже n lg(n).
Обратите внимание, что эти методы зависят от некоторой функции S, поэтому, если S становится достаточно большим (а n остается достаточно маленьким), возможно, вам лучше вернуться к сравнительной сортировке.
n log n.
- person hammar; 11.05.2011
Одно улучшение (асимптотически) по сравнению с Theta(nlogn), которое вы можете сделать, состоит в том, чтобы получить алгоритм времени O(n log K), где K — требуемое минимальное количество элементов.
Таким образом, если K постоянно или, скажем, log n, это лучше (асимптотически), чем сортировка. Конечно, если K равно n^epsilon, то это не лучше, чем Theta(n logn).
Это можно сделать с помощью алгоритмов выбора, которые могут определить ith наибольший элемент за время O(n).
Теперь выполните бинарный поиск K, начиная с i=1 (наибольшего) и удваивая i и т. д. на каждом ходу.
Вы находите ith по величине, находите сумму i по величине элементов и проверяете, больше ли она S или нет.
Таким образом, вы запустите O (log K) запусков алгоритма выбора (то есть O (n)) для общего времени работы O (n log K).
Вот решение задачи с ожидаемым временем O(n). Это чем-то похоже на идею Морона, но мы не выбрасываем работу, которую проделывал наш алгоритм выбора на каждом шаге, и начинаем пробовать с элемента, потенциально находящегося посередине, вместо того, чтобы использовать метод повторного удвоения.
В качестве альтернативы, это просто быстрый выбор с небольшим дополнительный учет на оставшуюся сумму.
Во-первых, ясно, что если бы у вас были элементы в отсортированном порядке, вы могли бы просто выбирать сначала самые большие элементы, пока не превысите желаемую сумму. Наше решение будет таким, за исключением того, что мы будем изо всех сил стараться не обнаруживать информацию о заказе, потому что сортировка медленная.
Вы хотите иметь возможность определить, является ли данное значение отсечением. Если мы включим это значение и все, что больше его, мы достигнем или превысим S, но когда мы удалим его, мы окажемся ниже S, тогда мы будем золотыми.
Вот псевдокод, я не проверял его на пограничные случаи, но идея понятна.
def Solve(arr, s):
# We could get rid of worse case O(n^2) behavior that basically never happens
# by selecting the median here deterministically, but in practice, the constant
# factor on the algorithm will be much worse.
p = random_element(arr)
left_arr, right_arr = partition(arr, p)
# assume p is in neither left_arr nor right_arr
right_sum = sum(right_arr)
if right_sum + p >= s:
if right_sum < s:
# solved it, p forms the cut off
return len(right_arr) + 1
# took too much, at least we eliminated left_arr and p
return Solve(right_arr, s)
else:
# didn't take enough yet, include all elements from and eliminate right_arr and p
return len(right_arr) + 1 + Solve(left_arr, s - right_sum - p)
log(S)) в худшем случае, не нанося ущерба среднему случаю. У нас есть массив целых чисел в ограниченном диапазоне. Сделайте так, чтобы каждый второй поворот находился в середине целых чисел в этом диапазоне, а не в значениях в массиве. Это гарантированно сойдется за O(log(S)) шагов. (В качестве альтернативы вы можете выполнить детерминированный медианный поиск в любое время, когда последние 3 выбора не уменьшили пространство поиска достаточно. Это делает его O(n) и в среднем случае не повредит производительности.)
- person btilly; 20.05.2011
Суммируйте элементы от большего к меньшему в отсортированном порядке, пока не превысите S.
n lg(n)на сортировку сравнением, заключается в том, что вы не знаете заранее, в каком диапазоне находятся значения, сколько их и т. д. Зная часть этой информации заранее, вы сможете выполнять несравнительную сортировку. работать лучше в некоторых случаях. - person verdesmarald schedule 11.05.2011