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

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?$\log_2(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.$n$$\log_2(n)$$\frac {n} {log_2(n)}$$log_2(\frac {n} {log_2(n)})$$\frac {\frac {n} {log_2(n)}} {log_2(\frac {n} {log_2(n)})}$

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 para$f(n) = n/\log n$$g(n)$$f$$n$$f^{(t)}(n) \geq n/\log^t n$

$$g(n) \geq \log_{\log n} n = \frac{\log n}{\log \log n}.$$ $f^{(t)}(n) \geq \sqrt{n}$$\log f^{(t)}(n) \geq (\log n)/2$$\log_{(\log n)/2} n = O(\log n/\log\log n)$$n$$\sqrt{n}$$\sqrt{n}$$\sqrt[4]{n}$e 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) \ll \frac{\log n}{\log\log n} + \frac{\log \sqrt{n}}{\log\log \sqrt{n}} + \frac{\log \sqrt[4]{n}}{\log\log \sqrt[4]{n}} + \cdots.$$ $\cdot \ll \cdot$$\cdot = O(\cdot)$$\log \sqrt{n} = \frac{1}{2} \log n$$n$$\log\log \sqrt{n} \geq \frac{2}{3} \log \log n$ $$\frac{\log \sqrt{n}}{\log\log \sqrt{n}} \leq \frac{2}{3} \frac{\log n}{\log\log n}.$$ $$g(n) = O\left(\frac{\log n}{\log\log n}\right).$$ $$g(n) = \Theta\left(\frac{\log n}{\log \log n}\right).$$ Com mais trabalho, provavelmente podemos provar uma estimativa mais refinada, como $$g(n) \sim \frac{\log n}{\log \log n}.$$

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 .

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 a$n^{1/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.)

Todo logaritmo abaixo significa logaritmo com base 2, $\log_2(\cdot)$.

---

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

• caso base, $\operatorname{slog}(1)=0$ e $\operatorname{slog}(2)=1.$
• a relação de recorrência, $\operatorname{slog}(n)=1+ \text{slog}\left(\left\lceil\dfrac{n}{ \lceil\log n\rceil}\right\rceil\right)$ para $n\gt2.$

Podemos provar a seguinte proposição sobre o comportamento assintótico de$\operatorname{slog}(n)$.

$$\lim_{n\to\infty}\dfrac{\quad\text{ slog}(n)\quad}{\dfrac{\log n}{\log\log n}}=1.$$

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

$$\begin{align} \lim_{n\to\infty}\frac{\log n}{\log\log n}-\frac{\log \frac n{\log n}}{\log\log \frac n{\log n}} &=\lim_{m\to\infty}\frac{m}{\log m}-\frac{m-\log m}{\log(m-\log m)}\\ &=\lim_{m\to\infty}\frac{m}{\log m}-\frac{m-\log m}{\log m + \log(1- \frac{\log m}m)}\\ &=\lim_{m\to\infty}\frac{(\log m)^2+ m\log(1- \frac{\log m}m)}{(\log m)(\log m+ \log(1- \frac{\log m}m))}\\ &=\lim_{m\to\infty}\frac{(\log m)^2+ m(-\frac{\log m}m)}{(\log m)(\log m)}\\ &=1 \end{align}$$

Corolário. $\text{slog}(n)=\Theta\left(\dfrac{\log n}{\log\log n}\right)$.

---

A mesma conclusão vale se definirmos $\text{slog}(x)$ para $x>1$ com $\text{slog}(x)=1$ para $1\lt x\le 2$ e $\operatorname{slog}(n)=1+ \text{slog}\left(\dfrac{n}{ \log n}\right)$.

---

Exercício. Escreva a prova completa de$\text{slog}(n)\sim \dfrac{\log n}{\log\log n}$.