O (mn) и O (mnlgn)

Question

для вышеуказанных 2 больших О, что произойдет, если n >> m.Как меняется большой O?Становится ли это O (n) в первом случае.Если да, то почему?

Answer 1

Это зависит от того, что вы знаете о том, каким может быть максимальное значение m (в зависимости от n).

Если m и n являются независимыми переменными, O(mn) равно O(mn) и не может быть дополнительно упрощено. Если вы знаете, что m никогда не будет больше, чем n, но ничего больше, вы также можете написать его как O(n^2). Например, если вы знаете, что m никогда не будет больше log n (что удовлетворяло бы n >> m), O(mn) можно записать как O(n log n).

Answer 2

O (mnlgn) всегда будет больше, чем O (mn), независимо от относительных размеров m и n.Вы удалили бы термины или упростили бы их только в том случае, если один из терминов считается ограниченным или фиксированной константой.Согласно этим утверждениям, n и m являются независимыми измерениями, которые совместно ограничивают время выполнения алгоритма.Они оба продолжают иметь значение в нотации big-O, если только у одного из них нет конечной границы.Даже в этом случае может оказаться полезным оставить ограниченное измерение m при сравнении границ времени выполнения различных алгоритмов, которые могут различаться по своей сложности относительно m.

O (mnlgn) и O (mn)не будет сходиться, даже если n >> m.Они всегда будут разделены множителем m.Если m является переменным и неограниченным, то правила Big-O требуют, чтобы он оставался.

Answer 3

Когда n >> m O (mnlgn) будет больше, чем O (mn). Просто решите на примере, предположим, что n = 2 ^ x. Да, когда n >> m O (mn) сходится к O (n).