Алдера Алдера для n 1-битовых чисел

Question

Предположим, что добавление двух чисел с a и b битами может быть выполнено в O (max {a, b}). мы хотим добавить n номеров (n 1-битных чисел i.e добавить n 0 или 1). стоимость этого альтогона варьируется от перестановки ввода до другой перестановки. каков наилучший и наихудший вариант этого алгоритма?

Я столкнулся с этой проблемой как старая викторина на компьютерном курсе.

Мы имеем два решение:

1- лучшего случай и худший случай могут быть в O (N)

2- Лучшее в O (N) и Wost Дело в О (п) п Л.Г.

Любой может описать любые pesudocode или алгоритм для выше двух временного порядка?

Answer 1

Ответ 1- Лучший и худший случай - O (n). Лучший случай, когда все биты равны 0, требуется порядок n - 1 или просто положить O (n). Худший случай, когда все биты равны 1, фактический порядок представляет собой сумму n * (lg n - lg i)/2^(lg n - lg i) i от n до 0. Поскольку i стремится к 0, результат значение выражения будет небольшим, и поэтому его можно игнорировать. Таким образом, выражение имеет вид n/2 + n/4 * 2 + .... Снова линейный рост с n.
Дополнительная информация:
Лучший случай, когда все биты равны 0, добавление их никогда не приведет к отсутствию более 1 цифры. (т. е. всегда дает 0). поэтому порядок равен O (n)
В худшем случае, когда все биты равны 1, добавление первого 2 бит потребует O (1) Результат будет 10. Теперь добавление его другим битом потребует O (2) и таким образом порядок может увеличиться в случае наихудшего случая. Предположим, что мы разделили входной набор на 2 пары чисел и добавили их, в первой итерации все пары потребуют O (1) и приведут к 10. Существует n/2 пары, так что это O (n/2). На второй итерации мы разделим первый набор результатов итерации на 2 пары чисел и добавим их. (Обратите внимание, что теперь все nos равны 10). Таким образом, порядок будет n/4 * O (2). то есть O (n/2). Таким образом, это должно продолжаться до тех пор, пока результирующий набор не будет исчерпан. Но когда значение n очень велико, вклад от 3-итераций вперед можно игнорировать. Так что это просто O (n/2) + O (n/2), т.е. O (n)