Recursão e algoritmos de classificação

vou apresentar praticamente todos os algoritmos de classificação recursivamente,então provavelmente devemos falar sobre recursão. Recursão é realmente uma mente-expandindotécnica, uma vez que você pegar o jeito dele. É também a base para o que poderiaser chamado de “interpretação matemática” da programação de computadores, então se você’area CSci major, você terá que se sentir confortável com isso mais cedo ou mais tarde. Então, vamos olhar para alguns algoritmos simples, tanto o iterativamente (usando loops) e recursivamente.

Encontrar o fatorial

O fatorial de n é definido como o produto de \(n (n-1) (n-2) \ldots (2) (1)\),por exemplo, o produto de todos os inteiros até, e incluindo, n. É fácil writeas um loop:

int factorial_iter(int n) { int r = 1; // Factorial of 0 is 1 for(int i = 1; i <= n; ++i) r *= i; return r;}

Para escrever este, ou qualquer outro algoritmo, recursivamente, temos de fazer duas perguntas:

  • Qual é o menor caso, o caso onde eu posso dar a resposta imediatamente? Isso é chamado de “caso base”. (Às vezes pode haver mais de um caso menor, e tudo bem.)

  • para qualquer coisa que não seja o menor caso, como faço para dividi-lo para torná-lo menor? Isso é chamado de caso recursivo.

para o fatorial, o caso base é o que acontece quando \(n = 0\): o loopdoesn’T é executado e 1 é retornado. Então podemos começar nossa versão recursivacom

int factorial_rec(int n) { if(n == 0) return 1; else ...}

para construir o caso recursivo, precisamos olhar para o que acontece quando n > 0. Em particular, como podemos quebrar \(n!\ ) para baixo em alguns \(n’ !, n ‘ < n\)?O caso mais comum é \(n’ = n – 1\).

uma maneira de ver isso é assumir que já temos o valor de \((n-1)!\ ), e queremos obter \(n!\ ) a partir dele. Ou seja, suponha que factorial_rec(n - 1) funcione e nos dê a resposta certa; só precisamosconstruir o fatorial de n a partir dele. Como podemos fazer isso?\(n! = n (n-1)!\). Então escrevemos nosso caso recursivo assim:

int fact(int n) { if(n == 0) return 1; else return n * fact(n - 1);}

vamos levar um minuto para percorrer o processo de computação factorial_rec(3):

  • fact(3) = 3 * fact(2)

  • fact(2) = 2 * fact(1)

  • fact(1) = 1 * fact(0)

  • fact(0) = 1 e neste ponto, podemos trabalhar o nosso caminho de volta para cima, dando o resultado 3 * 2 * 1 * 1 = 6.

prova indutiva

como mostramos que uma função faz o que deveria fazer? Poderíamos testá-lo, executá-lo milhares ou milhões de vezes e verificar se sua saída é o que esperamos, mas isso exige que criemos uma maneira independente de definirque a função faz (por exemplo ., uma maneira diferente de calcular o fatorial), quepode estar incorreto e, além disso, testes repetidos só podem Daruma confiança estatística de que nosso algoritmo está correto. Se queremos assureir, então precisamos de uma prova lógica ou matemática de que está correta. Para funções recursivas, isso geralmente assume a forma de prova por indução. A prova anindutiva é uma espécie de equivalente matemático a uma função recursiva.Como uma função recursiva, ela tem casos base(S) (um caso base, de fato, para cada caso base na função), e os casos base geralmente são fáceis. Também tem casos indutivos(um para cada caso recursivo na função), que são um pouco mais complicados, mas nos permitem fazer algo como recursão.

considere o exemplo acima. Queremos provar que fact(n) = \(n!\ ), ondea definição de \(n! = n(n-1) (n-2)\ldots(2) (1), 0! = 1\).

prova por indução em n (Qualquer que seja a variável em que fazemos a recursão, dizemos que estamos fazendo “prova por indução” nessa variável):

  • caso Base, \(n = 0\) então fact(0) = 1 = \(0!\ ) e estamos feitos.

  • caso indutivo: No caso indutivo, estamos tentando provar que fact(n) = \(n!\ ) ‘para alguns \(n > 0\). Podemos quebrar os lados esquerdo e Direito e ver que realmente temos

    $$n \cdot \mathtt{fact}(n-1) = n! = n (n-1) (n-2) \ldots (2)(1)$$

    Dividindo a por \(n\) temos

    $$\mathtt{verdade}(n-1) = (n-1)(n-2) \ldots (2)(1) = (n-1)!$$

    em outras palavras, reduzimos o problema de provar que fact(n) = \(n!\ ) para o problema de provar que fact(n-1) = \((n-1)!\). Que não parece útil, mas como em uma função recursiva, onde podemos chamar a função com um menor argumento, em uma prova indutiva podemos reutilizar a prova em si como uma suposição, para um menor \(n\). Chamamos essa suposição de hipótese indutiva e se parece com isso:

    $$\texto {assumir} \ qquad \ mathtt {fato} (n’) = n’! \qquad \text{para todo}\ n’ < n$$

    Se deixarmos \(n’ = n-1\), então temos

    $$\text{Assumir}\qquad\mathtt{verdade}(n-1) = (n-1)!$$

    que é exatamente o que precisávamos acima! Substituindo neste Para o acima, temos

    $$(n-1)! = (n-1)!$$

    e estamos feitos.

como a recursão, o coração de uma prova indutiva é o ato de aplicar a própria prova como uma suposição sobre valores “menores” (\(n’ < n\)). Tecnicamente, existem dois tipos de provas indutivas:

  • “indução do número Natural” só nos permite fazer a suposição sobre \(n ‘ = n-1\). Ou seja, só podemos fazer a suposição sobre uma “entrada” que é menor que a original.

  • “indução forte” nos permite usar qualquer \ (n ‘ < n\). Você pode usar indução forte em qualquer lugar onde você pode usar indução de número natural, mas nem sempre é necessário.

o cálculo do expoente inteiro

lembra quando elaboramos a complexidade de tempo de execução de nossa função “Otimizado” \(O(\log n)\) para encontrar a \(b^n\)? Podemos escrever uma versão recursiva disso também. Mais uma vez, temos que perguntar

  • Qual é o caso base? Nesse caso, é quando \(n = 0\). Nesse caso, \(b^0 = 1\), não importa o que f É(há algum debate sobre \(0^0\)).

  • Qual é o caso recursivo? Como dividimos \(b^n\) em \(b^{n’}\)? Aqui, vamos levar a nossa fila de nossa implementação anterior:

    $$b^n = (b^{n/2})^2 \quad\text{se } n \text{ é mesmo}$$
    $$b^n = b \cdot b^{n-1} \quad\text{se } n \text{ é ímpar}$$

Isso nos dá a seguinte definição:

float powi(float b, int n) { if(n == 0) return 1; else if(n % 2 == 0) { // Even float fp = powi(b, n / 2); return fp * fp; } else if(n % 2 == 1) // Odd return f * powi(b, n - 1);}

Este tem a mesma complexidade como o loop-based versão, e é sem dúvida o mais simples.

neste caso,se quisermos provar que \(\mathtt{powi}(b, n) = b^n\) precisaremos de indução forte, porque um dos casos recursivos encolhe o inputby algo diferente de apenas -1.

Prova de que \(\mathtt{powi}(b,n) = b^n\), por uma forte indução em \(n\):

  • caso Base: \(n = 0\)

    em Seguida, olhando para o programa temos \(\mathtt{powi}(n,0) = 1 = b^0\) e estamos a fazer.

  • caso indutivo: \(n > 0\), prove \(\mathtt{powi} (b,n) = b^n\). Aqui, na verdade, existem dois casos indutivos, um para os dois casos recursivos na função. Nossa indutivo hipótese (suposição) é

    $$\mathtt{powi}(b,n’) = b^{n}\qquad \text{para todo}\ n’ < n$$
    • Caso 1, \(n\) é o mesmo. Em seguida, substituir a chamada de powi pelo seu valor de retorno, temos

      $$\mathtt{powi}(b, n / 2)^2 = b^n$$ $$\mathtt{powi}(b, n / 2)^2 = b^{n/2})^2$$

      Tomando a raiz quadrada de ambos os lados:

      $$\mathtt{powi}(b, n/2) = b^{n/2}$$

      em que ponto podemos aplicar o IH, com \(n’ = n/2\), dando –

      $$b^{n/2} = b^{n/2}$$
    • Caso 2, \(n\) é ímpar. Em seguida, expandindo powi temos

      $$b \cdot \mathtt{powi}(b,n-1) = b \cdot b^{n-1}$$ $$\mathtt{powi}(b,n-1) = b^{n-1} (\text{ dividir por } b)$$ $$b^{n-1} = b^{n-1}\qquad\text{por IH, }(n’ = n-1)$$

    E a prova está completa

Mútuo recursão

Mútuo recursão é quando temos que definir várias funções recursivas em termos ofeach outros. Por exemplo, considere a seguinte definição de par e ímpar:

  • um número natural n É par iff \(n-1\) é ímpar.

  • um número natural n é ímpar iff \(n-1\) é par.

  • \(1\) é estranho, \(0\) é par. (Estes são os nossos casos básicos.)

podemos, então, definir duas funções (predicados) que recursivamente referir-se a si:

bool is_even(int n) { if(n == 0) return true; else if(n == 1) return false; else return is_odd(n - 1);}bool is_odd(int n) { if(n == 0) return false; else if(n == 1) return true; else return is_even(n - 1);}

Se acompanhamos a transformação de determinar is_even(4), vamos ver thatit salta para trás e para a frente entre is_even e is_odd.

pesquisa binária

fizemos uma pesquisa binária iterativamente, mas também podemos fazê-lo recursivamente:

  • existem dois casos básicos: quando encontramos o item, ou quando o espaço de busca é reduzido para 0 (indicando que o item não é encontrado).

  • O recursiva caso, compara-se o valor da meta para o valor atual do ponto médio, e, em seguida, reduz o tamanho do espaço de busca (por recursivamente a pesquisa à esquerda ou direita).

Isso parece

template<typename T>int binary_search(const vector<T>& data, int low = 0, int high = data.size()-1, const T& target) { if(low > high) return -1; int mid = low + (high - low) / 2; // Why did I do this? if(data.at(mid) == target) return mid; else if(data.at(mid) < target) // Search right return binary_search(data, mid+1, high, target); else if(data.at(mid) > target) // Search left return binary_search(data, low, mid-1, target);}

Outros exemplos: Contagem do número de cópias em um vetor. Para qualquer recursão de estilo vetorial, precisamos acompanhar nosso” ponto de partida ” comNo vetor. Isto é, porque não podemos fazer o vetor em si menor, de modo wehave para colocar um marcador para ele mostrar onde estamos começando. Podemos fazer thisin duas maneiras, com um int start parâmetro, ou usando iteradores.

template<typename T>int count(vector<T> data, int start, T target) { if(start == data.size()) return 0; else return (data.at(start) == target) + count(data, start + 1, target);}

Com iteradores:

template<typename T, typename It>int count(It start, It finish, T target) { if(start == finish) return 0; else return (*start == target) + count(start + 1, finish, target);}

Iteradores são como ponteiros.

algoritmos de Ordenação

Um algoritmo de ordenação é uma função que leva uma sequência de itens e somehowconstructs uma permutação deles, de tal forma que eles estão ordenados de alguma forma.Normalmente, queremos que as coisas sejam ordenadas de acordo com os operadores de comparação normais, de modo que se a < b então a vem antes de b na permutação final.Ainda, há algumas coisas que temos que ter certeza de que acertamos:

  • obviamente, não podemos perder nenhum elemento através do processo.

  • pode haver duplicatas no original, em caso afirmativo, deve haver um número igual de duplicatas na saída.

  • Para sua conveniência, nós permitir a ordenação de uma seqüência vazia (que, quando classificados, resulta em ainda outra sequência vazia)

Existem alguns termos associados com a classificação de que é importante estar ciente de:

  • Estabilidade – quando a seqüência de entrada tem elemento que comparar como iguais, mas que são distintos (por exemplo, funcionários com nomes idênticos, mas caso contrário, pessoas diferentes) surge a questão de saber se, na seqüência de saída, que ocorrem na mesma ordem como no original. Por exemplo., se o funcionário “John Smith” #123 veio antes de “John Smith” #234 na sequência original, então dizemos que uma classificação é estável se #123 for Antes de #234 no resultado.

    a estabilidade é importante ao classificar uma sequência em vários critérios. Por exemplo, se classificarmos com base no primeiro nome, então com base no sobrenome, uma classificação instável não nos dará o resultado que queremos: as entradas do primeiro nome serão todas misturadas.

  • adaptabilidade – algumas sequências de entrada já estão parcialmente (ou completamente) classificadas; um algoritmo de classificação adaptável será executado mais rápido (em termos de big-o) em entradas parcialmente classificadas. O tempo de execução ideal para uma entrada completamente classificada é \(O(n)\), o tempo que leva para verificar se a entrada já está classificada.

  • in-Place-um algoritmo de classificação no local é aquele que não precisa de espaço extra (ou seja, sua complexidade de espaço é \(O(1)\)) para classificar. Alguns algoritmos não podem ser usados no lugar e precisam construir uma sequência de saída separada do mesmo tamanho da entrada para gravar os resultados.

  • Online-alguns conjuntos de dados são muito grandes para caber na memória. Um algoritmo de classificação online é aquele que requer que todos os seus dados sejam acessíveis (na memória). Algoritmos de classificação Offline podem classificar dados que estão parcialmente na memória, parcialmente no disco ou outro armazenamento “lento”, sem afetar sua complexidade de tempo.

classificação de Seleção

já olhou para seleção de ordenação, então, vamos olhar para ele de novo:

  • A seleção de ordenar uma lista de itens, temos de encontrar o primeiro item mais pequeno em toda a lista, e colocá-lo no início.

  • em seguida, encontramos o menor item em tudo após o primeiro item e o colocamos em segundo lugar.

  • Continue até que não haja mais nada sem classificação.

efetivamente, selection sort divide a lista na região classificada no início e a região não classificada no final. A região classificada cresce, enquantoa região não classificada encolhe.

a classificação de seleção não é estável.

iterativamente, isso se parece com isso:

template<typename T>void selection_sort(vector<T> data) { for(auto it = begin(data); it != end(data)-1; ++it) { // Find smallest auto smallest = it; for(auto jt = it+1; jt != end(data); ++jt) if(*jt < *smallest) smallest = jt; // Swap it into place swap(it, smallest); }}

vamos traçar isso em um pequeno exemplo para ter uma ideia de como funciona.

como podemos implementar isso recursivamente? Em vez de passar pelovector real, vamos apenas passar os iteradores para o inícioe fim do vetor. Por que fazemos isso se tornará óbvio, em breve:

template<typename Iterator>void selection_sort(Iterator first, Iterator last) { ...}

vamos analisar a recursão:

  • o caso base é quando last == first + 1. Isso significa que há apenas 1 elemento e uma lista de 1 elemento é sempre classificada.

  • o caso recursivo é quando last - first > 1. Nesse caso, dividimos recursivamente em

    • encontrando o mínimo da região e colocando-a no início.
    • seleção recursiva-classificando first+1 por last(porque o elemento em first está agora no lugar correto).
template<typename Iterator>void selection_sort(Iterator first, Iterator last) { if(last - first == 1) return; // 1 element, nothing to sort else { // Find minimum Iterator smallest = first; for(Iterator it = first; it != last; ++it) if(*it < *smallest) smallest = it; // Swap into place swap(*smallest, *first); // Recursively sort the remainder selection_sort(first + 1, last); }}

Vamos desenhar a árvore de recursão para isso. Não rastrearemos o loop, vamos apenas assumir (por enquanto) que ele funciona corretamente.

DIAGRAMA

Classificação algoritmo de análise de

Além de analisar o geral melhor/pior-caso o grande-O tempo de execução de um algoritmo de ordenação, é comum também analisar dois outros recursos de tempo de execução:

  • O número de comparações entre elementos. Isso conta apenas comparações entre os objetos que estão sendo classificados, não a comparação de (por exemplo) uma variável de contador de loop.

  • o número de trocas entre elementos.

Analisando o número de comparações e de swaps é útil porque essas operações estão no coração de qualquer algoritmo de ordenação: não podemos saber whetherelements estão fora de ordem até podemos compará-los (e, se os elementos são complexas, comparando-las pode levar um não-trivial quantidade de tempo), e nós cannotput-los na ordem correta, sem movimentá-las – por exemplo, trocando-os.

Bubble sort

Bubble sort é um algoritmo de classificação que não é realmente adequado para implementação recursiva. A ideia é comparar elementos adjacentes na entrada (por exemplo,, a e a) e troque-os se estiverem fora de ordem. Começamos no início da entrada e passamos por ela, trocando nosso caminhopara o fim. Após uma dessas passagens, o maior elemento terá “borbulhado” até o último elemento da matriz. Então, podemos fazer outro passe, mas pulamos o último elemento desta vez. Enquanto selction sort fez passes cada vez menores a partir da frente, bubble sort faz pequenos e pequenos trechos do final.

Bubble sort é estável.

uma implementação se parece com isso:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) swap(data.at(i), data.at(i + 1));}

conforme implementado, esta função é de ordem\ (O (n^2)\) em ambos os melhores casos andworst; loop aninhado, com a mesma estrutura “triangular” que vimos antes.Podemos realmente implementar uma otimização simples: no loop interno, se não realizarmos swaps, a entrada é classificada e podemos parar. Se verificarmos isso, pode nos permitir sair mais cedo.

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); sorted = false; } if(sorted) return; }}

