Эй, заголовок, вероятно, немного выключен, поэтому исправьте его, если Вы знаете, как поместить его лучше.
Как присвоение домашней работы мне дали несколько присвоений вдоль следующего:
Позвольте f (n) и g (n) быть асимптотически положительными функциями. Докажите или опровергните каждую из следующих догадок.
a. f(n) = O(g(n)) implies g(n) = O(f(n))
Теперь, мой реальный вопрос - как Вы пошли бы о доказательстве этого формальным способом? Я знаю, что вышеупомянутое было бы легко, поскольку я мог легко обеспечить встречный пример для опровержения его, но ради аргумента скажем, что мы хотим сделать это без встречных примеров с курса, который это продолжает с некоторыми другими примерами, где это не будет работать.
Я немного застреваю, у меня есть следующие описанные неравенства (с <= быть меньше чем или равным)
f(n) <= c1 * g(n)
g(n) <= c2 * f(n)
Но я не уверен в том, как я объединил бы эти 2 неравенства в сингл (в) уравнении и опроверг бы его. Я являюсь самым уверенным, что это - что-то довольно легкое, которое я просто пропустил и что я довольно глуп в данный момент - но любые указатели / конкретные примеры того, как сделать это, были бы яркими, так, чтобы я смог работать остальная часть этих вопросов самостоятельно.
Почему вы хотите опровергнуть его, не используя контрпример? Это самый прямой способ опровергнуть заявление.
Если бы вам пришлось вместо этого доказывать это, вы, конечно, не смогли бы использовать контрпример. В этом случае контрапозитив может работать очень хорошо - предположите, что утверждение ложное, а затем покажите, как это ведет к логической несогласованности.
В этом случае вы начинаете с того, что f (n) <= c1 * g (n)
истинно, поскольку это то, что подразумевается под f (n) = O (g ( n))
. Теперь вы хотите предположить, что g (n) <= c2 * f (n)
верно для всех f
и g
(эта последняя часть очень важна , потому что вы, конечно, можете выбрать f
и g
так, чтобы это было верно), и показать, почему это не может работать. Мой вам совет: выберите f
и g
, чтобы он не работал, и покажите, что он не может работать, выбрав c1
и c2
.
Несколько советов:
Не забывайте, что f (n) = O (g (n))
- это обозначение набора , а вы может преобразовать его в математическую форму неравенств.
Простые операции, которые можно выполнять с помощью O -нотации:
f (n) = O (f (n))
c * O (f (n)) = O ( f (n))
, если c постоянна O (f (n)) + O (f (n)) = O (f (n))
O (O (f (n) )) = O (f (n))
O (f (n)) * O (g (n)) = O (f (n) g (n))
O (f (n) g (n)) = f (n) * O (g (n))
(Искусство программирования, том 1 - O -Notation)