Алгоритмы и структуры данных

Быстрорастущие функции доминируют над функциями с более медленным ростом. Поэтому если сложность алгоритма представляет собой сумму двух или нескольких таких функций, то можно отбросить все функции, кроме тех, которые растут быстрее всего. Если, например, алгоритм делает x 3 -30x сравнений, то его сложность растет как x 3 . Причина этого в том, что уже при x = 100 входных данных разница между x 3 и x 3 -30x составляет лишь 0,3%. Скорость роста сложности алгоритма определяется старшим, доминирующим членом формулы. Поэтому можно пренебрегать младшими членами, которые растут медленнее. Отбросив все младшие члены, мы получаем то, что называется порядком функции или алгоритма, скоростью роста сложности которого она является. Алгоритмы, сложность которых: - растёт по крайней мере так же быстро, как данная функция При занятии эффективностью алгоритмов, класс Ω(f) не представляет большого интереса: например в Ω(n 2 ) входят все функции, растущие быстрее, чем n 2 , скажем...

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

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

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом, или корнем. Бинарное дерево с N узлами имеет не меньше ⌊log 2 N + 1⌋ уровней (при максимально плотной упаковке узлов). Например, у полного бинарного дерева с 15 узлами один корень, два узла на втором уровне, четыре узла на третьем уровне и восемь узлов на четвертом уровне; наше равенство также даёт ⌊log 2 15⌋ + 1 = ⌊3,9⌋ + 1 = 4 уровня. Добавление еще одного узла к дереву приведет к появлению нового уровня, и их число станет равным ⌊log 2 16⌋ + 1 = ⌊4⌋ + 1 = 5. В самом большом бинарном дереве с N узлами N уровней: у каждого узла этого дерева в точности один потомок (и само дерево представляет собой список). Если уровни дерева занумеровать, считая, что корень лежит на уровне 1, то на уровне с номером k лежит не более чем 2 k - 1 узл...

Анализ среднего случая является самым сложным, поскольку он требует учета множества разнообразных деталей.  В основе анализа лежит определение различных групп, на которые следует разбить возможные входные наборы данных. На втором шаге определяется вероятность, с которой входной набор данных принадлежит каждой группе. На третьем шаге подсчитывается время работы алгоритма на данных из каждой группы. Время работы алгоритма на всех входных данных одной группы должно быть одинаковым, в противном случае группу следует разбить ещё раз. Среднее время работы вычисляется по формуле: ,  где n - размер входных данных; m - число групп; p i - вероятность того, что входные данные принадлежат группе с номером i; t i - время необходимое алгоритму для обработки данных из группы с номером i. И разбиение на группы, и значения параметров p i  и t i  зависят от n. Если вероятность попадания входных данных в каждую из групп одинакова, то среднее время работы ...

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