Университет XXI века: научное измерение

Математика, физика и информатика 253 обратим внимание на степень влияния выбора удачной модели данных на суще- ственное усиление эффективности алгоритма, а также на приложение алгорит- мов сортировки к поиску оптимальных решений. Рассмотрим задачу «Наибольшее произведение». Дано N целых чисел. Тре- буется выбрать из них три таких числа, произведение которых максимально. Ис- точником данных вступает файл с целыми числами. Условие задачи достаточно просто. С первого взгляда модель данных может быть представлена одномерным целочисленным массивом, а в качестве матема- тической модели для разработки алгоритма можно организовать полный перебор троек попарно различных элементов массива, с целью поиска максимального про- изведения. Трудоемкость данного алгоритма составляет O(N 3 ) операций. Если раз- работчик алгоритма обладает знаниями в области алгоритмов сортировки мас- сива, то трудоемкость сокращается до O(N 2 ) , а при знакомстве с алгоритмом би- нарной пирамидальной сортировки – до O(Nlog 2 N) . При этом малые значения N не дают убедительных данных о сокращении трудоемкости. Но если N достигнет значений 10000, 50000, 100000, то разница во времени работы будет уже суще- ственной, кроме того, может наступить дефицит памяти для хранения массива. В то же время вдумчивое изучение постановки задачи и ее предметной об- ласти позволяет уйти от необходимости хранения данных в массиве. По условию надо контролировать всего пять значений из всех данных в файле: три макси- мальных (max1, max2, max3) и два минимальных числа (min1, min2) . Достичь этого можно при поочередном считывании элементов файла и учета их влияния на текущие значения указанных характеристик. Для этого используется извест- ный алгоритм «проталкивания». После окончания считывания данных из файла останется сравнить только два произведения: max1*max2*max3 и max1*min1*min2 и выдать ответ. Таким образом, трудоемкость алгоритма со- ставляет O(N) операций, а в области памяти контролируется поток связи с фай- лом и шесть переменных. Продвижение в оценке эффективности представлен- ных алгоритмов более чем убедительно. Такая реализация алгоритма позволит пройти тест на файлах произвольного количества данных. Рассмотрим еще одну задачу: «В команде N человек, i -й из которых нахо- дится в точке плоскости с целыми координатами (x i , y i ) . Незнайка вычисляет рас- стояние между двумя людьми i и j по формуле � − � + � − �. А Знайка, как обычный человек, считает, что расстояние равно �� − � 2 + � − � 2 . Успех операции, задуманной мальчиками, зависит от того, сколько существует пар (i, j) (1 ⩽ i < j ⩽ N) , таких что расстояния между i и j людьми, вычисленные Знайкой и Незнайкой, равны между собой. В задаче требуется вычислить именно эту ве- личину». Обратим внимание на ограничения, которые накладываются на данные задачи: N≤200000, | |, | | ≤ 10 9 . Для решения используем одномерный массив. Для построения алгоритма было бы вполне логично организовать перебор пар несовпадающих по индексу точек, и для каждой пары вычислить расстояния по методам Знайки и Незнайки. В случае равенства вычисленных значений следует увеличить счетчик