Допустим, у вас на компьютере записана музыка и для каждого исполнителя хранится счетчик воспроизведений.
Вы хотите отсортировать список по убыванию счетчика воспроизведений, чтобы самые любимые исполнители стояли на первых местах. Как это сделать?
Одно из возможных решений - пройти по списку и найти исполнителя с наибольшим количеством воспроизведений . Этот исполнитель добавляется в новый список.
Потом то же самое происходит со следующим по количеству воспроизведений исполнителем.
Продолжая действовать так, мы получаем отсортированный список.
А теперь попробуем оценить происходящее с точки зрения теории вычислений и посмотрим, сколько времени будут занимать операции. Напомним, что время О(n) означает, что вы по одному разу обращаетесь к каждому элементу списка. Например, при простом поиске по списку исполнителей каждый исполнитель будет проверен один раз.
Чтобы найти исполнителя с наибольшим значением счетчика воспроизведения, необходимо проверить каждый элемент в списке. Итак, имеется операция, выполняемая за время О(n), и ее необходимо выполнить n раз.
Все это требует времени О(n2).
На следующем шаге рассмотрим код программы.
