Simplifique a complexidade de n tomadas múltiplas k

11

Eu tenho um algoritmo recursivo com complexidade de tempo equivalente a escolher elementos k de n com repetição, e estava pensando se poderia obter uma expressão big-O mais simplificada. No meu caso, k pode ser maior que n e eles crescem independentemente.

Especificamente, eu esperaria alguma expressão exponencial explícita. O melhor que pude encontrar até agora é o baseado na aproximação de Stirling O(n!)O((n/2)n) , para que eu possa usá-lo, mas me perguntei se conseguiria algo melhor.

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

yoniLavi
fonte
Este não é exatamente muito útil mas muito interessante aproximação factorial de Ramanujan
Pratik Deoghare
Obrigado parece como uma aproximação legal, mas de fato não parece ajudar a simplificar isso. n!π(ne)n8n3+4n2+n+1306
precisa saber é o seguinte

Respostas:

6

Editar: Esta resposta é para . Sem delimitar k em termos de n, a expressão é ilimitada.k<nkn

Se , sua expressão se torna O ( ( 2 ( n - 1 )k=n1. Observe que pela fórmula de Stirling para qualquer0<α<1(mO((2(n1)n1))0<α<1 ondeH(q)=-qlogq-(1-q)log(1-q)é o binário de entropia. Em particular,H(1/2)=1. Portanto, temos parak=n-1

(mαm)=Θ(m1/22H(α)m),
H(q)=qlogq(1q)log(1q)H(1/2)=1k=n1
O((2(n1)n1))=Θ((2n2)1/222n2)=Θ(4nn).

Como o limite superior é o pior caso (deixo como exercício para mostrar isso), sua expressão é O ( 4 nk=n1.O(4nn)

A.Schulz
fonte
Obrigado, exatamente o que eu estava procurando! e é outra coisa que me motiva a estudar teoria da informação.
precisa saber é o seguinte
@ Falcor84: Eu tive um erro de digitação menor na última transição. A parte da raiz quadrada deve ir para o denominador. Portanto, o limite é um pouco melhor do que o apresentado por Paresh. (Na verdade, o limite é assintoticamente restrito.)
A.Schulz
Eu também deveria ter notado aquele pequeno sinal de menos, obrigado novamente.
precisa saber é o seguinte
Sua afirmação "deixado como exercício" de que é o pior caso está errada. Se n = 3 , a expressão é ( k + 2k=n1n=3 . Isso nem sempre é menor que ( 4(k+2k)=(k+22)=(k+1)(k+2)2. (42)=6
quer
1
Desde , o problema é simétrico nonek(que pode crescer sem relação no meu caso). Portanto, creio eu, a resposta mais preciso seria a de substituir n na parte final da resposta comx:=mumx(n,k)(n+k1k)=(n+k1n1)nkx:=max(n,k)
yoniLavi
2

Wolfram diz que Sondow (2005) [1] e Sondow e Zudilin (2006) [2] observaram a desigualdade:

14rm[(r+1)r+1rr]m<((r+1)mm)<[(r+1)r+1rr]m
mr1

(n+k1k)<(n+kk)=((r+1)mm)
r=nkm=k

(n+k1k)<[(r+1)r+1rr]m=(n+kk)n+k

n+k=2kk=n

(n+k1k)<22n=4n

(n+k1k)=O(4n)

(n+k1k)=Ω(4nn)

Referências:
[1] Sondow, J. "Problema 11132". Amer. Matemática. Mensal 112, 180, 2005.
[2] Sondow, J. e Zudilin, W. "Constante de Euler, q-logaritmos e fórmulas de Ramanujan e Gosper" Ramanujan J. 12, 225-244, 2006.

Paresh
fonte