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

Question

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

Answer 1

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

Тогда есть практическая эффективность . Алгоритм O (N ² ) может быть намного быстрее, чем алгоритм O (N) на практике. Проводите реальные тесты и не слишком полагайтесь на теоретические результаты.

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

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

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

Если можете, используйте существующие библиотеки. Не катите свою собственную библиотеку мультиточности, если вы можете использовать GMP, например. Для C ++ такие вещи, как boost и даже контейнеры и алгоритмы STL, работали в течение многих лет целой армией людей и, скорее всего, лучше, чем вы можете сделать в одиночку.

Answer 2

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

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

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

Answer 8

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

Answer 9

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

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

Answer 10

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

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