Nano Hash - криптовалюты, майнинг, программирование

Большой вопрос — алгоритмический анализ

Я готовлюсь к экзамену, и я нашел эту проблему в Интернете, и мне было интересно, как я буду ее решать.

(с основанием 2 logs)
Докажите, что log(2n) является элементом O(log n).

Я попробовал, но не уверен, что я прав, так как ответа не было. Не могли бы вы помочь?

Вот моя попытка:

log 2n - c log n 0
log 2 + log n - c< /i> log n 0
1 + (1-c) log n 0
(затем я разделил на log н.)

Пример: n = 8 и c = 10 оцениваются как меньше нуля. Следовательно, это правда.

Мои вопросы:

  1. Я делаю это правильно?

  2. Можно ли еще упростить мой ответ?

algorithm big-o complexity-theory
08.04.2011

  • -1, не надо оскорблять других людей; Кроме того, ответ Ларсманса максимально краток и верен. 08.04.2011
  • Вы хотите доказать, что log(2n) равен O(log(n)). Поскольку log(2n) = log(2) + log(n) и члены более низкого порядка (log(2) в данном случае) можно игнорировать в асимптотическом анализе, результат следует. 08.04.2011

Ответы:


1

Длинный ответ заключается в том, что

                log(2n)       log(2) + log(n)       log(2)
lim n->infinity ------- = lim --------------- = lim ------ + 1 = 0 + 1 = 1
                log(n)        log(n)                log(n)

Поскольку отношение двух функций в пределе существует (т. е. ограничено), они имеют одинаковую асимптотическую сложность.

Точно так же, чтобы доказать, что O(n2) не равно O(n), вы должны сделать

lim n->infinity (n^2 / n) = lim n    which tends to infinity

Выполнение этого для O (n) по сравнению с O (log n) требует больше работы, потому что

lim n->infinity (n / log n)

нужно как-то обрабатывать. Хитрость заключается в том, что вместо этого вы можете использовать производные, поскольку производные в пределе также должны быть асимптотически связаны (иначе их интегралы не являются исходными функциями). Вы берете производную от n, которая равна 1, и от log n, которая равна n-1, после чего

lim n->infinity (1 / (1 / n)) = lim n    which tends to infinity
08.04.2011

2

lg(2n) = lg(2) + lg(n).

lg(2) — константа. См. Википедию, логарифмические тождества.

08.04.2011
  • Хм - я не уверен, откуда вы взяли lg (2) в конце. lg(2n) = lg(2)+lg(n) конечно.... 08.04.2011
  • Это новая фраза. Это не часть предыдущего уравнения :) 08.04.2011
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..
    © 2024 nano-hash.ru, Nano Hash - криптовалюты, майнинг, программирование