Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Основные понятия.rtf
Скачиваний:
9
Добавлен:
01.04.2015
Размер:
317.79 Кб
Скачать

Анализ алгоритмов

Рассматривая различные алгоритмы решения одной и той же задачи, по­лезно проанализировать, сколько вычислительных ресурсов они требуют (время работы, память), и выбрать наиболее эффективный. Конечно, надо договориться о том, какая модель вычислений используется. В качестве модели используется обычная однопроцессорная машина с произвольным доступом (random-access machine, RAM), не предусматривающая параллельного выполнения операций.

Сортировка вставками: анализ. Время сортировки вставками зависит от размера сортируемого массива: чем больше массив, тем больше может потребоваться времени. Обычно изучают зависимости времени работы от размера входа. (Впрочем, для алгоритма сорти­ровки вставками важен не только размер массива, но и порядок его элементов: если массив почти упорядочен, то времени требуется меньше.)

Как измерять размер входа (input size)? Это зависит от конкретной задачи. В одних случаях размером разумно считать число элементов на входе (сорти­ровка, преобразование Фурье). В других более естественно считать размером общее число битов, необходимое для представления всех входных данных. Иног­да размер входа измеряется не одним числом, а несколькими (например, число вершин и число рёбер графа).

Временем работы (running time) алгоритма мы называем число элементар­ных шагов, которые он выполняет — вопрос только в том, что считать эле­ментарным шагом. Мы будем полагать, что одна строка псевдокода требует не более чем фиксированного числа операций (если только это не словесное описание каких-то сложных действий — типа «отсортировать все точки по x-координате»). Мы будем различать также вызов (call) процедуры (на который уходит фиксированное число операций) и её исполнение (execution), которое может быть долгим.

Итак, вернёмся к процедуре Insertion-Sort и отметим около каждой стро­ки её стоимость (число операций) и число раз, которое эта строка исполняется. Для каждого j от 2 до n (здесь n = length[A] — размер массива) подсчитаем, сколько раз будет исполнена строка 4, и обозначим это число через tj. (Заме­тим, что строки внутри цикла выполняются на один раз меньше, чем проверка, поскольку последняя проверка выводит из цикла.)

Insertion-Sort(A) стоимость число раз

1 for(j=2;j<=n;j++){ c1 n

2 key=A[j]; c2 n-1

3 i=j-1; c3 n-1

4 while (i>0 && A[i]>key){ c4j=2ntj

5 A[i+1]=A[i]; c5j=2n(tj-1)

6 i=i-1; c6j=2n(tj-1)

7 }

8 A[i+1]=key; c8 n-1

9 }

Строка стоимостью с, повторённая m раз, даёт вклад cm в общее число опе­раций. (Для количества использованной памяти этого сказать нельзя!) Сложив вклады всех строк, получим

T(n)=c1n+c2(n-1) +c3(n-1)+c4j=2ntj+c5j=2n(tj-1)+c6j=2n(tj-1)+c8(n-1)

Как мы уже говорили, время работы процедуры зависит не только от n, но и от того, какой именно массив размера n подан ей на вход. Для процедуры Insertion-Sort наиболее благоприятен случай, когда массив уже отсортиро­ван. Тогда цикл в строке 4 завершается после первой же проверки (поскольку А[i]≤key при i=j-1), так что все tj равны 1, и общее время есть

T(n)=c1n+c2(n-1) +c3(n-1)+c4(n-1) +c8(n-1)= (c1234+ с8)n - (с234+ с8).

Таким образом, в наиболее благоприятном случае время Т(n), необходимое для сортировки массива размера га, является линейной функцией (linear function) от n, т.е. имеет вид Т(n) = аn-b для некоторых констант а и b. (Эти константы определяются выбранными значениями с1,...,с8.)

Если же массив расположен в обратном (убывающем) порядке, время работы процедуры будет максимальным: каждый элемент A[j] придётся сравнить со всеми элементами А[1],..., A[j-1]. При этом tj=j. Поскольку

j=2nj=n(n+1)/2-1, ∑j=2n(j-1)=n(n-1)/2,

получаем, что в худшем случае время работы процедуры равно

Т(п)=с12(п-1) 3(п-1) + с4 (n(n+1)/2-1)+c5+c6)(n(n-1)/2)+c8(n-1)= 0.5(c4+c5+c6)n2+(c1+c2+c3+0.5(c4-c5-c6+c8)n-(c2+c3+c4+c8).

Теперь функция Т(n) — квадратичная (quadratic function), т.е. имеет вид Т(п)=an2 + bn + с. (Константы а, b и c здесь также определяются значениями c1, ... ,с8.)