Начнем с того, что алгоритм – это точная инструкция, однозначно определяющая вычислительный процесс. Разумеется, очень хорошо иметь возможность оценить ресурсы, затрачиваемые на выполнение этого алгоритма. Результатом данной оценки и является сложность, которая показывает, какое количество памяти и времени требуется для алгоритма. Давайте изобразим работу алгоритма наглядно: Проанализируем простенькую программку: a = [3,5,8,1,9,7] n = 6 for i in a:     print(i) Обозначим время выполнения программы T, а N – за длину списка...

Предыдущая часть Ранее рассмотренные методы давали нам оценку сложности не лучше чем O(N²), так что, конечно, возникает вопрос – а можно ли её вообще улучшить? Да, но только это всегда будет приводить к некоторым ограничениям. Сортировка подсчётом Весьма оригинальный и супер-простой метод сортировки. Если на входе нам дан массив целых чисел, где каждое число находится в диапазоне от 0 до R, то после сортировки мы должны получить ряд возрастающих чисел: 0, 1, 2, 3, 4, 5, 6, ... R Но не все числа могут в нём присутствовать, а некоторые числа могут повторяться несколько раз...