Какими могут быть параметры, кроме времени и пространства, при анализе определенных алгоритмов?

Question

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

Answer 1

Для числовых алгоритмов есть также свойство непрерывность : то есть, если вы слегка измените входные данные, выходные данные также изменятся лишь незначительно. См. Также Анализ непрерывности программ на Lambda The Ultimate для обсуждения и ссылки на научную статью.

Для ленивых языков есть также строгость : f называется строгим, если f _|_ = _|_ (где _|_ обозначает низ (в смысл теории предметной области), вычисление, которое не может дать результат из-за отсутствия завершения, ошибок и т. д.), в противном случае оно не является строгим. Например, функция \x -> 5 не является строгой, поскольку (\x -> 5) _|_ = 5, тогда как \x -> x + 1 является строгой.

Другим свойством является определенность : зависит ли результат алгоритма (или других его свойств, таких как время работы или потребление пространства), от его входных данных.

Answer 2

То, что вас интересует, это не параметры , скорее они являются внутренними свойствами алгоритма.

Во всяком случае, другое свойство, которое вас может заинтересовать и анализировать алгоритм, касается эвристики (точнее, алгоритмов аппроксимации ), то есть алгоритмов, которые не находят точных решение, а то, которое (надеюсь) достаточно хорошо.

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

Другая метрика касается рандомизированных алгоритмов , где рандомизация используется для предотвращения нежелательного поведения в худшем случае. Одним из примеров является рандомизированная быстрая сортировка; quicksort имеет наихудшее время выполнения O ( n ² ), которого мы хотим избежать. Предварительно перемешивая массив, мы можем избежать наихудшего случая (то есть уже отсортированного массива) с очень высокой вероятностью. Просто насколько высока эта вероятность, может быть важно знать; это еще одно внутреннее свойство алгоритма, которое можно проанализировать с помощью стохастика.

Answer 3

Все эти вещи в других ответах о качестве различных алгоритмов важны и должны учитываться.

Но время и пространство - это две вещи, которые изменяются с некоторой скоростью по сравнению с размером ввода (n). Так что еще может варьироваться в зависимости от п?

Есть несколько, которые связаны с вводом / выводом. Например, количество записей на диск является важным, которое может не отображаться напрямую только с помощью оценок пространства и времени. Это становится особенно важным для флэш-памяти, где число записей в одну и ту же ячейку памяти является существенным показателем в некоторых алгоритмах.

Другой метрикой ввода / вывода будет "болтливость". Сетевой протокол может отправлять более короткие сообщения, чаще добавляя к тому же пространству и времени, что и другой сетевой протокол, но некоторые аспекты системы (возможно, выставление счетов?) Могут привести к минимизации желаемого размера или количества сообщений.

И это подводит нас к стоимости, которая иногда является очень важным алгоритмическим соображением. На стоимость алгоритма могут влиять как пространство, так и время в разных количествах (рассмотрим отдельную стоимость дискового пространства сервера и гигабиты передачи данных), но стоимость - это то, что вы хотите минимизировать в целом, поэтому он может иметь свои собственные оценки Big-O.