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

«Университет XXI века: научное измерение» – 2021 254 количества совпадений. Описанный алгоритм приводит к верному результату, а трудоемкость алгоритма O(N 2 ) для N=2*10 5 составит число порядка 4*10 10 . Попробуем изменить математическую модель задачи с целью уменьшения трудоемкости алгоритма. Обратим внимание на тот факт, что по первому алго- ритму возникала необходимость проверки на равенство целых и вещественных чисел. Для решения данной проблемы будем сравнивать не сами расстояния, а их квадраты, т.к. с точки зрения научной составляющей здесь нет никаких нару- шений. Для метода Знайки квадрат расстояния будет равен � − � 2 + � − � 2 , а для метода Незнайки: � − � 2 + 2 ∙ � − � ∙ � − � + � − � 2 . Анализ полученных выражений показывает, что их значения совпадут только в случае, если 2 ∙ � − � ∙ � − � = 0 , то есть в случае, если для пары точек совпадают или координаты x или координаты y. Таким образом, сформулированная задача по сути своей приведена к следу- ющей: «Для N точек с целочисленными координатами (x i , y i ) посчитать количе- ство пар точек, у которых совпадают координаты x или y ». Данная задача не яв- ляется оригинальной, и решается известными методами. Однако, трудоемкость данного решения составляет O(N 2 ) операций, что не отличается от первого вари- анта решения. Обратим внимание на возможность иного подхода к решению: следует отсортировать массив данных с координатами точек по неубыванию ко- ординаты x, что в хорошем случае требует O(Nlog 2 N) операций, и за один проход по массиву посчитать количество пар с совпадением координаты x за O(N) опе- раций. Из результатов анализа математической модели видно, что похожие дей- ствия следует осуществить и по отношению к координате y . Таким образом, мы видим, что для успешного решения может хватить порядка O(Nlog 2 N) операций, что для N=2*10 5 составит число порядка 3,5*10 6 , что существенно уменьшает время вычислений без увеличения объема занимаемой памяти. Частным случаем входных данных в этой задаче является совпадение значений обеих координат то- чек с разными порядковыми номерами. Понять, как считать в таком случае, можно из контрольных примеров, которые всегда сопровождают олимпиадные задачи. Рассмотренные нами две задачи (при желании таких примеров можно при- вести достаточно много) являются убедительным доказательством необходимо- сти подготовки будущих учителей информатики к решению олимпиадных задач. Такая работа существенно повышает уровень сформированности профессио- нальных компетенций будущих специалистов и, как следствие, уровень качества знаний их учеников.