Шура Люберецкий

Люблю я истории про O(N²), ничего не могу с собой поделать. Так как в этот раз все пока что держится на слухах — пусть это будет сказочка про республику Анчурия, где-то в Латинской Америке.

Анчурия — республика демократическая, в ней есть аж четыре партии — Пиратов, Жуликов, Воров и Коммунистов, и даже иногда проводятся выборы в парламент. Более того, Анчурия не чужда высоким технологиям и решила применить на очередных выборах модную новинку — электронную голосовалку на блокчейне, скачав ее прямо с гитхаба.

Одного не знали бедные любители высоких технологий из Анчурии — писал ту голосовалку не очень образованный программист Вася, и время подсчета результатов в той голосовалке зависело от количества избирателей квадаратично. Но Министерство Информационных Технологий Анчурии — люди прошаренные, и даже провели тестовое голосование — выбирали, что лучше, леденцы с ментолом или менты с леденцами. В голосовании приняли участие самые прошаренные граждане Анчурии, коих набралось аж 10 000, результаты подсчитались достаточно быстро — и систему решили внедрить на будущих парламентских выборах с десятью миллионами избирателей.

И вот поздно вечером в воскресенье закрылись электронные избирательные участки, и сам Министр Информационных Технологий нажал на самом мощном компьютере Анчурии кнопочку Enter, запустив процедуру подсчета. Долго ли ждать результатов? Ну полчаса-час, ответил министр — и все решили подождать. Сначала два часа ждали, потом четыре, восемь… — в общем, и к утру не дождались. Зато проснулись коммунисты и с криком «Дурят капиталисты нашего брата!» собрали митинг на Главной площади. К вечеру собрался уже не митинг, а целый майдан, кто-то обозвал цифрового министра пiдрахуем (не обошлось без украинского следа), пираты подрались с коммунистами, жулики с ворами — но все вместе пошли от Главной площади по Главной улице к Президентскому дворцу (география столицы Анчурии проста и понятна).

Ну дальше как всегда — Эль Президенте почуял, что пахнет жареным, и сбежал, в Анчурии случилась маленькая гражданская война, к власти пришла военная хунта и от греха подальше запретила все выборы, компьютеры и на всякий случай — украинский язык. Жуликов посадили, воров постреляли, пиратов развесили на реях, коммунистов отправили в тайные тюрьмы ЦРУ. Говорят, что где-то в начале гражданской войны бывший министр даже вылез из своего дата-центра в подземном бункере со словами «Мы все посчитали!» — но всем это было настолько безразлично, что никто про него и не вспомнил.

Так вот, господа программисты, вся беда случилась из-за того, что случайно найденная на гитхабе голосовалка имела сложность подсчета голосов O(N²) — то есть если для подсчета 10 000 бюллетеней требовалась всего 1 секунда — то подсчет 10 000 000 бюллетеней занял не 1 000 секунд, как надеялся цифровой министр, а гораздо больше — 1 000 000 секунд, или целых 11 дней — как раз хватит на то, чтобы не дождавшиеся итогов выборов анчурийцы начали гражданскую войну. O(N²) — очень «хорошая» оценка сложности, она, с одной стороны, достаточно мала, чтобы успешно проходить тесты на небольших наборах данных (это вам не перебор всех подмножеств, и даже не какие-нибудь числа Белла) — а с другой стороны, очень плохо ведет себя, когда данных становится много.

А чтобы не спровоцировать гражданскую войну в латиноамериканской стране — не делайте алгоритмы со сложностью O(N²), а читайте книжки Скиены, Седжвика, Дасгупты и Кормена, можно еще поставить на полочку многотомник Кнута.