Статья 2304

В итоге, получается выражение, которое вновь включает в себя гармонический ряд. Средняя длина пути для дерева, построенного без учета балансировки, логарифмически зависит от количества узлов и отличается от длины оптимального дерева на постоянный коэффициент. Среднее дерево гораздо меньше отличается от оптимального, чем самое плохое, - его путь длиннее оптимального на 38 процентов.
Все рассмотренные мной программы не тривиальны, однако они очень короткие. В практических приложениях программы, как правило, длиннее и запутаннее складывается впечатление, что они растут столь же быстро, как и память компьютеров, на которых их можно пропускать. Могут ли применяться приведенные мною методы анализа к таким программам. Я убежден, что не только могут, но и должны, ибо сложные системы требуют строгого обоснования в еще большей мере, чем простые.
Большинство крупных систем программного обеспечения опирается на очень малое число глубинных алгоритмов в известной мере они строятся на базовых алгоритмах типа умножения и поиска, которые выступают в различных вариантах и комбинациях. В то же время структуры данных, как правило, чрезвычайно сложны. В результате выбор правильного представления данных часто служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма.
Вряд ли когда-нибудь появится общая теория выбора структур данных. Самое лучшее, что можно сделать, - это разобраться во всех базовых кирпичиках и собранных из них структурах. Способность приложить эти знания к конструированию больших систем - это прежде всего дело инженерного мастерства и практики. Овладевая таким мастерством, программист должен постоянно бороться с запутанностью, отказываться доверять тем методам, которые не до конца поняты, и никогда не прекращать поиск более простых, более элегантных решений.