Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Сложность арифметических операций




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

В процессе переработки информации приходится выполнять арифметические действия.

В связи с этим возникает задача выбора наиболее эффективных способов решения, выбора эффективных алгоритмов.

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

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

Пусть число n є N в двоичной записи имеет число цифр S+1, т.е.

n = n0+ n1*2+ n2*22 + …+ ns*2s ; , где ns = 1

Значит 2s ≤ n < 2s+1 ⇒ S ≤ log2 n < S+1

Иногда вводят как обозначение log N – длина записи числа N.

В качестве оценки сложности алгоритма обычно выбирается время его работы. (max время для всех наборов данных).

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

Опр. Порядком роста функции f в точке z0 называется некоторое число α ≥ 0 такое, что для некоторой окрестности U0 существует такое число M > 0, что для произвольной точки z ϵ U0 выполняется неравенство

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

 







Дата добавления: 2014-12-06; просмотров: 500. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.004 сек.) русская версия | украинская версия