Упростить сложность n многоходовой k

11

У меня есть рекурсивный алгоритм с временной сложностью, эквивалентной выбору k элементов из n с повторением, и мне было интересно, смогу ли я получить более упрощенное выражение big-O. В моем случае может быть больше и они растут независимо.kn

В частности, я бы ожидал некоторого явного экспоненциального выражения. Лучшее, что я смог найти, это приближение Стерлинга , так что я могу это использовать, но мне было интересно, смогу ли я получить что-нибудь приятнее.O(n!)O((n/2)n)

O((n+k1k))=O(?)

yoniLavi
источник
Это не совсем полезно, но очень интересно факторное приближение Рамануджана
Пратик Деогхар
Спасибо, n!π(ne)n8n3+4n2+n+1306 выглядит как крутое приближение, но на самом деле это не помогает упростить это.
yoniLavi

Ответы:

6

Изменить: этот ответ для k<n . Без ограничения k через n выражение не ограничено.

Если , то ваше выражение становится . Обратите внимание , что по формуле Стирлинга для любого где является двоичной энтропией. В частности . Поэтому мы имеем дляO ( ( 2 ( n - 1 )k=n10<α<1(мO((2(n1)n1))0<α<1 Н(д)=-длогд-(1-д)журнал(1-д)Н(1/2)=1к=п-1O( ( 2(п-1

(мαм)знак равноΘ(м-1/22ЧАС(α)м),
ЧАС(Q)знак равно-QжурналQ-(1-Q)журнал(1-Q)ЧАС(1/2)знак равно1Кзнак равноN-1
О((2(N-1)N-1))знак равноΘ((2N-2)-1/222N-2)знак равноΘ(4NN),

Поскольку верхняя граница является наихудшим случаем (я оставляю это как упражнение, чтобы показать это), ваше выражение будет .O ( 4 nКзнак равноN-1О(4NN)

A.Schulz
источник
Спасибо, именно то, что я искал! и это еще одна вещь, побуждающая меня изучать теорию информации.
yoniLavi
@ Falcor84: у меня была небольшая опечатка в последнем переходе. Квадратная часть корня должна идти к знаменателю. Следовательно, оценка немного лучше, чем та, которую представил Пареш. (На самом деле, граница асимптотически жесткая.)
A.Schulz
Я тоже должен был заметить этот маленький знак минус, еще раз спасибо.
yoniLavi
Ваше утверждение «оставлено как упражнение», что - наихудший случай, неверно. Если , выражение равно . Это не всегда меньше, чем . п = 3 ( K + 2k=n1n=3(k+2k)=(k+22)=(k+1)(k+2)2(42)знак равно6
Питер Шор
1
Так как , проблема симметрична по и (которая может расти без отношения в моем случае ). Поэтому, я полагаю, более точным ответом было бы заменить n в заключительной части ответа на(N+К-1К)знак равно(N+К-1N-1)NКИксзнак равномaИкс(N,К)
yoniLavi
2

Вольфрам говорит, что Сондоу (2005) [1] и Сондоу и Зудилин (2006) [2] отметили неравенство: для положительное целое число и действительное число.

14рм[(р+1)р+1рр]м<((р+1)мм)<[(р+1)р+1рр]м
мр1

Затем мы можем использовать с и ,

(N+К-1К)<(N+КК)знак равно((р+1)мм)
рзнак равноNКмзнак равноК

Тогда у нас есть

(N+К-1К)<[(р+1)р+1рр]мзнак равно(N+КК)N+К

Теперь биномиальное выражение имеет наибольшее значение в середине треугольника Паскаля. Итак, в нашем случае или при .k = nN+Кзнак равно2ККзнак равноN

Подставляя это в вышеупомянутое неравенство, мы получаем: .

(N+К-1К)<22Nзнак равно4N

Следовательно, более узкий предел равен .

(N+К-1К)знак равноО(4N)

Вы также можете видеть, что нижняя граница для максимального значения равна

(N+К-1К)знак равноΩ(4NN)

Ссылки:
[1] Sondow, J. "Задача 11132". Amer. Математика Ежемесячно 112, 180, 2005.
[2] Сондоу Дж., Зудилин В. Константа Эйлера, q-логарифмы и формулы Рамануджана и Госпера. Рамануджан Дж. 12, 225-244, 2006.

Paresh
источник