T (n) преобразование в O (n)

Question

Я немного запутался в разнице между T(N) и O(N), когда речь идет о сложности времени. У меня есть три алгоритма с их соответствующими уравнениями T(N), и я должен найти худшую временную сложность O(N), и я не уверен, как это отличается от T(N).

Примером может быть:

T(n) = 150⋅N² + 3⋅N + 11⋅log₂(N) 

Будет ли O() быть просто O(N²)

Кроме того, следует алгоритм с более низкого порядка сложности всегда можно использовать? У меня есть ощущение, что ответ - нет, но я не слишком уверен в том, почему.

Answer 1

T (n) - это функция, представляющая время, затраченное на вход размера n. Обозначение Big-oh - это классификация этого. Как вы сказали в своем примере, большой-ой из этого примера будет n^2.

Что касается вашего второго вопроса, то обозначение big-oh указывает на алгоритм, который вы должны использовать, поскольку размер ввода приближается к бесконечности. Практически говоря, бывают случаи, когда вы никогда не получите вход, достаточно большой для компенсации. Например, если T1 (n) = 999999999999 * N и T2 (n) = 2 * N^2, в конечном итоге n достаточно велико, чтобы T2 был больше, чем T1. Однако для меньших размеров n T1 больше. Вы можете графически отображать функции или даже решать систему уравнений, чтобы выяснить, какой размер n будет иметь значение.

Примечание: Также имейте в виду, что big-oh является связанным по сложности, что означает, что вы можете иметь свободную границу, которая по-прежнему правильная.

Answer 2

T (n) - это просто функция. O или большой oh - уровень сложности.

T (n) может быть f (n) или g (n) в этом отношении.

Я надеюсь, что это ясно.

Big Oh - мера сложности времени или пространства алгоритма.

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

Answer 3

Будет ли O() быть только O (N²)

Да.

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

Например, для N = 10 в вашем примере 150⋅N² уже составляет 15000, тогда как 3⋅N = 30 и 11⋅log₂ (N) = 36,5, поэтому члены, не относящиеся к N², составляют только 0,44% общее количество шагов.

Для N = 100, 150⋅N² = 1500000, 3⋅N = 300, 11⋅log₂ (N) = 73,1, поэтому члены, не относящиеся к N², составляют всего 0,025% от общего количества шагов.

Таким образом, для более высоких N значение младших членов уменьшается.

Также следует использовать алгоритм с более низким порядком сложности?

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

В вашем примере, если у меня есть альтернативный алгоритм для проблемы, которую вы пытаетесь решить, которая имеет время выполнения T '(N) = 10⋅N³, то для N = 10 это займет всего 10000 шагов, в то время как ваш пример потребуется 150067 шагов. В основном, for any N ≤ 15, алгоритм T '(N) будет быстрее, и для любого N> 15 ваш алгоритм T (N) будет быстрее. Поэтому, если вы заранее знаете, что не увидите N> 15, вам будет лучше, выбирая теоретически менее эффективный алгоритм T '(N).

Конечно, на практике существует много других соображений, а, например, как:

• Наличие алгоритмов, которые можно повторно использовать в библиотеках, в Интернете и т.д.
• Если вы реализовать его самостоятельно : простота реализации
• Будь или не алгоритм масштабируется для нескольких ядер или нескольких машин легко