#algorithm #analysis
#алгоритм #анализ
Вопрос:
Мне нужна помощь в этом вопросе. Я действительно не понимаю, как это сделать.
Покажите математически или на примере, что если f (n) равно O(g(n)), то a * f (n) равно O (g(n)) для любой константы a > 0.
Комментарии:
1. Что у вас есть на данный момент?
2. Домашнее задание? Если это так, соответствующий тег отсутствует
3. Вы должны добавить домашнее задание к своим тегам.
4. это домашнее задание? Если да, пожалуйста, отметьте это как таковое. Кроме того, в чем ваша проблема? Вы понимаете, что означает O (…)? Вы смотрели на ее формальное определение ?
Ответ №1:
Я дам вам это. Это должно помочь вам смотреть в правильном направлении:
определение O (n):
функция f(n), которая удовлетворяет f(n) <= C * n для произвольного постоянного числа C и для каждого n выше произвольного постоянного числа N, будет отмечена f(n) = O(n).
Это формальное определение для нотации big-o, должно быть просто взять это и превратить в решение.
Комментарии:
1. Да, это домашнее задание, мне жаль, что я впервые использую stackoverflow.com и я не знал, что это означает под тегами
2. Мы едва знакомимся с нотацией big O и асимптотическим анализом. Я получил этот вопрос в своей домашней работе, и в нем не объяснялось, что речь идет об O (n), поэтому я в замешательстве. Я действительно не знаю, каким должен быть мой ответ.
3. Я не думаю, что здесь будет дано правильное решение. Самостоятельная разработка домашней работы очень поможет вам в долгосрочной перспективе. Тем не менее, помощь всегда доступна, просто задайте конкретный вопрос. Для начала, посмотрите, как вы можете взять свою функцию f (n) и посмотреть, что f (n) = O (g (n)) говорит об этом (в соответствии с приведенным выше определением big-o)
4. В этом проблема, я не понимаю, что означает f (n) или g (n). Функция чего? Обычная функция в математике? что означает O в этой задаче (например: O(g (n)))?
5. Я дал вам определение / значение O (он же нотация big-o), а что касается g (n) и f (n), то они являются общими математическими функциями. Все, что вам нужно знать о них, это то, что они представляют собой выражение, составленное из констант (чисел) и имен параметров «n» в сочетании с математическими операторами ( , -, log, power и т.д.). Не важно, что это за выражение, поэтому просто думайте об этом так, как вам нравится это называть (выражение, функция, черный ящик или как угодно). Это простой по сложности вопрос, поэтому не позволяйте ему сбивать вас с толку, просто попробуйте, что сможете.