Какой алгоритм сортировки сортирует массив с временной сложностю O(n * (N))?
Недавно наткнулся на задачу (на js). Суть в том, что надо создать функцию sort(), с временной сложностю O(n * (N)). Так как я далёк от алгоритмических структур и прочего связанного с алгоритмами - это ввело меня в ступор. Вот я и прошу вас объяснить алгоритм решения данной задачи. А также прошу скинуть какие-то материалы, где можно узнать об временных сложностях алгоритмов, сам я не нашёл нормальных.
Судя по разным буквам n и N имеется в виду сортировка подсчетом. Время ее работы зависит от размера массива n и количества возможных значений в массиве N. Так, например, если мы хотим отсортировать массив состоящий из чисел от 1 до 10, то мы можем сделать это за линейное время.
Кормен "Алгоритмы: построение и анализ" подойдет как справочник.
