Как доказать большие-o отношения

Эй, заголовок, вероятно, немного выключен, поэтому исправьте его, если Вы знаете, как поместить его лучше.

Как присвоение домашней работы мне дали несколько присвоений вдоль следующего:

Позвольте 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 неравенства в сингл (в) уравнении и опроверг бы его. Я являюсь самым уверенным, что это - что-то довольно легкое, которое я просто пропустил и что я довольно глуп в данный момент - но любые указатели / конкретные примеры того, как сделать это, были бы яркими, так, чтобы я смог работать остальная часть этих вопросов самостоятельно.

5
задан Bill the Lizard 16 December 2012 в 15:55
поделиться

2 ответа

Почему вы хотите опровергнуть его, не используя контрпример? Это самый прямой способ опровергнуть заявление.

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

В этом случае вы начинаете с того, что f (n) <= c1 * g (n) истинно, поскольку это то, что подразумевается под f (n) = O (g ( n)) . Теперь вы хотите предположить, что g (n) <= c2 * f (n) верно для всех f и g (эта последняя часть очень важна , потому что вы, конечно, можете выбрать f и g так, чтобы это было верно), и показать, почему это не может работать. Мой вам совет: выберите f и g , чтобы он не работал, и покажите, что он не может работать, выбрав c1 и c2 .

4
ответ дан 14 December 2019 в 08:49
поделиться

Несколько советов:
Не забывайте, что 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)

3
ответ дан 14 December 2019 в 08:49
поделиться
Другие вопросы по тегам:

Похожие вопросы: