[ivank]

Vlad Drakula

но веть и быстрая сортировка имеет шанс работать по n*n, и ничего пользуются...

Я не спорю. Есть сортировка с помощью кучи, которая гарантированно работает за n*logn, но ею не пользуются, т.к. в среднем случае она в несколько раз медленнее быстрой сортировки (которая, кстати называется сортировкой Хоара, на самом деле). Средние случаи встречаются значительно чаще, чтобы перевешивать превосходство хип-сорта над кусортом в худшем случае.

Аналогично в среднем случае твой алгоритм значительно лучше. Вот только на предполагаемых наборах чисел (25-50) вероятность влететь в худший случай максимальна (т.к. чем больше чисел (n>50), тем больше вероятность получить требуемую сумму с помощью твоей эвристики. А при малом n (<25), даже если требуеммую сумму получить нельзя, стоимость полного перебора невелика).

а как на счет реализации? если по оптимизировать то можно сократить время работы в 3-7 раз...

Да это вроде не требуется по условию. Человек готов был ждать по пол-часа и более. И вообще, не умею я оптимизировать на "не-алгоритмеческом" уровне, доверяю компилятору.