Пузырьковая сортировка

Оценка времени исполнения алгоритмов. Символ O()

Характеристики сортировок

Методы упорядочивания данных со статическими связями. Алгоритмы сортировок

1. Время сортировки.

2. Дополнительная память, необходимая для сортировки.

1. Устойчивость. Устойчивой сортировкой является та, которая не меняет взаимного расположения одинаковых элементов.
2. Естественность поведения. Под этим понятием понимается эффективность работы алгоритма в случае отсортированных или частично отсортированных данных. Естественный - учитывает этот факт и работает быстрее. Неестественный метод этот факт не учитывает, либо бывает, что работает даже хуже.

Для оценки производительности алгоритма можно использовать различные подходы. Самый простой из них - это запустить алгоритм и сравнить время его выполнения на разных задачах. Более научный подход заключается в оценке с использованием символа О(). Этот символ зависит от числа n, где n - это число обработанных чисел. Такую оценку называют асимптотикой, так как она обозначает асимптотическое поведение алгоритма при n→∞. Когда используют данную оценку, имеют в виду не точное время исполнения, а только его предел сверху с точностью до постоянного множителя.

Например, когда алгоритму требуется времени О(n^2), имеется в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов.

Таблица 1 иллюстрирует скорость роста для различных функций О:

Таблица 1. Скорость роста для различных функций O

N	log (n)	n * log (n)	n^2
16	4	64	256
256	8	2`048	65`536
4`096	12	49`152	16`777`216
65`536	16	1`048`565	4`294`967`296
1`048`476	20	20`969`520	1`099`301`922`576
16`775`616	24	402`614`784	281`421`292`179`456

Если считать, что числа в таблице соответствуют микросекундам, то для сортировки 1 миллиона элементов алгоритму, обладающему эффективностью O(log(n)) потребуется 20 микросекунд, а алгоритму с эффективностью O(n^2), - более 12 дней.

Если оба алгоритма имеют оценки эффективности O(n*log(n)), это не значит, что они одинаково эффективны, так как оценка O не учитывает константу, то есть первый алгоритм может быть эффективнее в 1000 раз, чем второй.

За функцию берется количество операций, возрастающее быстрее всего. То есть если в программе одна функция выполняется O(n) раз - например, умножение, а сложение - O(n^2) раз, то общая сложность - O(n^2), так как n^2 возрастает быстрее. Практический смысл этого такой: при увеличении n более быстрые (в определенное, константное число раз) сложения станут выполняться настолько часто, что будут влиять на производительность много сильнее, нежели медленные, но редкие умножения

Кроме символа O() используются также оценки Omega() - нижняя оценка, Theta() - комбинация O() и Omega(): точная оценка асимптотики.

Интуитивный смысл оценок:

• f = O(g), f растет не быстрее, чем g, при n→∞.
• f = Omega(g), f растет не медленнее,чем g при n→∞.
• f = Theta(g), а растет примерно также, как g при n→∞.

1. Общее быстродействие O(n^2), поэтому на практике практически не используется.

2. Дополнительные затраты на память. Сортировка происходит на месте.

3. Устойчивая.

4. Поведение неестественное.

Идея метода:

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию. Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент.

Дата добавления: 2014-01-11