Временная сложность

Cтраница 1

Временная сложность этого алгоритма есть О ( и), так как число выполнений оператора if равно ( п - 1), а число выполнений остальных операторов не зависит от размерности задачи. [1]

Временная сложность нашего алгоритма зависит от того, насколько нам повезет при разбиении сортируемого списка. Если списки всегда разбиваются на два списка примерно равной длины, то процедура сортировки имеет временную сложность порядка nlogn, где п - длина исходного списка. Анализ показывает, что, к счастью, средняя производительность быстрой сортировки ближе к лучшему случаю, чем к худшему. [2]

Временная сложность в худшем случае ( или просто временная сложность) РАМ-программы - это функция / ( л), равная наибольшей ( по всем входам размера п) из сумм времен, затраченных на каждую сработавшую команду. Временная сложность в среднем - это среднее, взятое по всем входам размера п, тех же самых сумм. [3]

Временная сложность процедуры определяется числом и размером подзадач и в меньшей степени работой, необходимой для разбиения данной задачи на подзадачи. Так как рекуррентные уравнения вида (2.2) и (2.5) часто возникают при анализе рекурсивных алгоритмов типа разделяй и властвуй, рассмотрим решение таких уравнений в общем виде. [4]

Временная сложность программ в основном определяется алгоритмами, используемыми для решения задач. Несмотря на возрастание быстродействия современных ЭВМ, имеется много задач, которые невозможно решать некоторыми точными алгоритмами при необходимом объеме входных данных. При ограниченной области изменения входных данных имеется возможность эффективного ускорения вычислений. Теоретически доказана принципиальная возможность размена длительности решения любых задач на объем памяти для хранения программ и данных. При реальной производительности ЭВМ достижимое качество программ может существенно определяться их временной сложностью. Это означает, что длительность исполнения программ по тестовым данным и длительность расчета эталонных значений возрастают так быстро, что реальные ресурсы современных ЭВМ ограничивают допустимую полноту отладки и объем получаемых результатов. [5]

Временная сложность описанного алгоритма ориентировочно составляет О ( га2) для одной генерации. [6]

Дерево решений. [7]

Временная сложность дерева решений равна высоте этого дерева как функции размера задачи. Обычно мы хотим измерить наибольшее число сравнений, которые приходится делать, чтобы найти нужный путь от корня к листу. [8]

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

Если временная сложность Т ( п) машины Тьюринга не превосходит некоторого полинома от п, то будем говорить, что данная машина имеет полиномиальную временную сложность. [10]

Подсчитаем временную сложность последовательности из п операций ВСТАВИТЬ, когда рассматриваемое множество представлено деревом двоичного поиска. Время, требуемое, чтобы в дерево двоичного поиска вставить элемент а, ограничено по порядку числом сравнений, производимых между а и элементами, уже находящимися в дереве. [11]

Оценим временную сложность реализации процедур, описанных в пп. [12]

Оценим временную сложность процедур разрешения коллизий как функцию от числа N масштабируемых операций. [13]

Фактически же временная сложность не превышает О ( № п): цикл while не нужно выполнять более одного раза, потому что, если строка не удаляется при первой итерации, она не будет удалена и при любой последующей итерации, как показывает следующая ниже лемма. [14]

Алгоритмы, временная сложность которых не поддается такой оценке, называются экспоненциальными. [15]

Страницы: 1 2 3 4