Временная сложность - алгоритм
Cтраница 1
Временная сложность алгоритма отражает требующиеся для его работы затраты времени. Эта функция, которая каждой входной длине ставит в соответствие максимальное ( по всем индивидуальным задачам длины п) время, затрачиваемое алгоритмом на решение индивидуальных задач этой длины. [1]
Временная сложность алгоритма - это функция от длины записи набора входных данных задачи, определяемая по аналогии с временной сложностью машины Тьюринга. Отличия заключаются в следующем. Вместо шага работы машины должна фигурировать элементарная операция. Под заключительным состоянием алгоритма следует понимать ситуацию, в которой получен ответ да, если речь идет о задаче распознавания, либо выбран элемент х е X, доставляющий экстремум целевому функционалу, если рассматривается экстремальная задача. [2]
Временная сложность алгоритмов 2.1 и 2.2 зависит от структуры данных, используемой для представления графов, и от механизма расстановки меток и построения списочного расписания. Матричное представление содержит 0 ( п) элементов, следовательно, требуется 0 ( п2) времени, чтобы выяснить, какие элементы матрицы являются ненулевыми. Поэтому представление леса в виде матрицы нецелесообразно, так как он содержит 0 ( п) ребер. [3]
 |
Эскиз канала с разведенными цепями ( второе альтернативное решение. [4] |
Теоретическая временная сложность алгоритма составляет NG ( NpP ( OK) 2) P ( OM) x xO ( N2), где NG - число поколений, Np - размер популяции, Р ( ОК) - вероятность крос-синговера, Р ( ОМ) - вероятность мутации, O ( N2) - временная сложность декодирования хромосомы, N - число цепей. [5]
Временную сложность алгоритмов ПАСС определим как функцию от числа шагов разметки уровней. Для разметки сети при втором проходе - это та же величина, поскольку для разметки 1-го уровня достаточно I шагов. [6]
Определим временную сложность алгоритма MINEQ. Предположим, что в Q имеется k строк и п столбцов. Множество COMPV ( w) можно найти за О ( kzri) шагов ( см. упр. Каждый из циклов for повторяется не более k раз, так что тело цикла while занимает не более О ( k n) времени. [7]
Определим временную сложность алгоритма MINEQ. Предположим, что в Q имеется k строк и п столбцов. Множество COMPV ( w) можно найти за О ( № п) шагов ( см. упр. Каждый из циклов for повторяется не более k раз, так что тело цикла while занимает не более О ( k n) времени. [8]
Оценим емкостную и временную сложность алгоритма Ланцоша, полагая что над полем GF ( p) решается система вида ( 24) с матрицей вида А MTD2M, где М - разреженная матрица, имеющая 6 ненулевых элементов. [9]
Лемма 5.2. Временная сложность алгоритма REDUCE составляет О ( л2), где п - длина входа. [10]
Лемма 5.2. Временная сложность алгоритма REDUCE составляет О ( п), где п - длина входа. [11]
Можно показать, что логарифмическая временная сложность алгоритма и временная сложность машины Тьюринга, реализующей этот алгоритм, полиномиально связаны. [12]
В обоих примерах в качестве временной сложности алгоритма поиска имеет смысл брать суммарное время ожидания очередного элемента ответа пользователем справочной системы в первом случае и периферийной ЭВМ - во втором. В идеальном случае, когда время обработки каждого элемента ответа пользователем или периферийной машиной больше времени поиска следующего элемента ответа основной машиной, эта временная сложность равна времени ожидания первого элемента ответа. [13]
Для экспоненциальных алгоритмов ( NP) временная сложность алгоритма составляет О ( пп), О ( п2п), 0 ( п3п), - Класс NP-полньтх задач включает такие задачи, для которых не найдены полиномиальные алгоритмы, однако и не доказано, что их не существует. [14]
Критерием эффективности в теории сложности служит временная сложность алгоритма как функция входной длины задачи. [15]
Страницы: 1 2 3