Prove max(O(f(n)), O(g(n)))=O(max(f(n), g(n))
Это имеет смысл, но до сих пор я «т есть какие-либо идеи, как на самом деле это доказать.Докажите max (O (f (n)), O (g (n))) = O (max (f (n), g (n))
Любой вклад будет оценен.
f(n) <= max(f(n), g(n))
g(n) <= max(f(n), g(n))
max(O(f(n)), O(g(n))) <= O(max(f(n), g(n)), max(f(n), g(n))) = O(max(f(n), g(n)))
Обратите внимание, что в-равенствах используются не строгие.
Как можете ли вы принять полиномиальное время, не теряя общности? –
@ Ryan: Полученный пункт –
Thank. Просто заметим, что последнее выражение должно быть max (O (f (n)), O (g (n))) = O (max (f (n), g (n)) – EatEmAll
что запятые означает в O (f (n), g (n))? Я знаю только O (f (n)). –
Это была моя ошибка. Она должна была быть max (O (f (n), O (g (n))). – EatEmAll