Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

Логарифмическое время
логарифмическое время, если T(n) = O (log n) ... Поскольку компьютеры используют двоичную систему, основание логарифма равно 2 (т.е. log 2). н). Однако изменение основания с логарифмами log an и log bn отличаются только постоянным коэффициентом, который компенсируется в O-большой нотации. Таким образом, O(log n) является стандартной записью для алгоритмов логарифмического времени, независимо от основания логарифма.
Алгоритмы логарифмического времени обычно используются в операциях с бинарными деревьями или при использовании бинарного поиска.
Алгоритмы O(log n) очень эффективны, поскольку время выполнения каждого элемента уменьшается по мере увеличения количества элементов.
Очень простой пример такого алгоритма — деление строки пополам, деление второй половины еще раз пополам и так далее. Это занимает O(log n) времени (где n — длина строки, мы предполагаем, что console.log и str.substring здесь занимают постоянное время). Это означает, что для увеличения количества отпечатков длину строки необходимо удвоить.
// Функция для рекурсивного вывода правой половины строки var right = function (str) (var length = street length; // вспомогательная функция var help = function (index) ( // Рекурсия: печатать правую половину do if (index < length ) { // Печатаем символы от индекса до конца строки console.log(str.substring(index, length));// рекурсивный вызов: вызываем вспомогательную функцию с правой стороны help(Math.ceil(( длина + индекс) / 2)); )) помощь (0); )
Полилогарифмическое время
Говорят, что алгоритм запускается за полилогарифмическое время, если T(n) = O ((log n) k) для некоторого k... Например, задача о порядке умножения матриц может быть решена за полилогарифмическое время. параллельная машина PAM.
Сублинейное время
Говорят, что алгоритм работает за сублинейное время, если T(n) = o ( n ). В частности, сюда входят алгоритмы временной сложности, перечисленные выше, а также другие, такие как поиск Гровера со сложностью O (n ½).
Хотя это и правда, типичные алгоритмы, которые все еще работают за сублинейное время, полагаются на распараллеливание процессов (например, в алгоритме NC 1 для вычисления определителя матрицы), неклассические вычисления (как в поиске Гровера) или имеют гарантированную аппроксимацию , использует алгоритмы. структура входных данных (выполнение в логарифмическом времени, алгоритмы бинарного поиска и многие алгоритмы обработки дерева). Однако формальные конструкции, такие как набор всех строк, имеющих 1 бит в состоянии, определяемом первыми log(n) битами строки, могут зависеть от каждого бита входных данных, но по-прежнему оставаться сублинейными во времени.
Термин сублинейный алгоритм времени выполнения обычно используется для алгоритмов, которые, в отличие от приведенных выше примеров, работают на традиционных моделях последовательных машин и не требуют априорного знания входной структуры. Однако для них допускается использовать вероятностные методы, и тем более алгоритмы должны быть вероятностными для самых тривиальных задач.
Поскольку такой алгоритм должен отвечать без чтения всех входных данных, он сильно зависит от методов доступа, разрешенных во входном потоке. Обычно предполагается, что для потока битовых строк b 1 ,...,bk алгоритм может запросить значение bi для каждого i.
Алгоритмы сублинейного времени обычно являются вероятностными и дают только приближенное решение. Сублинейные алгоритмы времени выполнения естественным образом возникают при изучении тестирования свойств.