Архив категории ‘Сложность алгоритма’

Возведение целого числа без знака в положительную целую степень

    На этом шаге мы рассмотрим возведение целого числа без знака в положительную целую степень.     Вычисление у = хn для вещественных x и n не представляет никакого труда: y = en*ln(x). Но для целых чисел этот способ неприменим, поскольку вычисления экспоненты и логарифма на цифровой вычислительной машине принципиально являются приближенными и не будут давать […]

Задача перемножения длинных целых чисел без знака

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

Рекурсивный алгоритм умножения матриц

    На этом шаге мы рассмотрим рекурсивный алгоритм умножения матриц.     Классический итеративный алгоритм перемножения квадратных матриц размера n*n имеет сложность O(n3), а нижняя оценка сложности не менее O(n2). Следовательно, оптимальный алгоритм имеет сложность, заключенную в этом узком коридоре. Отыскивая алгоритм в классе алгоритмов, разбивающих задачу на a подзадач в c раз меньшего размера с […]

Оптимизация алгоритмов

    На этом шаге мы рассмотрим оптимизацию алгоритмов.     Одна из задач, которая обычно ставится при разработке алгоритмов и программ - минимизация требуемых программой ресурсов. Особенно это касается системного программного обеспечения: программ операционной системы, трансляторов, систем управления базами данных и знаний и т. д., т.е. программ, имеющих большое количество пользователей и испытывающих как товар, большую […]

Балансировка деревьев

    На этом шаге мы рассмотрим балансировку деревьев.     Если хотим, чтобы дерево, которое строим, никогда не выродилось в список, можно прибегнуть к процедуре балансировки. Балансировка - это метод, позволяющий не допустить возникновения слишком плохих деревьев. Обсудим здесь лишь основную идею алгоритма, оставив детали реализации для самостоятельных упражнений.     Высотой дерева называется длина самой длинной […]

Число вырожденных деревьев

    На этом шаге мы рассмотрим число вырожденных деревьев.     Вырожденное дерево - это линейный список. Мы уже приводили примеры вырожденных деревьев: список левых потомков и список правых потомков. Но это не единственные вырожденные деревья. Условием вырожденности дерева является наличие у любой вершины, кроме последней, только одного потомка. На рисунке 1 приведены все возможные вырожденные […]

Число бинарных деревьев

    На этом шаге мы рассмотрим число бинарных деревьев.     Число бинарных деревьев определяется, исходя из рекурсивного определения бинарного дерева: число деревьев с n вершинами определяется как сумма чисел возможных комбинаций левых и правых поддеревьев. Это дает возможность составить уравнения, решение которых и дает искомое число.     Обозначим tn - число различных бинарных деревьев, содержащих […]

Сложность операций с бинарными деревьями

    На этом шаге мы рассмотрим сложность операций с бинарными деревьями.     Бинарные деревья часто используются для хранения информации. Они выгодно отличаются от массивов фиксированного размера своим динамическим характером, возможностью почти неограниченно увеличивать объемы хранимой информации. От линейных списков их отличают лучшие временные характеристики - например, при поиске элемента (наиболее часто используемой операции) требуется в […]

Особые случаи анализа сложности рекурсивных алгоритмов

    На этом шаге мы рассмотрим осбые случаи анализа сложности рекурсивных алгоритмов.     Если функция f(Х) преобразования аргумента при рекурсивном вызове нелинейна, то аналитическое отыскание функции сложности алгоритма редко бывает возможно. Общих методов в этом случае нет, и приходится привлекать сведения из соответствующей проблемной области, а не только информацию о структуре программы. Аналогичная ситуация имеет […]

Случай косвенной рекурсии

    На этом шаге мы рассмотрим случай косвенной рекурсии.     Если две процедуры A и B связаны косвенной (взаимной) рекурсией, то для каждой из них можно записать выражения функции сложности и объединить их в общую систему уравнений. Поскольку одна из процедур, например, B имеет нерекурсивную ветвь, то эта ветвь порождает начальные условия. В простом случае […]