Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Суще-ие 2 чисел в массиве в сумме дающих введённое

Автор: temak 9.2.2012, 00:33

Помогите с  упражнением из книги Кормена. Упражнение со свёздочкой. Цитата Пусть имеется множество S, состоящее из n целых чисел, и отдельное  целое число х.  Необходимо определить, существуют ли во множестве S  два элемента, сумма которых равна х. Разработайте алгоритм решения  этой задачи, время работы которого возрастало бы с увеличением n как O(n lg n).  За n^2 с лёгкостью получается а вот nlgn в худшем случае не выходит.

Автор: temak 9.2.2012, 01:33

Всё, решил)  Сразу сортируем слиянием, затнм линейно проходим по массиву и бинарным поиском ищем разницу.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)