Como os Algoritmos Funcionam
Chapter 8 Algorithm Analysis Techniques

Capítulo 8: Técnicas de Análise de Algoritmos

Nos capítulos anteriores, exploramos uma ampla gama de algoritmos e estruturas de dados fundamentais, abrangendo tópicos como ordenação, busca, grafos, strings e várias aplicações. Embora a implementação e o entendimento desses algoritmos sejam cruciais, é igualmente importante analisar suas características de desempenho para tomar decisões informadas ao selecionar algoritmos para problemas específicos. Neste capítulo, mergulhamos nas técnicas usadas para analisar e avaliar algoritmos, com foco em modelos matemáticos, estudos empíricos e visualização de algoritmos.

Modelos Matemáticos e Análise

A análise matemática é uma ferramenta poderosa para entender o comportamento e o desempenho de algoritmos. Desenvolvendo modelos matemáticos que capturam as características essenciais de um algoritmo, podemos raciocinar sobre sua eficiência e escalabilidade. Esses modelos nos permitem fazer previsões sobre o tempo de execução, o uso de memória e outras métricas de desempenho de um algoritmo, permitindo-nos comparar diferentes algoritmos e escolher o mais adequado para uma determinada tarefa.

Notação Big-O

Uma das notações mais amplamente utilizadas para descrever o desempenho de um algoritmo é a notação big-O. A notação big-O fornece um limite superior na taxa de crescimento de uma função, permitindo-nos caracterizar o pior caso do tempo de execução ou da complexidade de espaço de um algoritmo.

Na notação big-O, expressamos o desempenho de um algoritmo como uma função do tamanho da entrada, geralmente denotada como n. Por exemplo, considere a seguinte função simples que calcula a soma dos primeiros n inteiros positivos:

public static int sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

O tempo de execução dessa função cresce linearmente com o tamanho da entrada n. Podemos expressar isso usando a notação big-O como O(n), indicando que o tempo de execução é proporcional ao tamanho da entrada. Isso significa que, à medida que oAqui está a tradução em português do arquivo markdown, com os comentários traduzidos, mas o código não traduzido:

À medida que o tamanho da entrada aumenta, o tempo de execução do algoritmo aumenta no máximo linearmente.

A notação Big-O nos permite ignorar fatores constantes e termos de ordem inferior, focando no termo dominante que determina a taxa de crescimento da função. Por exemplo, considere a seguinte função:

public static int sumOfSquares(int n) {
    // Inicializa a soma como 0
    int sum = 0;
    // Itera de 1 até n
    for (int i = 1; i <= n; i++) {
        // Itera de 1 até i
        for (int j = 1; j <= i; j++) {
            // Adiciona j à soma
            sum += j;
        }
    }
    // Retorna a soma
    return sum;
}

O tempo de execução desta função é proporcional ao quadrado de N. Para ser preciso, o número de vezes que a instrução sum += j é executada é 1 + 2 + ... + N ~ N^2/2.

Em geral, podemos expressar o tempo de execução de um programa em termos do tamanho da entrada usando a notação Big-O. Isso nos permite suprimir os coeficientes líderes e os termos de ordem inferior, e nos concentrar na parte importante: a ordem de crescimento do tempo de execução.

Algoritmo Knuth-Morris-Pratt

O algoritmo Knuth-Morris-Pratt (KMP) é um algoritmo eficiente de pesquisa de substring que usa uma "função de falha" pré-computada para evitar comparações desnecessárias.

A função de falha nos diz o comprimento do maior prefixo próprio do padrão que também é um sufixo do substring do padrão que já combinamos. Isso nos permite "pular à frente" no texto quando encontramos uma incompatibilidade, em vez de retroceder.

Aqui está um exemplo do algoritmo KMP:

Texto:    "abacadabrabracabracadabrabrabracad"
Padrão: "abracadabra"
Saída:  [13]

