Нотация О-большое и сложность социальных взаимодействий

Если вам приходилось сидеть на невыносимо скучном совещании, где два человека обсуждают проблему, а все остальные являются зрителями, вы готовы принять идею о том, что такой способ взаимодействия не эффективен. Возможно, вы также задумывались об альтернативах. Ошибка организаторов встречи была в том, что они выбрали форму взаимодействия не соответствующую задаче, и, тем самым, обрекли большое количество людей на потерю времени.

Некоторое время назад, я понял, что к оценке сложности социальных взаимодействий, можно применять те же подходы, что и к оценке сложности алгоритмов – а значит можно увидеть их плюсы, минусы и области применения. Ниже краткий список наиболее частых вариантов, с которыми я имел дело.

О(n2): Совещание равноправных участников. n человек обсуждают вопрос, причем для достижения взаимопонимания, каждому участнику нужно пообщаться с каждым. Всего будет осуществлено n*(n-1)/2 социальных взаимодействий (эквивалентно задаче подсчета числа рукопожатий в группе из n человек), т.е сложность алгоритма О(n2). Казалось бы, за счет того, что общение одновременно могут осуществлять n/2 пар людей, оценка по времени – О(n), однако на реальных совещаниях в один момент времени говорит только один человек, поэтому оценка для худшего случая — О(n2). Если время взаимодействия – 5 минут и для достижения полного взаимопонимания в группе требуется две итерации, то совещание трех человек продлиться 30 минут, четырех – час, пятерым потребуется 1 час 40 минут для нахождения общего решения (что подозрительно похоже на правду). Если же число итераций зависит от числа участников, мы получаем еще более печальные оценки.

Но не все так плохо! Читать дальше →

В Google научили ИИ убирать водяные знаки с изображений

Водяные знаки считаются довольно надежным способом защиты изображений от копирования или от использования без разрешения. Чтобы вручную удалить такую метку, необходимо владеть «фотошопом» на достаточном уровне и потратить немало времени. Кроме этого, при ручном удалении на фотографии, как правило, остаются многочисленные следы, так или иначе портящие ее вид. Именно поэтому специалисты компании Google решили создать […]

[Из песочницы] Описание алгоритмов сортировки и сравнение их производительности

Вступление

На эту тему написано уже немало статей. Однако я еще не видел статьи, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера. Кроме того, далеко не везде выложены реализации и описание набора тестов. Это приводит к тому, что могут возникнуть сомнения в правильности исследования. Однако цель моей работы состоит не только в том, чтобы определить, какие сортировки работают быстрее всего (в целом это и так известно). В первую очередь мне было интересно исследовать алгоритмы, оптимизировать их, чтобы они работали как можно быстрее. Работая над этим, мне удалось придумать эффективную формулу для сортировки Шелла.

Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.
Читать дальше →