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

Question

Предположим, у меня есть следующее: T (n) = 5n ^ 2 + 2n Асимтотическая жесткая граница этого тета n ^ 2.Я хочу понять причину отбрасывания 5. Я понимаю, почему мы игнорируем члены более низкого порядка.

Answer 1

Обратитесь к определению big-O.

Проще говоря [*], давайте определим, что функция g есть O (f), если существуют такие константы C и M, что для n> M 0 <= g (n) <Cf (n). </p>

Наличие положительного постоянного множителя в f не влияет на это, просто выберите C соответственно. Ваш пример T - это O (n ^ 2), выбрав значение C больше 5, а значение M достаточно большое, чтобы значение +2n не имело значения. Например, для n> 2 это факт, что 5n ^ 2 + 2n <6n ^ 2 (потому что n ^ 2> 2n), поэтому при C = 6 и M = 2 мы видим, что T (n) есть O (n ^ 2).

Так что верно, что T (n) - это O (n ^ 2), а также верно, что это O (5n ^ 2) и O (5n ^ 2 + 2n). Наиболее интересным из этих фактов является то, что это O (n ^ 2), поскольку это простейшее выражение, а два других логически эквивалентны. Если мы хотим сравнить сложности различных функций, то мы хотим использовать простые выражения.

Для большой тэты просто обратите внимание, что мы можем сыграть ту же самую хитрость, когда f и g - наоборот. Отношение "g is Theta (f)" является отношением эквивалентности, так что мы будем выбирать в качестве репрезентативного члена класса эквивалентности T? Самый простой.

[*] Чтобы сделать вещи менее простыми, мы справляемся с отрицательными числами, используя limsup, а не простой предел. Мое определение выше на самом деле достаточно, но не обязательно.

Answer 2

большое обозначение O

эта ссылка объясняет ваш вопрос.

Answer 3

все возвращается к понятию «Орден Магнит».Учитывая что-то вроде

5n ^ 2 + 2n

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

5 * 50 ^ 2 + 2 * 50 -> 5 * 2500 + 2 * 50 -> 12 600

Как вы упомянули, 2* n незначительно по сравнению с n ^ 2.Эта же концепция применима и при просмотре константы ... вы можете подумать, что 2500 против 125 000 - большая разница;однако подумайте, если бы алгоритм был n ^ 3 ... вы сейчас смотрите на 12 600 против 625 100

Таким образом, коэффициент, который будет иметь наиболее существенное различие в стоимости алгоритма, равен просто n ^ 2.

Answer 4

Константа отбрасывается, потому что она не влияет на класс сложности, к которому принадлежит функция.

Если у вас есть две функции f (n) = c1 * n ^ 2 и g (n) = c2 * n^ 3, где c1 и c2 - константы, не имеет значения, насколько велика c1 и насколько мала c2, g (n) ВСЕГДА обгонит и перерастет f (n) при некотором значении n.