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

Каково повторение, если базовый случай O (n)?

Мы должны создать алгоритм и найти и решить его повторение. Обнаружение повторения поставило меня в тупик ..

foo(A, C)
  if (C.Length = 0)
    Sum(A)
  else
    t = C.Pop()
    A.Push(t)
    foo(A,C)
    foo(A,C)

Изначально A пусто и C.Length = n. Я не могу дать реальный алгоритм, потому что это не разрешено.

Мой инструктор сказал мне, что я могу попробовать использовать 2 переменные. Вот что я придумал:

T(n, i) = { n                if i =  0
            2*T(n, i-1) + C  if i != 0

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

T(n) = { n0                  if n =  0
         2*T(n-1) + C        if n != 0

Где n0 — начальное значение n.

Как вы формируете повторение из алгоритма, где сложность базового случая составляет O (n)?

recursion recurrence algorithm complexity-theory
06.02.2011

Ответы:


1

Пусть f(n) будет сложностью, если C имеет размер n. Пусть N будет исходным размером C.

Тогда f(0) = N и f(n) = 2 * f(n - 1) + c.

Это имеет решение f (n) = N * 2 ^ n + (2 ^ n - 1) * c, и поэтому f (N) = O (N * 2 ^ N).

06.02.2011
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..