Qual é a profundidade da recursão se dividirmos uma matriz em a cada chamada recursiva?

7

Temos uma função que recebe uma matriz como entrada. Ele divide uma matriz em partes com tamanhos iguais, onde é o tamanho da sub- matriz . Ele continua quebrando cada um dos sub-arranjos até restarem apenas dois elementos nele. Qual é a profundidade dessa recursão?log2(n)n

Exemplo do processo:

Primeiro, temos elementos e os em partes com tamanhos iguais. Cada uma dessas partes possui elementos . No próximo nível de recursão, dividiremos cada um dos sub- em partes novamente com tamanhos iguais. Agora eles terão em cada um deles. E continuamos quebrando a matriz dessa maneira até chegarmos a um sub-arranjo com apenas dois elementos.nlog2(n)nlog2(n)log2(nlog2(n))nlog2(n)log2(nlog2(n))

Hinko Pih Pih
fonte
É facilmente calculado, não é? Tente n = 1.000.000, por exemplo. Faça isso manualmente, então deve ser óbvio.
precisa saber é o seguinte
11
@ gnasher729 ainda não está claro para mim ...
Hinko Pih Pih
O que é log_2 (1.000.000)? Então, se você dividir 1.000.000 itens em muitas sub-matrizes de tamanho igual, qual o tamanho de cada uma? E se você fizer de novo?
precisa saber é o seguinte
Não dividirei a matriz em partes toda vez. Na primeira etapa, sim, mas depois eu a dividirei em e assim por diante. log2(1,000,000)log2(1,000,000log2(1,000,000))
Hinko Pih Pih
Você se dizer "onde n é o tamanho da matriz", não "onde n é o tamanho da subarray". Faz pouca diferença na prática.
precisa saber é o seguinte

Respostas:

5

Seja e denote por o número de aplicações de necessárias para obter abaixo de alguma constante arbitrária. Por um lado, e, portanto, Para obter um limite superior, observe que, contanto que , tenhamos e, portanto, são necessárias no máximo iterações para reduzir para . O mesmo argumento se aplica à redução de paraf(n)=n/logng(n)fnf(t)(n)n/logtn

g(n)loglognn=lognloglogn.
f(t)(n)nlogf(t)(n)(logn)/2log(logn)/2n=O(logn/loglogn)nnnn4e assim por diante e, portanto, (Aqui é o mesmo que .) Observe que . Para grandes , teremos (digamos), e assim Portanto, a soma é aumentada por uma série geométrica convergente e concluímos que No total, entendemos isso
g(n)lognloglogn+lognloglogn+logn4loglogn4+.
=O()logn=12lognnloglogn23loglogn
lognloglogn23lognloglogn.
g(n)=O(lognloglogn).
g(n)=Θ(lognloglogn).
Com mais trabalho, provavelmente podemos provar uma estimativa mais refinada, como
g(n)lognloglogn.

Yuval Filmus
fonte
O que representa? t
Hinko Pih Pih
É o número de vezes que você aplicou . f
Yuval Filmus
Não consigo descobrir como você obteve da primeira desigualdade. g(n)loglognn
Hinko Pih Pih
Resolvendo a equação . Aqui é minha constante "arbitrária". n/logtn=11
Yuval Filmus
Agora eu não entendo como você conseguiu iterações de . Pode me explicar por favor? log(logn)/2nlogf(t)(n)(logn)/2
Hinko Pih Pih
2

Parece que você está se referindo ao logaritmo iterado, também conhecido como a função . É uma função que expressa quantas vezes você pode obter o logaritmo de um número até que ele produza um número menor ou igual a 1.log

A função cresce muito lentamente. É o inverso da tetração.log

Veja mais disso aqui .

Victor Stafusa
fonte
2
Não é o logaritmo iterado. Por exemplo: no primeiro passo terein elementos e separá-lo em log2(n)peças. Em cada parte tereinlog2(n). Isso significa que, no próximo nível, não aceitarei o logaritmo de um logaritmo. Vou separar o subarray emlog2(nlog2(n)) partes que é definitivamente muito mais do que log2(log2(n)). E esse padrão continua. Na verdade, eu escrevi o programa e a profundidade da recursão é sempre maior do quelog2(log2(n)) e sempre menor que log2(n).
Hinko Pih Pih
2

Seja n o tamanho da matriz. Seja k = log2 (n). Na primeira etapa, você divide por k. Desde que o tamanho da matriz seja superior an1/2, você divide por mais de k / 2. Eu diria que este é O (log n / log log n).

(Sempre dividir em k partes leva o log n / log k divide. Você solicitou o caso especial k = log n, portanto, log n / log log n. Depois, você precisa decidir se o encolhimento k faz a diferença ou não.)

gnasher729
fonte
Mas o tamanho do subarray será menor que n12em algum ponto. E mesmo que isso não fosse verdade, eu não entendo como você conseguiuO(log2(n)log2(log2(n))).
Hinko Pih Pih
Sua resposta editada fornece uma boa explicação para uma constante k mas aqui knão é constante, por isso ainda não é útil.
Hinko Pih Pih
1

Todo logaritmo abaixo significa logaritmo com base 2, log2().


Vamos nomear a função dada na pergunta slog. ( "trabalho árduo" vem do s plitting com log . Ele também pode implicar " s maller de log ".) Em termos precisos, slog em N é definido pelas seguintes condições.

  • caso base, slog(1)=0 e slog(2)=1.
  • a relação de recorrência, slog(n)=1+slog(nlogn) para n>2.

Podemos provar a seguinte proposição sobre o comportamento assintótico deslog(n).

limn slog(n)lognloglogn=1.

Aqui está a idéia básica da prova.

limnlognloglognlognlognloglognlogn=limmmlogmmlogmlog(mlogm)=limmmlogmmlogmlogm+log(1logmm)=limm(logm)2+mlog(1logmm)(logm)(logm+log(1logmm))=limm(logm)2+m(logmm)(logm)(logm)=1

Corolário. slog(n)=Θ(lognloglogn).


A mesma conclusão vale se definirmos slog(x) para x>1 com slog(x)=1 para 1<x2 e slog(n)=1+slog(nlogn).


Exercício. Escreva a prova completa deslog(n)lognloglogn.

John L.
fonte
O resultado assintótico aqui deve ser folclore ou conhecido. No entanto, ainda não encontrei nenhuma referência.
John L.