Вс, 23.07.2017, 23:55
Главная
Регистрация
Вход
აბაშის ხმა
Приветствую Вас Гость | RSS
Меню сайта
Категории раздела
Алгебра
Алгебра Дж. Буля
Алгоритмы
Анализ
Векторы
Вейвлеты
Геометрия
Графики
Дзета-функция Римана
Задача Лагранжа
Интегралы
Математика
Математическая интуиция
Математические игры
Методы Рунге Кутты
Нестандартный анализ
Теория Графов
Уравнения
Численные методы оптимизации
Геометрия в пространстве
Мини-чат
200
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Главная » Статьи » Математика » Алгоритмы

Алгоритмы

Сложность теоретико-числовых алгоритмов

Сложность алгоритмов теории чисел обычно принято измерять количеством арифметических операций (сложений, вычитаний, умножений и делений с остатком), необходимых для выполнения всех действий, предписанных алгоритмом. Впрочем, это определение не учитывает величины чисел, участвующих в вычислениях. Ясно, что перемножить два стозначных числа значительно сложнее, чем два однозначных, хотя при этом и в том, и в другом случае выполняется лишь одна арифметическая операция. Поэтому иногда учитывают ещё и величину чисел, сводя дело к так называемым побитовым операциям, т. е. Оценивая количество необходимых операций с цифрами 0 и 1, в двоичной записи чисел. Это зависит от рассматриваемой задачи, целей автора и т. д.

На первый взгляд странным также кажется, что операции умножения и деления приравниваются по сложности к операциям сложения и вычитания. Житейский опыт подсказывает, что умножать числа значительно сложнее, чем складывать их. В действительности же, вычисления можно организовать так, что на умножение или деление больших чисел понадобится не намного меньше битовых операций, чем на сложение. Существует алгоритм Шенхаге – Штрассена, основанный на так называемом быстром преобразовании Фурье, и требующий O(ln n lnln nбитовых операций для умножения двух n-разрядных двоичных чисел. Таким же количеством битовых операций можно обойтись при выполнении деления с остатком двух двоичных чисел, записываемых не более чем n цифрами. Для сравнения отметим, что сложение n-разрядных двоичных чисел требует O(n) битовых операций.

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

Категория: Алгоритмы | Добавил: nukria (26.04.2012)
Просмотров: 145 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Вход на сайт
Поиск
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • | Copyright MyCorp © 2017 | |