agora, quais são os melhores e piores casos?

  • o melhor caso é quando a entrada já está classificada. Nesse caso, fazemos uma passagem pelo vetor (para verificar se está classificado), mas não trocamos nada e depois retornamos. Portanto, o melhor caso de eficiência de tempo de execução é \(O (n)\).

  • o pior caso é uma matriz que é classificada em ordem decrescente. Cada elemento terá que” borbulhar ” toda a distância até o local adequado, então nunca sairemos mais cedo (devido a sorted) e a condição na instrução if será verdadeira todas as vezes, então executaremos quantas trocas forem necessárias. Se fizermos a soma, obtemos

    $$\sum_{j = 1}^n (n – j) = n – \sum_{j = 1}^n j$$

    onde a segunda soma expande-se para \(\frac{n(n+1)}{2}\), dando-nos uma ordem de \(S(n)\).

correção do tipo de bolha

se quisermos provar a correção do tipo de bolha, como de costume, tudo se reduzpara escolher o(s) invariante (s) certo (s). Aqui, é útil se tivermos dois, um de cada loop:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); // INVARIANT: every element in data to data is *smaller* // than data. sorted = false; } // INVARIANT: every element of data to data is smaller // than data, and every element of data to // data is larger than data. (That is, // data is in the right place.) if(sorted) return; }}

