Wataru

Зависит от размеров item. Если они там каждый O(N) размера, то ваша догадка правильная: O(n^2 log n).

Если же все item суммарно не превосходят N, то ответ O(N log N). Потому что если их размеры a_i, то у вас сумма ai log ai. log(ai) можно сверху ограничить log(N) и вынести за скобки и потом заменить сумму в скобках на N.

Если скорость не особо важна, то просто пройдитесь по всем именным цветам (лучше, чтобы это был какой-то списко или массив, а не мап) и считайте какую-то метрику (например, сумма квадратов разности по каждому каналу отдельно). Из полученных чисел ищите минимум и выдавайте тот цвет, что ее дал.

Если надо работать очень быстро, то надо представить ваши именные цвета как точки в трехмерном пространстве, построить kd-дерево или r-дерево и уже в нем искать ближайшую к запрошенной точку.

Надо, как в бинарном поиске - идти или в левое или в правое поддерево. Если пошли в левое поддерево, то надо проверить, что вернула рекурсивная функция - если там не было больших элементов, то надо вернуть значение в текущей вершине.

Ну вот как вы прибавляете 1 к числу из 0..9 прибавляйте 1 к числу, где цифры могут быть 0..9 и a..z. Все z в конце замените на 0, следующий символ увеличте на 1 (если стало '9'+1, то Замените на 'a').

Вы генерируете перестановки по одной, пока не отсчитаете k. Это медленно, потому что k может быть очень большим. Перестановок-то n! - это дофига много.

Надо генерировать ее сразу по номеру.

Посмотрите на первый элемент. У первых (n-1)! перестановок там 1, у следующих (n-1)! - там 2, потом идет группа, начинающихся с 3 и т.д.

Уже вы можете понять в какой группе искомая k-ая перестановка. Тупо floor(k/(n-1)!) (если нумерация с 0 и перестановок и групп). Фактически, формула для первого элемента - a[0] = (k-1)/(n-1)! + 1.

Дальше вы можете выкинуть из рассмотрения первый элемент. Сфокусируйтесь на группе с заданным известным первым элементом. Какой номер искомая перестановка имеет среди этих (n-1)!? Надо из k вычесть количество перестановок c меньшими первыми элементами (их (a[0]-1)*(n-1)!. Потом задача сводится к преведущей - сгенерировать k-ую перестановку среди оставшихся n-1 элементов.

Если использовать какое-нибудь дерево отрезков, чтобы быстро искать j-ый пока не занятый элемент, то все решение будет за O(n log n). Если делать совсем просто - двумя циклами - то будет O(n^2). Гораздо быстрее вашего O(n!).

Надо только аккуратно обработать случаи, когда (n-1)! слишком большое. Фактически, вам надо найти максимальный факториал, который меньше k. Пока не спуститесь до этого момента нужно сразу брать первый незанятый элемент и не считать факториал вообще.

Не специалист по JS, но похоже там можно сделать проще чем стандартный обход графа в ширину/глубину.

Заведите мап объектов, которые будете собирать. Ключи будудт айдишники, а значения - объекты. У объектов заполните uid, parentUID, пустой Map children и пустой список children_list. Так же запомните куда-то id, у которого null отец.

Потом еще одним проходом по списку всех элементов заполните children_list у всех обхектов в Map из прошлого шага (кладите текущий id в список для parentUID).

Потом еще одним проходом по всем элементам этого Map соберите дерево: обойдите список детей и в Map children кладите 'id' => объект из внешнего Map'а по данному ключу. После прохода можно children_list удалить.

Если я правильно понимаю, как работает JS, то у вас будет не копироваться объект а его ссылка. В итоге в Map будут осодержаться вообще все поддеревья ссылыющееся друг на друга. Можно потом вырвать оттуда объект по ключу id корня и Map удалить.

Посмортите на метод Гаусса. Там получается диагональная матрица путем прибавления одной строки к другим и перестановки строк. Так вот - прибавление одной строки к другой с коэффициентом - это и есть домножение матрицы на трансвекцию.

Единственная проблема - надо переставлять строчки местами. Тут вам поможет класический пазл о помене двух чисел без использования вспомогательных переменных:

a = a + b;
b = a - b;
a = a - b;

Эти три операции поменяют местами a и b. При чем они уже выглядят как трансвекции - только вторая операция не совсем вида a += b*k.

Но можно чуть чуть поменять:

a = a + b;
b = b - a;
a = a + b;

Тут три трансвекции и строки меняются местами, только одна из них домножается на -1. Но это домножение метод гауса нисколько не меняет.

Вот и ваш алгоритм.

Никак. Есть методы получить число, которое будет стоять на заданной позиции (или числа на отрезке) в отсортированном массиве быстрее сортировки (алгоритм QuickSelect). Как-то быстрее сортировки найти все числа на нечетных позициях - нельзя.

Edit: Если стандартная сортировка не работает и L большое, то стоит посмотреть в сторону radix sort. Если бы L было относительно небольшим - то лучший вариант был бы сортировка подсчетом.

Вам нужно сделать побитовое И с маской, где стоят 0 в нужных вам разрядах (и 1 в остальных). Маску можно задавать прямо бинарной или шестнадцатеричной константой.