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

Стабильность - некоторые алгоритмы могут "взорваться" при определенных условиях тестирования, например, потребовать неумеренно много времени для выполнения, или использовать неумеренно большой объем памяти, или, возможно, даже не завершиться.

Для алгоритмов, выполняющих операции с плавающей запятой, накопление ошибки округления часто является проблемой.

Энергопотребление для встроенных алгоритмов (например, смарт-карт).

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

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

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

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

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

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

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

Если мы говорим об алгоритмах в целом, то (в реальном мире) вам, возможно, придется подумать об использовании процессора/файловой системы (операции чтения/записи)/пропускной способности.

Правда, они находятся далеко внизу в списке вещей, о которых нужно беспокоиться в наши дни, но при достаточно большом объеме данных и достаточно дешевой инфраструктуре вам, возможно, придется подправить свой код, чтобы облегчить то или другое.

Стабильность (сортировка) - Поддерживает ли алгоритм относительный порядок равных элементов ?

Числовая стабильность - подвержен ли алгоритм ошибкам при использовании очень больших или малых действительных чисел?

Правильность - Всегда ли алгоритм дает правильный ответ? Если нет, то какова погрешность?

Общность - Работает ли алгоритм во многих ситуациях (например, с множеством разных типов данных)?

Компактность - Краткая ли программа для алгоритма?

Возможность распараллеливания - Насколько хорошо масштабируется производительность при увеличении количества параллельных потоков выполнения?

Осведомленность о кэше - Разработан ли алгоритм для максимального использования кэша компьютера?

Забвение кэша - Настроен ли алгоритм для определенных размеров кэша / размеров строк кэша или он хорошо работает независимо от параметров кеша?

Сложность. 2 одинаковы во всех других отношениях, гораздо более простой будет гораздо лучшим кандидатом для будущей настройки и использования.

Простота распараллеливания. В зависимости от вашего варианта использования это может не иметь никакого значения или, с другой стороны, сделать алгоритм бесполезным, поскольку он не может использовать 10000 ядер.

Вас интересуют не параметры, а внутренние свойства алгоритма.

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

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

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

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

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

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

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

Время и пространство - большие, и они кажутся настолько простыми и окончательными, что часто должны быть квалифицированы (1). Тот факт, что OP использует слово « параметр », а не говорит « критерии » или « свойства », отчасти свидетельствует об этом (как если бы большой O значение по времени и по пространству было достаточно, чтобы сформировать базовый алгоритм).
К другим критериям относятся:

• область применимости
• сложность
• математическая управляемость
• определенность результата
• легкость настройки (может быть привязана к «сложности» и «тактильности» «вышеупомянутое)
• возможность запуска алгоритма в параллельном режиме

(1)« квалифицировано »: как указано в других ответах, -технически- O (n ^ 2) алгоритм может оказывается быстрее, чем, скажем, алгоритм O (n), в 90% случаев (что, кстати, может оказаться 100% практических случаев)