O algoritmo KMP tem um tempo de execução de O(n + m), tornando-o muito mais eficiente do que a abordagem de força bruta para textos e padrões grandes.

Algoritmo Boyer-Moore

O algoritmo Boyer-Moore é outro algoritmo eficiente de pesquisa de substring que funciona pré-processando a string do padrão. Ao contrário do KMP, que inicia as comparações do início do padrão, o Boyer-Moore começa do final e trabalha para trás.

A ideia-chave por trás do Boyer-Moore é usar duas funções pré-computadas: o "bom sufixo"Aqui está a tradução em português do arquivo markdown:

Função Boyer-Moore e a função "caractere ruim". Essas funções nos permitem avançar no texto quando encontramos uma incompatibilidade, semelhante ao KMP.

Aqui está um exemplo do algoritmo de Boyer-Moore:

Texto:    "abacadabrabracabracadabrabrabracad"
Padrão: "abracadabra"
Saída:  [13]

O Boyer-Moore tem um tempo de execução no melhor caso de O(n/m) e um tempo de execução no pior caso de O(n * m), mas na prática, muitas vezes é o algoritmo de pesquisa de substring mais rápido para grandes alfabetos.

Expressões Regulares

Expressões regulares são uma ferramenta poderosa para descrever padrões em strings. Elas fornecem uma notação concisa e flexível para correspondência, pesquisa e manipulação de texto.

Uma expressão regular é uma sequência de caracteres que define um padrão de pesquisa. A forma mais simples de uma expressão regular é uma string literal, como "hello", que corresponde exatamente à string "hello". No entanto, as expressões regulares também incluem caracteres e construções especiais que permitem padrões mais complexos:

  • . (ponto) corresponde a qualquer caractere único.
  • * (asterisco) corresponde a zero ou mais ocorrências do caractere ou grupo anterior.
  • + (mais) corresponde a uma ou mais ocorrências do caractere ou grupo anterior.
  • ? (ponto de interrogação) corresponde a zero ou uma ocorrência do caractere ou grupo anterior.
  • ^ (circunflexo) corresponde ao início de uma linha.
  • $ (cifrão) corresponde ao final de uma linha.
  • [] (colchetes) definem uma classe de caracteres, correspondendo a qualquer caractere único dentro dos colchetes.

Aqui estão alguns exemplos de expressões regulares e os padrões que elas correspondem:

  • a.b corresponde a qualquer string de três caracteres que começa com "a" e termina com "b", como "acb", "a5b" ou "a b".
  • a*b corresponde a qualquer string que consiste em zero ou mais caracteres "a" seguidos por um único "b", como "b", "ab", "aab" ou "aaab".
  • a+b corresponde a qualquer string que consiste em um ou mais caracteres "a" seguidos por um único "b", como "ab", "aab" ou "aaab", mas não "b".
  • a?b corresponde a "ab" ou "b".
  • ^a corresponde a qualquer string que começa com "a".Aqui está a tradução em português deste arquivo markdown. Para o código, não traduzi o código, apenas os comentários.

ts com "a".

  • a$ corresponde a qualquer string que termine com "a".
  • [aeiou] corresponde a qualquer caractere vogal.

Expressões regulares são suportadas por muitas linguagens de programação e ferramentas, incluindo Java, Python e utilitários Unix como grep e sed. Elas são amplamente utilizadas para tarefas como validação de dados, processamento de texto e análise de logs.

Compressão de Dados

A compressão de dados é o processo de codificar informações usando menos bits do que a representação original. Isso é útil para reduzir os requisitos de armazenamento e os tempos de transmissão. Existem dois principais tipos de compressão: sem perdas e com perdas. A compressão sem perdas permite que os dados originais sejam perfeitamente reconstruídos a partir dos dados comprimidos, enquanto a compressão com perdas permite alguma perda de informações em troca de maiores taxas de compressão.

Codificação por Comprimento de Sequência

