Задать вопрос

Алгоритм выборки топ 10 фотографий?

Есть n фотографий, из них нужно найти топ k самых "красивых" и составить рейтинг-список (список в котором фото расположены в порядке убывания по красоте) для этих k фотографий.
Топ k красивых определяет один пользователей, делая выборки между двумя фотографиями.
Пример: есть 200 фотографий котов, из них нужно определить 10 самых милых и из этих 10 составить рейтинг-список по убыванию милости.
Надеюсь доступно что объяснил доступно.
  • Вопрос задан
  • 545 просмотров
Подписаться 4 Средний 7 комментариев
Ответ пользователя Сергей Соколов К ответам на вопрос (3)
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Посмотрите алгоритмы сортировки. Например, методом пузырька придётся до 10 раз пройти по всему массиву, итого 199+198+197+...+189 = 2123 сравнений.

Но т.к. интересует только верхушка, можно оптимизировать. Разбить фотогрфии на пары, сравнить попарно, отбросить проигравших. Так уменьшается вдвое число кандидатов. 200 -> 100 -> 50 -> 25 -> 13 за 100+50+12=162 сравнения. Оставшиеся 13 надо уже пузырьковым методом отсортировать до отбора топ-10: 12+11+10+...+3 = 75
Итого всего 237 сравнений, если не ошибаюсь.

В фильме «Социальная сеть» (2010) есть эпизод, где молодой Цукерберг якобы использовал алгоритм начисления шахматного рейтинга ELO в своём первом приложении FaseMash для сравнения, какая из девушек привлекательнее. Там тоже посетители выбирают одну из двух фотографий. Может ли это сократить число необходимых сравнений, вопрос открытый.
Ответ написан