A princípio considerei aplicar o algoritmo de detecção de ciclos de Floyd, também conhecido como o algoritmo da "tartaruga e do coelho", mas o problema parece ser mais simples do que isso.
Características de complexidade logarítmicas geralmente envolvem uma comparação que vai diminuindo ao longo do tempo. Por exemplo, a busca binária, que vai dividindo o vetor sempre em dois.
O fato dela ser elevada ao quadrado também poderia estar associado a comparações entre os elementos do vetor, como ocorre com o algoritmo de ordenação bolha (bubble sort).
Considerando tudo isso, mais a definição do problema:
S[K] = S[K+P] para todo K, onde 0 ≤ K < Q − P
Pensei num algoritmo simples que funciona basicamente da seguinte forma:
- Calcula o maior período dividindo o tamanho da cadeia de bits por 2, fazendo
P = T / 2
, sendo T
o tamanho da cadeia de bits.
Calcula a quantidade de cadeias a comparar fazendo Q = LEN / P
, arredondando-se sempre para cima
Para cada K = 1..P
e J = 2..K
, compara cada elemento na posição K
com o correspondente na posição K * J + P
, somente quando K * J + P <= T
Se encontrar um elemento diferente
- Se
P > 1
, decrementa o período P
e retorna ao passo 2
novamente
- Senão, continua no passo
4
Se P <= 0
retorna -1
, senão, retorna P
Exemplo prático
Dado o número de exemplo 955
, cujo valor binário é 1110111011
, podemos calcular os valores inicias dos Passos 1 e 2 da seguinte forma:
T = 10
P = 10 / 2 = 5
Q = 10 / 5 = 2
Então a comparação no Passo 3 ocorre da seguinte forma:
K = 1
: 1 1 1 0 1 | 1 1 0 1 1 (iguais)
K = 2
: 1 1 1 0 1 | 1 1 0 1 1 (iguais)
K = 3
: 1 1 1 0 1 | 1 1 0 1 1 (diferentes)
Ao comparar o terceiro elemento de cada período, um elemento diferente foi encontrado. Então, atualizados as variáveis assim:
P = P - 1 = 4
Q = 10 / 3 = 4 (arredondando para cima)
E continuamos a comparação:
K = 1
: 1 1 1 0 | 1 1 1 0 | 1 1 (iguais)
K = 2
: 1 1 1 0 | 1 1 1 0 | 1 1 (igualis)
K = 3
: 1 1 1 0 | 1 1 1 0 | 1 1 (iguais)
K = 4
: 1 1 1 0 | 1 1 1 0 | 1 1 (iguals)
Como não há diferença, então retornamos o valor de P
, que é 4
.
Implementação em Java
public static int periodo( int n ) {
// validação inicial: precisa ser positivo e com pelo menos duas casas binárias
if( n < 2 ) return -1;
// inicialização de variáveis
String s = Integer.toBinaryString( n );
byte[ ] bytes = s.getBytes();
int t = bytes.length;
// período inicial
int p = t / 2;
// verifica se o período se repete pelo menos uma vez
boolean diferente;
do {
diferente = false;
int qp = t / p; // quantidade de períodos
if (t % p > 0) qp++; //somar 1 para comparar os caracteres de resto no final
// verifica se a repetição ocorre
for2: for( int k = 0 ; k < p ; k++ ) {
for (int j = 1; j < qp; j++) {
if( k + p * j < t && bytes[ k ] != bytes[ k + p * j ] ) {
diferente = true;
break for2;
}
}
}
//se não encontrou repetição, tenta um período menor
if( diferente ) {
p--;
}
} while( diferente && p > 0 );
return p <= 0 ? -1 : p;
}
Algumas Considerações
Não sou muito bom em julgar a complexidade de um algoritmo, mas acredito que no pior caso o algoritmo acima irá fazer N / 2
iterações e, em cada uma, ele faz iterações em períodos menores, o que leva a uma complexidade logarítmica temporal.
Quanto à complexidade especial (de memória), o algoritmo é O(1)
porque não acrescenta novas estruturas de dados além da original, embora a implementação seja O(N)
porque cria um vetor auxiliar do mesmo tamanho da cadeia de bits.
Algo que me deixa com uma pulga atrás da orelha é que o problema sugeriu uma complexidade especial também logarítmica, então talvez haja alguma estrutura de dados que possa otimizar a complexidade temporal da solução.
Uma solução que pensei com complexidade temporal logarítmica é dividir a cadeia de bits em várias Strings e então comparar para ver se elas possuem o mesmo conteúdo. Porém, suspeito que essa solução seria bem menos eficiente, já que executar vários substring
s me parece algo desnecessário, além do que a comparação de Strings também ocorreria caractere a caractere.
Outra ideia é recuperar o trecho binário de cada período e comparar o equivalente em seu formato numérico. Talvez ainda com operações binárias o algoritmo pudesse ser muito eficiente. Mas não analisei a complexidade da conversão de cada período do formato binário para o decimal.
Ainda outra ideia para otimizar isso ainda mais seria fazer toda essa comparação usando operadores binários para verificar a igualdade dos períodos, por exemplo, usando cadeias de bits assim: 1000010000
, 1000100010
, 1001001001
, 1010101010
. É uma ideia.
Enfim, não sei se a solução que propus atende ao requisito da pergunta, mas espero ter ajudado pelo menos com algumas ideias.
E, antes de concluir, só um alerta: cuidado com o desempenho da linguagem ao participar de um desafio online. Já resolvi alguns desses problemas usando Java e Python. Infelizmente, muitas vezes obtive um timeout mesmo com um bom algoritmo. Alguns sites adicionam multiplicadores de velocidade, por exemplo, Java 1,5
e Python 2,5
para tentar igualar a eficiência do algoritmo com linguagens mais velozes como C++. Porém, isso nem sempre é justo e basta olhar o ranking para ver quais linguagens estão sempre no topo.
Atualização
Baseado no gist do Anthony Accioly, fiz uma tentativa de otimizar ainda mais o código usando somente manipulação em bits. Segue o código:
public class BitPeriod5 {
public int solution(int n) {
// validação inicial: precisa ser positivo e com pelo menos duas casas binárias
if (n < 2) {
return -1;
}
// inicialização de variáveis
final int t = 32 - Integer.numberOfLeadingZeros(n);
// descarta bits não significantes
final int s = n >>> Integer.numberOfTrailingZeros(n);
// período inicial
int p = 1;
int maxp = t / 2;
int vp = 0;
// verifica se o período se repete pelo menos uma vez
boolean diferente;
do {
diferente = false;
int qp = t / p + 1;
if (t != p * qp) {
qp++; //somar 1 para comparar os caracteres de resto no final
}
vp = vp << 1 | 1;
int vi = n & vp;
for (int i = 1; i < qp; i++) {
if (((n >> (i*p)) & vp) != (vi & vp)) {
diferente = true;
}
}
//se não encontrou repetição, tenta um período menor
if (diferente) {
p++;
}
} while (diferente && p <= maxp);
return p > maxp ? -1 : p;
}
public static void main(String[] args) {
final BitPeriod5 bitPeriod = new BitPeriod5();
for (int i = 0; i < 100; i++) {
long nano = System.nanoTime();
for (int j = 0; j < 100000; j++) {
bitPeriod.solution(10);
bitPeriod.solution(187);
bitPeriod.solution(955);
bitPeriod.solution(1000000000);
bitPeriod.solution(0b10101000001010100000);
}
System.out.printf("%.2f\n", ((double) (System.nanoTime()) - nano) * 1e-6);
}
}
}
Entretanto, notei que essa solução acaba sendo mais lenta que a que a anterior, mesmo tendo um for
a menos.
Lição 1
Manipular bits é mais "caro" que acessar elementos do vetor e comparar o seu valor.
Também notei que retirando a operação de módulo, o desempenho do código melhora bastante.
Alterando o trecho:
if (t % qp > 0) ...
Por isso:
if (t != p * qp) ...
O ganho de desempenho foi na faixa dos 25%. É muito interessante ver como cada operação a mais afeta drasticamente o desempenho.
Lição 2
A operação de módulo da divisão é muito "cara" do ponto de vista de desempenho.
905 = 1110111011
. Mais tarde também esbarrei nos algoritmos de detecção de ciclos mas não consegui formular o problema exatamente conforme a proposta dos algoritmos.n
, o tamanho de sua cadeia de bits é [o teto de]log2(n)
. Ou seja, uma solução "quadrática em relação a Q" corresponde exatamente alog2(n)^2
...