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

Упражнение 2.2.1

Выразите функцию n³/1000 - 100n² - 100т + 3 в O - обозначениях.

Для определения скорости роста и упрощения анализа выбираем член с наибольшим порядком.

n³/1000 - 100n² - 100т + 3 = O(n³)

Упражнение 2.2.2

Сортировка выбором

Реализация на языке Python:

def selection_sort(array):
	for j in xrange(0, len(array)):
		tmp = j
		for i in xrange(j+1, len(array)):
			if array[tmp] > array[i]:
				tmp = i
		array[tmp], array[j] = array[j], array[tmp]
	return array

Для сортировки по убыванию меняем if array[tmp] < array[i]:

Какой инвариант цикла сохраняеться для этого алгоритма?

xz

Укажите время его работы в лучшем и худшем случаях, используя O - обозначения.

Вычеслительная сложность в лучшем случае: O(n)

Вычеслительная сложность в худшем случае: O(n²)

Упражнение 2.2.3

Сколько сравнений потребуеться в среднем этому алгоритму, если искомым элементом может быть любой елемент массива(с одинаковой вероятностью)

xz

Каково время работы в худшем случае и в среднем ? Как записать эти времена с помощью O обозначений ?

В худшем случае время работы будет n-1, в лучшем: алгоритм поиска остановиться на 1-й же итерации. Соответсвенно в среднем время работы будет n/2.

Записав это в O обозначении получаем: O(n) - в худшем и в среднем случаях.

Упражнение 2.2.4

Каким образом можно модифицировать почти каждый алгоритм, что бы получить оптимальное время работы в наилучшем случае ?

xz