Если у меня есть алгоритм, который состоит из (скажем) три суб-алгоритмов, все с разными O() характеристики, например:Как добавить/объединить несколько больших выходов в один
Как теоретически оценить O() для всего алгоритма ? То есть не синхронизируя его или не выполняя никаких других практических измерений.
Есть ли известная формула или процедура?
Есть хорошо известная формула или процедура?
Поскольку это базовая математика, да. Но в вашем случае это еще проще: поскольку все они дают верхнюю границу , вы можете просто взять максимум всех границ, чтобы получить общую верхнюю границу.
- При условии, что все эти алгоритмы равны прикованным (а не вложенным). Если алгоритмы вложены, вам необходимо умножить их верхние границы (в простейшем случае).
Для иллюстрации предположим, что у вас есть структура данных контейнера, которая имеет стоимость O (log n) для поиска одного элемента. У вас также есть алгоритм, который нуждается в таком поиске, но имеет время работы O (n), при условии, что постоянные затраты на поиск и использование одного цикла над входом с постоянным количеством поисковых запросов для каждого цикла.
Теперь, если вы хотите использовать ранее упомянутую структуру данных контейнера с этим алгоритмом, его время выполнения поиска, очевидно, заменяет (предполагаемый) поиск по постоянному времени. Таким образом, у нас есть один и тот же цикл, но каждая из его итераций теперь принимает O (log n) вместо постоянного времени O (1), поэтому общее время работы становится O (n log n).
Как можно умножить, например, O (n) на O (n log (n))? – sharkin
@ R.A.: путем умножения функций, определяющих границы, т. е. результат будет O (n^2 log n). –
«Общая» сложность является наихудшим случаем всех под-алгоритмов. В вашем примере: O(n*log(n))
Definition of O(f(n)) является то, что, начиная с некоторого номера (некоторого n0), существует постоянная, «Const», где общее число действий по вводу размера п меньше Const*f(n).
Поэтому, если у вас есть группа под-алгоритмов, сложность всегда будет меньше, чем сигма всех констант (Const1 + Const2 + ...), умноженная на худшую функцию сложности (например, от «n», «n * logn "и" n^2 "это будет n^2). По определению сложности это наихудшая сложность в группе.
Пример:
(n*logn)(logn)Пусть const1 в этом роде 5 (то есть мы можем отсортировать список из n элементов менее чем за 5 * n * logn-действий), а Const2 - 3 (это означает, что мы можем найти элемент менее чем за 3 * logn-действия).
В этом случае, очевидно, что общее число действия обоих алгоритмов меньше (5+3)*n*logn действия, и поэтому O(n*logn)
Это будет зависеть от того, будут ли алгоритмы выполняться одинаковое количество раз относительно друг друга или если есть мультипликативный эффект, и в этом случае вам нужно их умножить. – Joe
@Joe, вы правы, этот анализ имеет отношение к последовательному запуску, а не к вложенным прогонам, я надеюсь, что это вопрос :) Результат остается тем же, если некоторые из алгоритмов работают более одного раза, сколько раз постоянна и не зависит от п. – Elisha
Одним из предположений с оценкой эффективности алгоритма O (n) является то, что наше фактическое время работы приближается к теоретическому значению. Таким образом, мы не должны слишком обернуться вокруг оси, пытаясь определить небольшие отклонения. Алгоритм O (n) может завершиться в O (n/2) раз, если мы делаем простой итеративный поиск через несортированный набор данных (в среднем, мы найдем значение на половину точки), например, но он по-прежнему алгоритм O (n).
Если у вас есть функция, которая должна завершить три подпроцесса в наборе данных, прежде чем она сможет выйти, то самое медленное время работы подпроцесса в этом наборе данных будет самым длинным полюсом в палатке, если можно так выразиться. В приведенном конкретном примере функция («алгоритм») работает в O (n) времени, и мы не волнуемся, если это O (n + n * log (n) + log (n)); разница между этой суммой и O (n) не более чем в два раза. Мы заботимся о относительной величине, т. Е. Является ли время работы log (n) или (n) или (n^2) или (n^3) до бесконечности. Мы заботимся о коэффициенте 10 или 100 или 1000.
Сложность проблемы определяется с условием «n», стремящимся к бесконечности. Эта ссылка в корне объясняет, почему все O (n) числа меньшей сложности отбрасываются; даже формат O (n) отбрасывает другие полиномиальные термины, которые будут меняться на разных аппаратных средствах. Разумно, вы можете добавить различные общие времена, если у вас есть время для функций. Это могут быть значимые данные в зависящей от времени среде, например обработке больших наборов данных, где вызываемые функции вызываются более одного раза. Это также может обеспечить масштабируемость решения и пик производительности обновления, скажем, сервера. Это будет одно машинное решение, и коэффициенты также не будут отброшены.
Все машины будут иметь различные коэффициенты работы при выполнении любой функции, основанной на архитектуре, и как компилятор генерирует двоичный код. Это означает, что если вы разрабатываете программы для нескольких пользователей, и они находятся на разных компьютерах, то конкретные вычисления являются не только посторонними, но и неточными.
В том случае, когда расчеты не являются чужеродными или неточными:
Трюк с отдельными структурами является функцией времени одного не функция времени всех остальных.
O(n) = x + y + z,
x(n) = (t1) * (n^2)
y(n) = (t2) * (log n)
z(n) = (t3) * (n log n)
...
времени (t1), (t2) и (t3) приведены в качестве времени функции на конкретной машине.
Просто предупреждение, чтобы «n» ссылалось на одно и то же в каждом алгоритме, или вы собираетесь отклеиваться. – Tim
Будет ли иметь смысл заняться наихудшим сектором в целом? –