Helpers - компьютеры, интернет, программирование

Создание рекурсивной формулы для фрагмента кода

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

Вот код:

    public static double power2(double base, int n) {
    switch (n) {
        case 1:
            return base;
        case 2:
            return base * base;
        default:
            if (n % 2 == 0) /* n is even */ {
                return power2(power2(base, n / 2), 2);
            } else /* n is odd */ {
                return power2(power2(base, n / 2), 2) * base;
            }
    }
}

У меня есть базовый случай, который, как я полагаю, равен 0, n=1; Однако при достижении T(n) я борюсь.

Оно должно быть похоже на T(n-1)+c, n>1.

Мне нужно выразить код рекурсивной формулой.

Может ли кто-нибудь ELI5 это для меня?

java recursion formula master-theorem
28.08.2015

  • Что ты хочешь делать? Узнайте, сколько раз можно разделить число на 2? 28.08.2015
  • Главная теорема? 28.08.2015
  • @ozgur Мне нужно выразить код с помощью рекурсивной формулы T (n). 28.08.2015
  • @Влад Да, верно. В моем учебнике это не упоминается. 28.08.2015

Ответы:


1

Я склонен сказать, что повторение

T(n) = T(n/2) + O(1)

Если вы перепишете общий случай как

double temp = power2(base, n/2); // T(n/2)
if (n%2 == 0) {
  return power2(temp, 2); // O(1) by looking at the base case
} else {
  return power2(temp, 2) * base; // O(1) by looking at the base case
}

что делает это

O(log(n))

Этот документ описывает конкретную проблему, которую вы ищете. в. Они, вероятно, делают свою работу лучше, чем я, я не смотрел основную теорему в течение длительного времени.

28.08.2015
  • Итак, если оговорено, что для выполнения умножения требуется c единиц времени, повторение будет 'T(n) = T(n/2) + c'? Будет ли умножение на основание в дополнительное время, когда число нечетное, составит 2c? Несмотря ни на что, спасибо за помощь! 28.08.2015
  • Ах, я пропустил эту часть. Я предполагаю, что в случае n-нечетного это будет 2c, одно c для базового случая n=2, а затем еще одно c для *base в конце. 28.08.2015
  • Верно. В этом есть смысл. Огромное спасибо. 28.08.2015
    • Новые материалы
    Интуитивное понимание тензоров в машинном обучении
    Тензор является важной концепцией во многих научных областях, таких как математика, физика, обработка сигналов и компьютерное зрение, и это лишь некоторые из них. В математике тензор — это..
    Использование машинного обучения для диагностики болезни Альцгеймера, часть 4
    Маркеры семантической согласованности для ранней диагностики болезни Альцгеймера (arXiv) Автор: Давиде Колла , Маттео Дельсанто , Марко Агосто , Бенедетто Витиелло , Даниэле Паоло Радичони..
    Почему объяснимость так важна прямо сейчас?
    По мере того, как системы искусственного интеллекта и инструменты на основе машинного обучения распространяются в нашей повседневной жизни, как практики, так и критики все чаще заявляют о..
    Анимированный математический анализ
    Использование Manim для создания математических анимированных визуализаций Визуализация данных помогает понять скрытые закономерности в данных, которые невозможно визуализировать..
    Создание простого слайдера изображений с помощью JavaScript
    Узнайте, как создать базовый слайдер изображений с помощью HTML, CSS и JavaScript. Введение В этом уроке мы создадим удобный слайдер изображений, используя JavaScript, HTML и CSS. Ползунок..
    Создание базы данных с помощью супергероя «Python»
    В этом посте мы узнаем, как создать «базу данных SQLite с помощью модуля python sqlite3, создав простую функцию входа и регистрации. Готовы ли вы к этому путешествию? Если да , давайте приступим..
    ИИ для чайников: руководство для начинающих по пониманию будущего технологий
    Вы чувствуете, что остались позади в мире ИИ? Не волнуйтесь, вы не одиноки! Со всей этой шумихой вокруг искусственного интеллекта может быть трудно понять, с чего начать. Но не позволяйте сленгу..