Cтраница 4
Все важные нижние оценки времени вычислений и объема памяти основаны на диагональных рассуждениях. Диагональные рассуждения использовались Тьюрингом и его современниками для доказательства того, что некоторые задачи алгоритмически неразрешимы. В 1960 г. Рабин [60] доказал, что для всякой разумной меры сложности, такой, как время вычисления или объем памяти, достаточное увеличение допустимого времени или объема памяти всегда позволяет вычислять большее число 0 - 1 функций. Примерно в то же время Ритчи в своей диссертации [65] определил специальную иерархию функций ( которая, как он показал, нетривиальна для 0 - 1 функций) в терминах объема доступной памяти. [46]
Функция нижней оценки, которая ставит в соответствие каждому частичному решению нижнюю оценку его стоимости, служащую оценкой всех полных решений, получаемых из данного частичного решения. [47]
Установление нижних оценок для характеристик работы алгоритмов решения определенной задачи - одна из главных целей анализа алгоритмов, поскольку они дают меру для оценки эффективности конкретных алгоритмов. [48]
Точность нижних оценок может быть повышена. Повышение точности нижних оценок имеет смысл, если априори или в процессе решения задачи становится известно, что возможные решения из множества допустимых достаточно близки по значениям характеристик (3.1.9) - (3.1.11) и (3.1.15), используемых для оценки оптимальности решений. [49]
Получение нижних оценок, линейных относительно п - числа аргументов функции ( или в общем случае относительно объема входной информации), обычно все-таки не вызывает больших трудностей. Получение более сильных нижних оценок - - значительно более сложная задача. Наиболее высокие нижние оценки, к-рые к настоящему времени ( 1984) удалось получить, имеют порядок и2, если не считать оценок, получающихся при очень сильных ограничениях на класс у. [50]
Вывод нижней оценки быстродействия Bmin процессора ( см. § 4.2) осуществлялся безотносительно к какой-либо дисциплине обслуживания. [51]
Получение нижних оценок сложности умножения целых чисел должно относиться к конкретной вычислительной модели. При очень разумных предположениях Патерсон, Фишер и Мей-ер [11] серьезно уменьшили разрыв между верхней и нижней оценками, показав следующее. [52]