2.4. Exemplo: Detecção de Anagramas¶

2.4.1. Solução 1: Marcação¶

Nossa primeira solução para o problema dos anagramas verificará se cada caractere na primeira string realmente ocorre na segunda. Se for possível “marcar” cada caractere, então as duas strings são anagramas. A marcação de um caractere será realizada substituindo-o pelo valor especial em Python None. Entretanto, como strings em Python são imutáveis, o primeiro passo do processo será converter a segunda string em uma lista. Cada caractere da primeira string será buscado entre os caracteres da segunda lista e, caso encontrado, será marcado por substituição. ActiveCode 1 mostra essa função.

Para analisar este algoritmo, devemos notar que cada um dos n caracteres em s1 causará uma iteração por até n caracteres na lista de s2. Cada uma das n posições na lista será visitada uma vez para marcar um caractere de s1. O número de visitas então é dado pela soma dos inteiros entre 1 e n. Vimos anteriormente que isso pode ser escrito como

Conforme \(n\) aumenta, o termo \(n^{2}\) dominará sobre o termo \(n\) e o \(\frac {1}{2}\) pode ser ignorado. Assim, a solução é \(O(n^{2})\).

2.4.2. Solução 2: Ordenar e Comparar¶

Outra solução para o problema do anagrama utilizará o fato de que mesmo que s1 e s2 sejam diferentes, eles são anagramas somente se consistem exatamente dos mesmos caracteres. Então, se começarmos ordenando cada string alfabeticamente, de a a z, concluiremos com a mesma string se as duas strings originais forem anagramas. ActiveCode 2 mostra essa solução. Novamente, em Python podemos utilizar o método sort em listas simplesmente convertendo cada string em uma lista no início.

À primeira vista você pode se sentir tentado a pensar que este algoritmo é \(O(n)\), já que há somente uma simples iteração para comparar os n caracteres depois do processo de ordenação. Entretanto, as duas chamadas ao método sort do Python também têm seus custos. Como veremos no último capítulo, ordenações são tipicamente \(O(n^{2})\) ou \(O(n\log n)\), então as operações de ordenação dominam sobre a iteração. No fim, este algoritmo terá a mesma ordem de magnitude do processo de ordenação.

2.4.3. Solução 3: Força Bruta¶

Uma técnica de força bruta para resolver um problema tipicamente tenta todas as possibilidades à exaustão. Para o problema de detecção de anagramas, podemos simplesmente gerar uma lista com todas as strings possíveis usando os caracteres de s1 e verificar se s2 ocorre. Entretanto, há uma dificuldade com esta abordagem. Ao gerar todas as strings possíveis a partir de s1, há n possíveis primeiros caracteres, \(n-1\) possíveis caracteres para a segunda posição, \(n-2\) para a terceira e assim por diante. O número total de strings candidatas é \(n*(n-1)*(n-2)*...*3*2*1\), ou seja, \(n!\). Embora algumas das strings sejam duplicadas, o programa não pode saber disso de antemão e então ele ainda gerará \(n!\) strings diferentes.

Acontece que \(n!\) cresce mais rápido ainda do que \(2^{n}\) conforme n cresce. De fato, se s1 contivesse 20 caracteres, haveria \(20!=2.432.902.008.176.640.000\) possíveis strings candidatas. Se processássemos uma possibilidade a cada segundo, ainda seriam necessários 77.146.816.596 anos para percorrer toda a lista. Esta provavelmente não será uma boa solução.

2.4.4. Solução 4: Contar e Comparar¶

Nossa solução final para o problema do anagrama se aproveita do fato de que quaisquer dois anagramas terão o mesmo número de a’s, o mesmo número de b’s, o mesmo número de c’s e assim por diante. Para decidir se duas strings são anagramas, vamos inicialmente contar o número de vezes que cada caractere ocorre. Como há 26 possibilidades de caracteres, podemos utilizar uma lista de 26 contadores, um para cada caractere possível. Cada vez que encontramos um caractere em particular, incrementamos o seu contador naquela posição. Ao final, se as duas listas de contadores são idênticas, as strings são anagramas. ActiveCode 3 mostra esta solução.

Novamente, a solução tem algumas iterações. Entretanto, diferentemente da primeira solução, nenhuma delas é aninhada. As duas primeiras iterações utilizadas para contar os caracteres são ambas baseadas em n. A terceira iteração, comparando as duas listas de contadores, sempre demoram 26 passos, já que há somente 26 possíveis caracteres nas strings. Adicionando tudo temos \(T(n)=2n+26\) passos. Ou seja, \(O(n)\). Encontramos um algoritmo com ordem de magnitude linear para resolver este problema.

Antes de deixarmos este exemplo, devemos dizer algo sobre requisitos de espaço. Embora a última solução tenha sido capaz de ser executada em tempo linear, ela só pôde fazer isso utilizando memória adicional para armazenar as duas listas de contadores de caracteres. Em outras palavra, este algoritmo sacrificou espaço para ganhar tempo.

Isso é bastante comum. Em diversas ocasiões você deverá tomar decisões entre tempo e espaço. Neste caso, a quantidade de espaço adicional não é significativa. Entretanto, se o alfabeto utilizado tivesse milhões de caracteres, seria uma preocupação maior. Como um cientista da computação, quando dada a escolha de algoritmos, caberá a você determinar o melhor uso dos recursos computacionais dado um problema em particular.