Теория времени сложности

Question

Если f (n) - O (g (n)), а f (n) - O (h (n)), то какова связь между f (n), g (n) и h (n)?

Я видел этот вопрос во многих местах и ​​никогда не мог понять разницу. Для меня это выглядело как g (n) и h (n) как одно и то же, тогда как это не так.

Я даю из возможных вариантов, которые могли бы быть возможно, пожалуйста, скажите, какое условие выполняется:

А. п (п) + г (п) O (ч (п))

Б. г (п) + л (п) = О (е (п))

С. F (п) О (г (п) + л (п))

Answer 1

Вернитесь к определению нотации «Big-Oh». Здесь F (п) = О (ч (п)), который означает, что существует такое целое число п _ч и вещественные постоянные с _{ч, 1} и с _{ч, 2} такое, что для любого п> п _ч,

с _{ч, 1}. h (n) ≤ f (n) ≤ c _{h, 2}. ч (п) (1)

Аналогично, так как F также О (г (п)), существует также п _г и вещественные постоянные с _{г, 1} и с _{г, 2} такие что для любого п> п _г

гр _{г, 1}. g (n) ≤ f (n) ≤ c _{g, 2}. г (п) (2)

Оттуда, если взять п> тах (п _ч, п _г), оба неравенства, но они не приносят вам никакого знания об отношениях между h и g.

EDIT:

Поскольку вы не можете ничего между ч и г сказать, что вы не можете доказать предположения А и В без дополнительных знаний. С другой стороны, для любого n> max (n _h, n _g) у вас есть [1/2. (1) + 1/2.(2)]:

1/2. c _{g, 1}. g (n) + 1/2 c _{h, 1}. h (n) ≤ f (n) ≤ 1/2. c _{g, 2}. g (n) + 1/2. c _{h, 2}. ч (п)

И тогда

1/2. мин (с _{г, 1}, с _{ч, 1}). (г (п) + Н (п)) ≤ F (N) ≤ 1/2.max (с _{г, 1}, с _{ч , 1}). (г (п) + л (п))
Следовательно, ф (п) = О (г (п) + л (п))

Answer 2

Мы имеем:

• f (n) - O (g (n)) (При условии)
• F (п) = О (ч (п)) (с учетом)

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