График роста o большое

Сложности алгоритмов.

Поиск

Сортировка

Числа Фибоначчи

Последовательность Фибоначчи определяется следующим образом:

Несколько первых её членов:

Свойства

Правило "сложения":

Теорема Цекендорфа утверждает, что любое натуральное число можно представить единственным образом в виде суммы чисел Фибоначчи:

где , , , (т.е. в записи нельзя использовать два соседних числа Фибоначчи).

По отношению к алгоритму Евклида числа Фибоначчи обладают тем замечательным свойством, что они являются наихудшими входными данными для этого алгоритма (см. "Теорема Ламе" в Алгоритме Евклида).

Алгоритм Евклида нахождения нод (наибольшего общего делителя)

Даны два целых неотрицательных числа и . Требуется найти их наибольший общий делитель, т.е. наибольшее число, которое является делителем одновременно и , и . На английском языке "наибольший общий делитель" пишется "greatest common divisor", и распространённым его обозначением является :

(здесь символом " " обозначена делимость, т.е. " " обозначает " делит ")

Когда оно из чисел равно нулю, а другое отлично от нуля, их наибольшим общим делителем, согласно определению, будет это второе число. Когда оба числа равны нулю, результат не определён (подойдёт любое бесконечно большое число), мы положим в этом случае наибольший общий делитель равным нулю. Поэтому можно говорить о таком правиле: если одно из чисел равно нулю, то их наибольший общий делитель равен второму числу.

Алгоритм Евклида, рассмотренный ниже, решает задачу нахождения наибольшего общего делителя двух чисел и за .

Алгоритм

Сам алгоритм чрезвычайно прост и описывается следующей формулой:

Реализация

int gcd (int a, int b) {

if (b == 0)

return a;

else

return gcd (b, a % b);

}

Используя тернарный условный оператор C++, алгоритм можно записать ещё короче:

int gcd (int a, int b) {

return b ? gcd (b, a % b) : a;

}

Наконец, приведём и нерекурсивную форму алгоритма:

int gcd (int a, int b) {

while (b) {

a %= b;

swap (a, b);

}

return a;

}

Время работы

Время работы алгоритма оценивается теоремой Ламе, которая устанавливает удивительную связь алгоритма Евклида и последовательности Фибоначчи:

Если и для некоторого , то алгоритм Евклида выполнит не более рекурсивных вызовов.

Более того, можно показать, что верхняя граница этой теоремы — оптимальная. При будет выполнено именно рекурсивных вызова. Иными словами, последовательные числа Фибоначчи — наихудшие входные данные для алгоритма Евклида.

Учитывая, что числа Фибоначчи растут экспоненциально (как константа в степени ), получаем, что алгоритм Евклида выполняется за операций умножения.

Сортировка.

Пузырьковая.

1.6 Алгоритмы сортировки.

Пузырьковая сортировка. Наименее эффективна, но наиболее проста в реализации. Программный код соответствующего алгоритма приведен в листинге 1.1.

Листинг 1.1 – Реализация пузырьковой сортировки

template <class T>

void bubbleSort(vector<T> &v) {

int in, out, tmp;

for(out = v.size()-1; out>0; --out) {

for(in = 0; in<out; ++in) {

if(v[in] > v[out]) {

tmp = v[in];

v[in] = v[out];

v[out] = tmp;

} } } }

Произведем аналитическую оценку реализации алгоритма пузырьковой сортировки, приведенную в листинге 1.1, путем подсчета количества выполняемых операций сравнения. Для этого обозначим размер массива через : .

Размером входа рассматриваемого алгоритма есть размер (количество элементов) сортируемого массива .

Из листинга 1.1 видно, что на 1-м проходе внешнего цикла выполниться сравнений, на 2-м проходе – сравнения, и т.д. Таким образом, для сортировки (по возрастанию) элементов массива необходимо выполнить сравнений. Например, для массива из элементов таких сравнений потребуется выполнить 45. Количество перестановок, обусловленных выполнимостью -условий, в худшем случае не будет превышать значения – когда на вход алгоритма подана последовательность элементов, отсортированных в порядке убывания.

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

Сортировка методом выбора.

Сортировка методом вставки.

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому^[1]. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).

2. Пусть переменная p изначально равна двум — первому простому числу.

3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).

4. Найти первое незачеркнутое число в списке, большее чем p, и присвоить значению переменной p это число.

5. Повторять шаги 3 и 4, пока возможно.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p², потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p² станет больше, чем n.^[2] Также, все p большие чем 2 — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p².