Память - еще один фактор, который следует учитывать, например, Mergesort, как правило, работает с одинаковой временной сложностью (хотя и с более низким постоянным коэффициентом), но в два раза больше пространства, чем Heapsort (я говорю «обычно», потому что на месте Mergesort обычно O (N^2)). Базовый алгоритм вычисления простых чисел до N требует, чтобы вы сохранили все простые числа до N, тогда как Sieve of Eratosthenes более эффективны с точки зрения времени, но требуют, чтобы вы сохранили все числа (не все простые числа) до N Radix Sort работает в O (n) (в отличие от Heapsort/Mergesort/Quicksort, которые работают в O (n * log (n))), но вряд ли кто-либо использует Radix Sort, потому что он требует гораздо больше памяти и имеет низкую производительность кеша. Также обратите внимание, что для рекурсивного алгоритма обычно требуется больше пространства (в виде стека), чем эквивалентный итеративный алгоритм.
Средняя временная сложность - еще один фактор - Bubblesort и Quicksort работают в такой же наихудшей временной сложности (O (n^2)), но средняя временная сложность Bubblesort равна n^2, в то время как средняя временная сложность Quicksort - n * log (п). Вставка и поиск в сбалансированном двоичном дереве имеет наихудшее и среднее время n * log (n), тогда как вставка и поиск в хэш-таблице обычно имеют наихудшее время O (n) и постоянное среднее время.
Иногда алгоритмы будут иметь одинаковую сложность по времени, но можно использовать менее дорогостоящие операции. Например, стандартным алгоритмом умножения матрицы является O (n^3); альтернативный алгоритм (чье имя я забыл) работает с той же сложностью во времени, но у пользователей меньше умножений и больше дополнений (дополнения дешевле, чем умножения). (В этом случае влияют постоянные факторы, поэтому сравнение яблок и яблок по-прежнему остается яблочным, но избегайте сравнения алгоритмов, которые являются яблоками для апельсинов.)
Еще одно соображение - распараллеливание. Алгоритм базового матричного умножения работает с той же сложностью по времени, что и block matrix multiplication algorith, но последний намного эффективнее первого при параллельном запуске. Подмножество параллельных алгоритмов также обладает тем свойством, что они «блокируются», что означает, что они обеспечивают синхронизацию без использования семафоров или мониторов или других блокирующих структур; подмножество алгоритмов без блокировки «без ожидания», что означает, что все потоки гарантируют прогресс.
производительности кэша является еще одним фактором - основные и блок-матричные алгоритмы умножения используют примерно такой же объем памяти, но алгоритм блок имеет лучшее поведение кэша (меньше кэш-промахов)
стабильность является фактором во многих численных алгоритмов , При решении обыкновенных дифференциальных уравнений метод Рунге-Кутты четвертого порядка сходится гораздо быстрее, чем неявный метод Эйлера, но неявный метод Эйлера всегда будет сходиться к решению, тогда как метод Рунге-Кутты может проявлять нестабильность (например, сходятся к бесконечности или NAN) ,
Многие алгоритмы требуют, чтобы все данные находились в основной памяти; напротив, внешний алгоритм требует только того, чтобы часть данных находилась в основной памяти в любой момент времени.Например, классический алгоритм Mergesort требует, чтобы все отсортированные элементы находились в памяти, в то время как Polyphase Mergesort требует только, чтобы подмножество элементов находилось в памяти, а остальные - на жестком диске или по сети.