A codificação por comprimento de sequência (RLE) é uma técnica simples de compressão sem perdas que substitui sequências repetidas de símbolos idênticos (sequências) por uma única instância do símbolo e uma contagem do número de vezes que ele é repetido.

Aqui está um exemplo de RLE:

Entrada:  "AAAABBBCCCDDDEEE"
Saída: "4A3B3C3D3E"

A RLE é eficaz para dados com muitas sequências longas, como imagens gráficas simples. No entanto, ela pode realmente aumentar o tamanho dos dados se houver poucas ou nenhuma sequência.

Codificação de Huffman

A codificação de Huffman é um algoritmo de compressão sem perdas que atribui códigos de comprimento variável a símbolos com base em suas frequências nos dados de entrada. Símbolos mais frequentes recebem códigos mais curtos, enquanto símbolos menos frequentes recebem códigos mais longos.

O algoritmo funciona construindo uma árvore binária, chamada de árvore de Huffman, de baixo para cima. Cada nó folha representa um símbolo e sua frequência, enquanto cada nó interno representa a soma das frequências de seus filhos. A árvore é construída repetidamente combinando os dois nós com as menores frequências até que reste apenas um nó.

Uma vez construída a árvore, o código de cada símbolo é determinado pelo caminho da raiz atéAqui está a tradução em português do arquivo Markdown, com os comentários traduzidos, mas o código não traduzido:

O nó folha correspondente, com um ramo esquerdo representando um "0" e um ramo direito representando um "1".

Aqui está um exemplo de codificação de Huffman:

Entrada:  "AAAABBBCCCDDDEEE"
Saída: "000010011001011100101"

Árvore de Huffman:
      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

Neste exemplo, "A" recebe o código "00", "B" recebe "01", "C" recebe "10", "D" recebe "110" e "E" recebe "111". A saída compactada é obtida substituindo cada símbolo da entrada pelo seu código correspondente.

A codificação de Huffman é um código de prefixo ótimo, o que significa que nenhum código é prefixo de qualquer outro código. Isso permite a decodificação inequívoca dos dados compactados. A codificação de Huffman é amplamente utilizada em vários formatos de arquivo e ferramentas de compressão, como JPEG, MP3 e ZIP.

Compressão de Lempel-Ziv-Welch (LZW)

A compressão de Lempel-Ziv-Welch (LZW) é um algoritmo de compressão baseado em dicionário que constrói um dicionário (ou livro de códigos) de strings durante a compressão da entrada. O LZW é amplamente usado em utilitários de compressão de arquivos e foi usado no formato de imagem GIF.

A ideia-chave por trás do LZW é substituir strings de caracteres por códigos únicos. Ele lê a string de entrada caractere por caractere e codifica a string em uma representação compacta, substituindo cada código de tamanho fixo por um código de tamanho variável. Quanto maior a string, mais espaço é economizado ao codificá-la como um único número.

Aqui está uma descrição passo a passo de como funciona a compressão LZW:

  1. Inicialize o dicionário para conter todas as strings de um único caractere.
  2. Encontre a string mais longa W no dicionário que corresponda à entrada atual.
  3. Emita o índice do dicionário para W na saída e remova W da entrada.
  4. Adicione W seguido do próximo símbolo na entrada ao dicionário.
  5. Volte para a Etapa 2.

Vamos considerar um exemplo. Suponha que queiramos comprimir a string "ABABABABA" usando LZW.

  1. Inicialize o dicionário para conter "A" e "B".

  2. A correspondência mais longa é "A". Emita seu íAqui está a tradução em português deste arquivo Markdown. Para o código, não traduzi o código, apenas os comentários.

  3. O índice mais longo é "A". Emita seu índice (0) e remova-o da entrada. O dicionário agora contém "A", "B" e "AB".

  4. O índice mais longo é "B". Emita seu índice (1) e remova-o da entrada. O dicionário agora contém "A", "B", "AB" e "BA".

  5. O índice mais longo é "AB". Emita seu índice (2) e remova-o da entrada. O dicionário agora contém "A", "B", "AB", "BA" e "ABA".

  6. O índice mais longo é "ABA". Emita seu índice (4) e remova-o da entrada. O dicionário agora contém "A", "B", "AB", "BA", "ABA" e "ABAB".

  7. O índice mais longo é "BA". Emita seu índice (3). A entrada agora está vazia.

