Cтраница 4
Изложенные рассуждения показывают, что на современном этапе поисков доказательства гипотезы о восстановлении нет также оснований рассчитывать, что такое доказательство даст, кроме того, хороший алгоритм. Поэтому в следующих разделах будут рассмотрены такие свойства графов, которые являются восстанавливаемыми, но, по всей вероятности, не выявляются с помощью хороших алгоритмов. [46]
Для обработки коллизий записи, входящие в класс коллизий, вместе с их ключами организуются в виде линейного списка, первый элемент которого размещается по адресу, получаемому при перемешивании. Для нахождения конкретной записи список просматривается и ключи записей сравниваются с заданным ключом. Хороший алгоритм перемешивания хотя и не сможет предотвратить возникновение коллизий совсем, обычно позволяет сохранять небольшой размер списков коллизий, делая приемлемым их последовательный просмотр. Отметим, что списки коллизий требуют дополнительной памяти. В то же время некоторые участки памяти могут остаться свободными из-за того, что ключи, соответствующие адресам этих участков, могут никогда не встретиться. Поэтому файл, для адресации записей которого используются методы перемешивания, неизбежно имеет дыры ( в связи с этим данный метод часто называют рассеянной памятью), но это вполне окупается получаемыми преимуществами. [47]
Эти функции характеризуют эффективность работы алгоритма наилучший вариант реализации) в наихудшем случае для всех начальных данных с фиксированной степенью сложности. Например, временная сложность многих алгоритмов сортировки оценивается величиной О ( n log п), где п - количество элементов массива данных. Хорошие алгоритмы синтаксического анализа языков программирования требуют времени порядка О ( п), где п - длина анализируемого текста. [48]
Хорошей мерой эффективности может быть С - число необходимых сравнений ключей и М - число пересылок ( перестановок) элементна. Хотя хорошие алгоритмы сортировки требуют порядка n ] ogn сравнений, мы сначала разберем несколько простых и очевидных методов, их называют прямыми, где требуется порядка п2 сравнении ключей. [49]
В случае большой ЭВМ проблема даже серьезней, чем в случае карманного калькулятора, так как на ЭВМ производится гораздо больше вычислений и на ней обычно нет индикации накопления большой ошибки. Вся забота о получении точных результатов ложится на программиста. Следует применять только хорошие алгоритмы и, если необходимо, контролировать промежуточные результаты, чтобы убедиться в правильности вычислений. [50]
Алгоритм идентификации деревьев использует каталожную систему, построенную на основе линейного упорядочения множества всех конечных деревьев. Однако наличие такой системы совершенно не обязательно. Например, существует хороший алгоритм для определения идентичности ( в комбинаторном смысле) любых двух поверхностных карт. Карты обладают свойством комбинаторной жесткости - так, что если карты MI и М2 идентичны и установлено, что ребро е в MI идентично ребру е2 в М2, конечная точка Vi ребра е идентична с конечной точкой v2 ребра е2 и грань fi, содержащая е, идентична с гранью f2, содержащей е2, идентификация оставшихся частей М и М2 однозначна и легко устанавливается. Из такой процедуры, конечно, непосредственно не следует система каталогизации карт. [51]