, если f (n) = n-100 и g (n) = n-200 равно f, равному большому o из g или омега g или тета g

-3

Привет, ребята, которые сами изучают алгоритмы, используя книгу г-на Дасгуптаса. Кажется, я не нашел руководство по решению, поэтому подумал о том, чтобы разместить здесь свои вопросы. любые способы, проблема заключается в качестве названия состояний, если, если f (n) = n-100 и g (n) = n-200 равно f, равному большому o из g или омега g или тета g

, если F (п) = п-100 и г (п) = п-200 является е равно большое О от г или омега г или тета д я думаю, что его тета g, но не уверен

источник

2015-02-03 user119020

просто используйте определения O, Omega и Theta –

IMO, f (n) не является чем-то большим. Это самая вводящая в заблуждение, непоследовательная и бессмысленная нотация, которую вы можете использовать. Как функция может быть равна классу функций? Также есть много ресурсов, как получить эти обозначения и как их использовать. Покажите немного усилий. – luk32

Хорошо, насколько я понимаю, для O должна быть константа c, что f (n) cg (n), таким образом, для omega c может быть одно (если n положительно) , что im не уверен, существует ли константа c, где f (n) user119020

Ни то, ни другое - O (g) - это набор функций, и функция не может быть равна множеству fucntions справа?

О (г) - функции, которые растут на НАИБОЛЕЕ так же быстро, как функция g
Ω (г) - функции, которые растут, по крайней мере так же быстро, как функция g
Θ (г) - функции, которые растут на ТОЧНО так же быстро, как функция g

Вы должны использовать вместо термина belongs или is member of в случае множества ассоциаций.

Наиболее правильная вещь состоит в том, что f является членом Θ (g), обозначенным f ∈ Θ (g). F действительно растет точно так же быстро, как g.

источник

2015-02-03 11:36:25

согласно книге, которую он скажет, чтобы сказать f ∈ Θ (g), необходимо доказать f ∈ O (g), а также f ∈ Ω (g). Определение говорит, что для f ∈ O (g) должна существовать константа c> 0 такая, что f <= cg (n). Мне не удалось найти эту константу – user119020

@ user119020 Я не знаю, о какой именно книге вы говорите, но определение, которое вы цитируете, не на 100% точнее. Обычно это определяется с помощью limeses для n, приближающегося к бесконечности. С вашим определением было бы достаточно константы, превышающей единицу, с достаточно большими значениями n. –

, если f (n) = n-100 и g (n) = n-200 равно f, равному большому o из g или омега g или тета g

ответ

Смежные вопросы