A representação compactada de "ABABABABA" é, portanto, a sequência de índices [1], o que requer menos bits para representar do que a representação ASCII original.

A descompactação funciona de maneira semelhante, mas em ordem inversa:

  1. Inicialize o dicionário para conter todas as strings de um único caractere.
  2. Leia um código X da entrada.
  3. Emita a string para X do dicionário.
  4. Se o código anterior existir, adicione a string anterior concatenada com o primeiro caractere da string para X ao dicionário.
  5. Vá para a Etapa 2.

A compactação LZW é simples e rápida, tornando-a uma boa escolha para muitas aplicações. No entanto, ela possui algumas limitações. O tamanho do dicionário pode crescer bastante, consumindo uma quantidade significativa de memória. Além disso, o dicionário é redefinido após cada bloco de entrada, o que pode reduzir a taxa de compactação para arquivos pequenos.

Apesar dessas limitações, o LZW permanece um algoritmo de compactação popular e eficaz, particularmente para aplicações em que a velocidade é mais importante do que atingir as maiores taxas de compactação possíveis.

Conclusão

Neste capítulo, exploramos vários algoritmos importantes de processamento de strings, incluindo ordenação de strings, tries, pesquisa de substrings, expressões regulares e compactação de dados. Esses algoritmos formam a base para muitas aplicações do mundo real e são ferramentas essenciais para qualquer programador que trabalhe com dados textuais.

Começamos discutindo a ordenação de strings, que são opAqui está a tradução em português do arquivo Markdown, com os comentários de código traduzidos:

Algoritmos de ordenação otimizados que aproveitam as propriedades especiais das strings. Contagem por índice-chave, ordenação LSD por radix e ordenação MSD por radix fornecem métodos eficientes para ordenar strings com base em seus caracteres individuais.

Em seguida, examinamos tries, uma estrutura de dados em árvore para armazenar e recuperar strings. As tries permitem correspondência rápida de prefixos e são comumente usadas em aplicações como autocompletar e tabelas de roteamento IP.

Algoritmos de pesquisa de substrings, como os algoritmos de Knuth-Morris-Pratt e Boyer-Moore, nos permitem pesquisar eficientemente padrões em strings maiores. Esses algoritmos têm inúmeras aplicações em edição de texto, biologia computacional e recuperação de informações.

Expressões regulares fornecem uma maneira poderosa e flexível de descrever padrões de strings. Discutimos a sintaxe básica das expressões regulares e como elas podem ser usadas para correspondência de padrões e manipulação de strings em várias linguagens de programação e ferramentas.

Finalmente, exploramos algoritmos de compressão de dados, que reduzem o tamanho dos dados explorando a redundância e os padrões dentro da entrada. Abordamos a codificação por comprimento de sequência, a codificação de Huffman e a compressão de Lempel-Ziv-Welch, cada uma com suas próprias forças e aplicações.

Entender esses algoritmos e estruturas de dados de processamento de strings é crucial para qualquer pessoa que trabalhe com dados textuais. À medida que a quantidade de dados não estruturados continua a crescer, a capacidade de manipular, pesquisar e comprimir strings de forma eficiente se tornará cada vez mais valiosa. Dominando as técnicas abordadas neste capítulo, você estará bem equipado para enfrentar uma ampla gama de desafios de processamento de strings em seus próprios projetos e aplicações.

Chapter 7 ContextChapter 9 Algorithm Design Paradigms Divide and Conquer