Сложность алгоритмов (Python)

операционной системой, которые могут влиять на длительность вычисления. Поэтому на одних ЭВМ одни и те же программы могут работать быстрее, на других – медленнее. При разработке алгоритма решения какой-либо задачи эти особенности разных устройств не учитываются, а анализ алгоритмов проводят на так называемой «модели абстрактного вычислителя, называемого машиной с произвольным доступом к памяти (RAM)».
Цель работы – рассмотреть сложность алгоритмов (Python).
Задачи:
- исследовать временную сложность алгоритма;
- определить алгоритм пузырьковой сортировки (bubblesort);
- рассмотреть алгоритм сортировки выбором (SelectionSort);
- проанализировать алгоритм сортировки вставками (InsertionSort).
Одной из причин простоты, которой отличается программирование на Python, является то, что он поставляется с инструментами, которые помогут разрабатывать, писать и отлаживать программы.

1. Временная сложность алгоритма

Зачастую выбор между эффективным и неэффективным решением задачи даже может означать выбор между реализуемым и нереализуемым способом ее решения. Например, есть классическая задача, которая называется «Коммивояжер», в которой требуется найти наименьшую возможную длину кольцевого маршрута, проходящего по одному разу через все города.
Можно построить решение этой задачи простым перебором всех возможных вариантов построения маршрута: перебирая все возможные перестановки городов с фиксированным начальным городом. Анализ сложности такого алгоритма показал, что обработка одного маршрута потребует Cn операций (С – константа), и этот процесс придется повторить (n-1) раз. При n=5 данную задачу можно в принципе решить вручную (потребуется выполнить 120 операций), при n=10 уже потребуется быстродействующая ЭВМ (3,6*106) операций, а для n=15 даже суперкомпьютер не поможет .
То есть в данном примере мы видим, что незначительные изменения входных данных в задаче приводят к быстрому росту количества операций, необходимых для решения этой задачи предложенным методом – алгоритм перебора.
Здесь как раз и возникает вопрос об эффективности алгоритма: выбор между эффективным и неэффективным алгоритмом означает выбор между реализуемым и нереализуемым решением задачи.
Поскольку временная сложность алгоритма зависит от количества операций в алгоритме, то позволяет сравнить эффективность алгоритмов. Однако, чаще анализ проводят с расчетом на достаточно большой объем обрабатываемых данных (n→∞), поэтому ключевое значение имеет скорость роста функции сложности, а не точное количество операций.
При анализе скорости роста не учитываются постоянные члены и множители в выражении, т.е. функции f(x)=10x2+20 и g(x)=2x2 эквивалентны между собой.
В оценке алгоритмов используются специальные асимптотические обозначения, задающие следующие классы функций:
- O(g) – функции, растущие медленнее, чем g; (О большое);
- Ω(g) – функции, растущие быстрее, чем g; (Омега большое);
Θ(g) – функции, растущие с той же скоростью, что и g. (Тета большое) .
Запись f(n)=O(g(n)) означает, что функция f ограничена сверху функцией g для достаточно больших значений аргумента (см. Рисунок 1).

Рис. 1. Оценка алгоритмов.
Одномерный список представляет собой последовательность элементов, пронумерованных от 0, как символы в строке. Список можно задать перечислением элементов списка в квадратных скобках, например, так: А = [2, 3, 5, 7, 11, 13].
Считывание элементов списка, если они были введены в одной строке через пробел, производится с помощью команды B = list(map(int, input().split())).

2. Алгоритм пузырьковой сортировки (bubblesort)

Основная идея алгоритма. Пройдем по всему списку А слева направо. Если есть два неправильно упорядоченных элемента, то есть A[i] > A[i+1], — переставим их. В результате самый большой элемент списка «всплывет» в его конец — станет последним элементом. Повторим этот проход еще раз — второй по величине элемент списка «всплывет» в конец, остановившись перед наибольшим элементом. За следующий проход мы можем установить на место третий элемент и т. д. При этом последние, уже «всплывшие» наибольшие элементы не нужно затрагивать алгоритмом сортировки.
Подпрограмма на языке Python.
defBubbleSort(A):
for j in range(len(A) - 1, 0, -1):
for i in range(j):
if A[i] > A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]
returnA
Оценка временной сложности алгоритма обменами. Пусть список содержит n элементов. Сначала за первый проход по списку наибольший элемент «всплывет» на свое место (в конец списка), для этого понадобится n-1 операция. За второй проход второй по максимуму элемент «всплывет» на второе с конца место: для этого понадобится (n-2) операции, и т.д. Общее число операций равно (n−1)+(n−2)+…+1=n(n-1)/2=O(n2), то есть количество операций сравнения, нужных для выполнения сортировки списка, меньше либо равно некоторой константы, умноженной на n2.
В нашем случае количество операций n(n-1)/2. Почему оно <=Cn2? Действительно, n(n-1)/2<= n2/2=1/2 n2 или Cn2. То есть, если у нас n элементов списка, то понадобится n2 операций, а если элементов списка станет в 10 раз больше, то количество операций вырастет в 100 раз: 100 n2.