Временная сложность

Для алгоритма выделяют – время работы в лучшем и худшем случае, а также среднее время работы.

Для алгоритмов определяют также порядок роста времени работы:

- линейные;

- квадратичный;

- логарифмический;

- экспонициальный (друдноразрушаемые – для них разрабатываются приближенные алгоритмы);

- полиноминальный – вычислимые за реальное время.

1) Ханойские башни,определение,алгоритм,формулировка

Существует легенда: «В храме Бендареса находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разного диаметра из чистого золота. Наибольший диск лежит на бронзовой плите и с остальными образует пирамиду, сужающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят диски с одного стержня на другой, следуя законам Брамы:

— 1) диски можно перемещать с одного стержня на другой только по одному;

— 2) нельзя класть больший диск на меньший;

— 3)при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски тоже могут находиться тоже только в виде пирамиды.

— Когда все 64 диска будут перенесены с одного стержня на другой, наступит конец света».

Алгорим Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносе m дисков с левого стержня на правый. Задача может быть решена одним перемещением только для одного (m = 1) диска.

Построим рекурсивное решение задачи, состоящее из трех этапов:

— a) перенести башню, состоящую из m – 1 диска, с левого стержня на средний;

— b) перенести один оставшийся диск с левого стержня на правый;

— c) перенести башню, состоящую из m – 1 диска, со среднего стержня на правый.

2)Порядок сложности алгоритма

Порядок сложности алгоритма выражает его эффективность обычно через количество обрабатываемых данных.

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

Порядок алгоритма - это функция, доминирующая над точным выражением временной сложности.

Функция f(n) имеет порядок O(g(n)), если имеется константа К и счетчик n0, такие, что f(n)(K*g(n), для n>n₀.

3)Временная сложность оператора присваивания

Временная сложность оператора присваивания определяется временем, затрачиваемым на вычисление значения выражения и присваивание этого значения переменной. Если значение выражения не принадлежит к данным основного типа, таким как целые числа, то в некоторых случаях можно уменьшить время с помощью указателей. Например, присваивание А - В, где А и В - матрицы размера пХп, обычно потребовало бы 0 (п2) шагов.

4) жадные алгоритмы

Жадный подход далеко не всегда дает оптимальное решение, но во многих случаях получаемое решение оказывается достаточно близким к оптимальному, а для некоторых задач известны и оптимальные жадные алгоримы (построение оптимального префиксного кода по Хаффману, построение остовного дерева максимального веса, планирование вычислений на процессоре с минимизацией ожидания и другие).

Основными достоинствами жадных алгоритмов является их простота и нетребовательность к ресурсам.

Жадные (градиентные) алгоритмы, действуют по принципу "максимальный выигрыш на каждом шаге". Такая стратегия не всегда ведет к конечному успеху - иногда выгоднее сделать не наилучший, казалось бы, выбор на очередном шаге с тем, чтобы в итоге получить оптимальное решение. Но тем не менее, существует большое количество задач, для которых применение жадных алгоритмов оказывается оправданным.

5)Класс P задач

В теории алгоритмов классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включён в более широкие классы сложности алгоритмов.

Поиск по сайту: