Можем ли мы уменьшить сложность сравнения каждого пользователя в массиве с каждым другим?

Question

У нас есть массив пользователей. Мы хотим сравнить каждого пользователя с любым другим пользователем по какой-то причине. Может ли его сложность быть меньше, чем n ^ 2? В настоящее время сравнение занимает n ^ 2 сложности. Я хочу, чтобы оно было меньше n ^ 2.

Answer 1

Если вам действительно нужно сравнить каждого пользователя с каждым другим пользователем, то сложность определяется по определению O (n * n).

На практике (как упомянуто в комментариях) требование вряд ли будет«сравнить каждого пользователя с каждым другим пользователем», но обычно «сортировать пользователей» или «найти наиболее похожего пользователя для каждого данного пользователя» или что-то подобное.Эти задачи имеют гораздо меньшую сложность.Однако вы должны сообщить нам, в чем заключается проблема, которую вы пытаетесь решить.

Answer 2

Нечто подобное, упомянутое в комментариях, будет работать. Это просто проблема с поиском элемента в массиве. Я полагаю, что вы выбираете пользователя, а затем вы получаете, например, имя пользователя, а затем вы нашли этого пользователя в массиве, чтобы найти другую информацию об этом пользователе. Вы можете сохранить пользователей отсортированными по значениям этого ключа, тогда вы можете найти его в O (logn). Также вы можете использовать хеш-таблицу, которая будет выполнять работу в постоянное время.