classificação de inserção

suponha que dividamos a entrada em duas “seções”, classificadas e não classificadas. A seção classificada está inicialmente vazia. Para cada elemento na seção não classificada,inserimos na seção classificada, em sua posição adequada, classificada. PorqueEste é um array / vetor, inserir um elemento requer mudar todos os elementosdepois de um passo. Embora possamos construir uma versão disso que opera “no lugar”, em uma única matriz (porque quando a região classificada cresce em 1, a região não classificada encolhe em 1, Então o tamanho total é sempre n), será mais fácil entender se escrevemos como uma função que move elementos de um vetor Não classificado para um vetor Classificado, que é então retornado.

a classificação de inserção é estável.

template<typename T>vector<T> insertion_sort(vector<T>& data) { vector<T> sorted; for(int i = 0; i < data.size(); ++i) { T& item = data.at(i); // Find the proper place for item in sorted int pos = sorted.size(); // Defaults to the end for(int j = 0; j < sorted.size(); ++j) if(sorted.at(j) >= item) { pos = j; break; } // Insert the item at pos, by shifting everything forward // (Increases the size of sorted by 1) sorted.insert(sorted.begin() + pos, item); }}

quais são os melhores e piores casos para este algoritmo? É um pouco complicado descobrir porque a complexidade do insert é proporcional ao número de elementos movidos (isto é, para sorted.size() - pos). Assim, enquanto theloop para encontrar a posição pode sair mais cedo (ainda na primeira iteração), thisis ruim para a inserção, que implica que pos será pequeno e, portanto, theruntime de insert bastante ruim. Por outro lado, se o loop interno for executado até o final (pos = sorted.size()), então o insert effectivelydoes nada mais do que um push_back.

na verdade, o loop interno e o insert sempre se equilibram, de modo que o total entre eles é sorted.size(). E sorted.size() aumenta em umtodos os tempos através do loop externo, então mais uma vez temos nosso loop “triangular”.

podemos escrever uma versão recursiva com a ajuda de funções de utilitário:

  • insert coloca um elemento no lugar adequado na região classificada, novamente mudando tudo para cima.

com esses dois no lugar, a implementação recursiva torna-se

template<typename Iterator>void insertion_sort(Iterator start, Iterator unsorted, Iterator finish) { if(start == finish - 1) return; // One element else { // Insert first unsorted element into sorted region insert(start, unsorted, *unsorted); // Recursively sort the remainder of the unsorted region. insertion_sort(start, unsorted+1, finish); }}

Deixe uma resposta

O seu endereço de email não será publicado.