Какой алгоритм сортировки сортирует массив с временной сложностю O(n * (N))?

Question

[Andrey Kubishenko]

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

Answer 1

[Luke LikeSkywalker]

Bubble sort. Любой алгоритм сложности O(n^2)
Прочитай книжку Гроккаем алгоритмы. Там есть про Big(O) time complexity

Comments

[Andrey Kubishenko]

Спасибо

Answer 2

[tsarevfs]

Судя по разным буквам n и N имеется в виду сортировка подсчетом. Время ее работы зависит от размера массива n и количества возможных значений в массиве N. Так, например, если мы хотим отсортировать массив состоящий из чисел от 1 до 10, то мы можем сделать это за линейное время.
Кормен "Алгоритмы: построение и анализ" подойдет как справочник.