Para começar, a abordagem O(N2) precisa apenas de uma pequena alteração para contar os pares:
1 2 3 4 5 6 7 8 | long long ContaPares(int* valores, int N, int S) { long long resultado = 0; for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] <= S) resultado++; return resultado; } |
Note-se que se o array tiver uma dimensão considerável, e.g. ~100 000, o resultado pode exceder facilmente os 32 bits dos ints. Por outro lado, um programa com complexidade 1000002 é lento. Só esta função demoraria cerca de 15 segundos no meu computador.
Ordenação ajuda?
Como queremos os pares menores ou iguais a S, ordenar volta a parecer fazer sentido. Voltando ao exemplo dado no último post, o array ordenado fica -3, -2, 1, 5, 6, 7, 10 e S = 12.
Para o número -3, precisamos de saber quantos números existem menores ou iguais a S - (-3), ou seja, 15.
Para -2, seria quantos <= 14,
Para 1, quantos <= 11,
etc.
Se viram os links dados no último post, isto pode ser feito de forma eficiente com pesquisa binária. Assim, basta procurar qual é o índice do primeiro número do array ordenado maior do que S - número_actual e contar quantos números existem entre o número actual e esse índice.
No caso do C++, basta usar a função upper_bound().
1 2 3 4 5 6 7 8 9 10 11 | long long ContaParesNlogN(int* v, int N, int S) { sort(v, v+N); long long resultado = 0; for (int i = 0; i < N; i++) { // v+i+1 porque procuramos a partir da posição i+1 // caso não exista nenhum número > S-v[i], pos = N int pos = upper_bound(v+i+1, v+N, S-v[i]) - v; resultado += pos - (i + 1); } return resultado; } |
Temos a ordenação e é feita uma pesquisa binária para cada um dos N números. Assim, o tempo de execução é O(N log N).
De modo análogo ao problema anterior, podemos voltar a eliminar a pesquisa binária. Se -3 + 10 for maior do que S, então o 10 não vai formar um par válido com nenhum outro número e pode ser descartado.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | long long ContaParesNlogNv2(int* v, int N, int S) { sort(v, v+N); long long resultado = 0; int a = 0, b = N-1; while (a < b) { // descarta números que formam pares inválidos. while ((b > a) && (v[a] + v[b] > S)) b--; // conta os pares (a,a+1), (a,a+2), ... (a,b) = b - a pares resultado += b - a; a++; } return resultado; } |
O ciclo while exterior tem, no máximo, N-1 iterações. Cada iteração do ciclo while interior descarta um número do fim do array e retira uma iteração ao ciclo exterior porque decrementa b. Assim, o tempo de execução é O(N). Contudo, o tempo total continua dominado pelo O(N log N) da ordenação.
E hashing?
Como vimos no post anterior, as hash tables são muito úteis. No entanto, não podem ser usadas em todas as situações. Para contar o número de pares de forma eficiente, precisamos de usar a ordem dos números. As hash tables são excelentes para inserir, eliminar ou pesquisar elementos, mas não nos dizem nada sobre a ordem dos números e são inúteis para este problema.
O(N) é possível?
No caso de arrays já ordenados, sim. Basta usar o método referido acima.
Para arrays não ordenados, estamos limitados pela ordenação. No caso de termos números inteiros, temos:
- Counting Sort: pode ser utilizado quando sabemos que os números estão contidos num intervalo pequeno (e.g. entre 0 e 1000, -100 e 100 ou 1000 e 9999).
- Radix Sort: depende do número de bits K necessário para representar todos os números e é bastante útil em algumas situações. O tempo de execução é O(K * N) e é considerado linear se K for considerado uma constante (K é independente do valor N).
Sem comentários:
Enviar um comentário