Как добавить / объединить несколько больших О в один

Question

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

• алгоритм A: O (n)
• алгоритм B: O (log (n))
• алгоритм C: O (n log (n))

Как теоретически оценить O () для всего алгоритма? То есть не синхронизировать его или выполнять другие практические измерения.

Есть ли хорошо известная формула или процедура?

Answer 1

Есть ли хорошо известная формула или процедура?

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

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

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

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

Answer 2

«Общая» сложность - наихудший случай из всех подалгоритмов. В вашем примере: O(n*log(n))

Определение O(f(n)) состоит в том, что, начиная с некоторого числа (некоторого n0), существует константа 'Const', где общее количество действий на входе размера n меньше Const*f(n).

Следовательно, если у вас есть группа подалгоритмов, сложность всегда будет меньше, чем сигма всех констант (Const1 + Const2 + ...), умноженная на наихудшую функцию сложности (например, из "n", "n * logn "и" n ^ 2 "это будет n ^ 2). По определению сложности это худшая сложность в группе.

Пример:

1. Давайте предположим, что мы сортируем массив (n*logn)
2. Поиск предмета с ключом выше x (logn)

Предположим, что Const1 сорта равен 5 (это означает, что мы можем отсортировать список из n элементов менее чем за 5 * n * logn действий), а Const2 равно 3 (что означает, что мы можем найти элемент менее чем за 3 * действий logn).

В этом случае ясно, что общее количество действий обоих алгоритмов меньше, чем (5+3)*n*logn действий, и, следовательно, оно O(n*logn)

Answer 3

Сложность задачи определяется условиями стремления «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) задаются как время функции на конкретной машине.

Answer 4

Одно из предположений с оценками эффективности алгоритма 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.