Recursão e análise de algoritmos recursivos

O algoritmo recursivo é aquele que referencia a si mesmo, direta ou indiretamente. Quem chegou até aqui já está cansado de saber disso, já que a recursão é introduzida em PC I.
Dentre os aspectos importantes do algoritmo recursivo está a condição de terminação: sem ela, o algoritmo entra em loop infinito.
Exemplo de uma função recursiva:
   long fatorial(int n) {
      if ((n == 0) || (n == 1)) // condição de terminação
         return 1;
      else // caso recursivo
         return (n * fatorial(n -1));

   }
Observe que a função retorna uma chamada dela mesma com um valor uma unidade menor do que a "origem" da chamada até que este valor seja 0 ou 1.
Durante a execução de um algoritmo recursivo, vão sendo abertas novas chamadas da função conforme o tempo de execução aumenta. Portanto, o número máximo de chamadas abertas é um fator importante a ser considerado ao programar recursivamente. No exemplo do fatorial de n, n chamadas ficam empilhadas na pilha de recursão, pois cada uma espera o resultado da anterior para calcular e retornar um valor.
A recursão nunca deve ser utilizada no lugar de um laço simples. Se a chamada recursiva vier no início ou no fim do código, provavelmente pode ser substituída com facilidade por um laço.
O tempo de execução de um algoritmo recursivo é expresso por uma relação de recorrência, que é uma equação ou inequação que descreve uma função em termos de seus valores sobre entradas menores. É composta pelo caso base (conhecido) e pelo caso indutivo, que é deduzido a partir dos casos anteriores. Exemplo:

A partir da fórmula tem-se

Há o caso base (T(1) = 1) e a fórmula para descobrir um padrão.

Exercícios resolvidos - Complexidade assintótica

Utilizando as definições para as notações assintóticas, prove se são verdadeiras ou falsas as seguintes afirmativas:
1) 3n³ + 2n² + n + 1 = O(n³)
3n³ + 2n² + n + 1 <= c * n³
3 + 2/n + 1/n² + 1 <= c
menor valor possível de c: 3 + 2 + 1 + 1 = 7
verdadeira para c = 7 e n0 = 1

2) 7n² = O(n)
7n² <= c * n
7n <= c
não existe um valor para c que seja sempre maior que n, portanto a afirmação é falsa

3) 2ⁿ⁺² = O(2ⁿ)
2ⁿ⁺² <= c * 2ⁿ
2ⁿ  * 2²<= c * 2ⁿ
2² <= c
verdadeira para n0 = 1 e c = 4

4)2²ⁿ = O(2ⁿ)
(2ⁿ)² <= c * 2ⁿ
2ⁿ <= cnão existe um valor para c que seja sempre maior que n, portanto a afirmação é falsa

5) 5n² + 7n = Θ(n²)
5n² + 7n <= c2 * n²             c1 * n² <= 5n² + 7n
5 + 7/n <= c2                     c1 <= 5 + 7/n
5 + 7/1 <= c2                     c1 <= 5 + 7/infinito
verdadeiro para n0 = 1, c1 = 5 e c2 = 12
no cálculo de c1, considera-se n0 tendendo ao infinito fazendo 7/n assumir o menor valor possível; já no cálculo de c2, considera-se n0 = 1 para que 7/n assuma o maior valor possível.

6) 6n³ + 5n² ≠ Θ(n²)
c1 * n² <= 6n³ + 5n²           6n³ + 5n² <= c2 * n²
c1 <= 6n + 5                      6n + 5 <= c2
para n0 = 1, c1 pode valer 11. Porém, não existe um valor fixo para c2. Portanto, a afirmativa é VERDADEIRA, pois perguntava se a expressão era DIFERENTE de Θ(n²).

7) 9n³ + 3n = Ω(n)
9n³ + 3n >= c * n
9n² + 3 >= c
verdadeira para n0 = 1 e c = 12.

Obs: nem sempre n0 precisa ser 1. Vários pares (ou triplas) de valores podem resolver as expressões.

Complexidade Assintótica

Determinar a função exata do tempo de execução de um programa pode ser uma tarefa complexa - é mais simples determinar a ordem do tempo de execução. É uma definição mais útil, porque para valores grandes de n (sendo n o tamanho da entrada), apenas a ordem de crescimento é relevante. O comportamento assintótico da função é o limite que f(n) atinge quando n aumenta.
Considerações:

• constantes aditivas e multiplicativas não são importantes: podem ser desprezadas
• um polinômio de grau k é O(n^k)
• o termo de maior ordem da função é que conta

Existem 3 notações utilizadas para expressar o comportamento de funções assintóticas:

• Notação O (O grande) - é o limite assintótico superior da ordem de crescimento da função de custo do algoritmo.
  Definição: uma função f(n) é O(g(n)) se existem duas constantes c, n0 >= 0 tais que 0 <= f(n) <= c·g(n) para todo n >= n0.
  Significado: c·g(n) é um limite superior de f(n) para valores grandes de n

---


• Notação Θ - é o limite assintótico firme ou justo ou restrito da ordem de crescimento da função de custo.
  Definição: Uma função f(n) é Θ g(n)) se é  Ω g(n)) e O(g(n)), isto é, se existem constantes c1, c2, n0 > 0 tais que 0 <= c1 g(n) <=  f(n) <= c2g(n) para todo n >= n0Significado: f(n) e g(n) tem a mesma ordem de crescimento. Θ indica um limite firme.

---

• Notação Ω - é o limite assintótico inferior da ordem de crescimento da função de custo.
  Definição: Uma função f(n) é Ω g(n)) se existem constantes positivas c, n0 tais que f(n) >= c·g(n) para n >= n0
  Significado: c·g(n) é um limite inferior de f(n) para n grande.

Existem ainda as notações o (o pequeno) e w (menos utilizadas).
Uma função f(n) é o(g(n)) se, para qualquer constante c > 0 existe uma constante n0 > 0 tal que f(n) < c g(n) para todo n >= n0 (limite superior não assintoticamente restrito). Uma função f(n) é w(g(n)) se, para qualquer constante c > 0 existe uma constante n0 > 0 tal que c g(n) < f(n) para todo n >= n0 (limite inferior não assintoticamente restrito).

Propriedades e características:
O, Θ, Ω são transitivas e reflexivas
● f(n) = O(g(n)) e g(n) = O(h(n)) então f(n) = O(h(n))
● f(n) = O(f(n))
Θ é simétrica
● f(n) = Θ(g(n)) se e somente se g(n) = Θ(f(n))
f(n) = O(g(n)) se e somente se g(n) = Ω(f(n))
analogia com 2 números reais a e b
● f(n) = O(g(n)) » a <= b
● f(n) = o(g(n)) » a < b
● f(n) = Ω(g(n)) » a >= b
● f(n) = Ω(g(n)) » a > b

● f(n) = Θ(g(n)) » a = b

Uma expressão pode ser igualada a uma notação, mas o contrário não acontece.

Classes de complexidade (comportamento assintótico especificado pela notação O)

• complexidade constante: f(n) é O(1)
• complexidade logarítmica: f(n) é O(log n)
• complexidade linear: f(n) é O(n)
• complexidade linear logarítmica: f(n) é O(nlog n)
• complexidade quadrática: f(n) é O(n²)
• complexidade cúbica: f(n) é O(n³)
• complexidade exponencial: f(n) é O(2ⁿ)

Algoritmos com complexidade exponencial normalmente são relacionados a problemas intratáveis. Um algoritmo é considerado intratável se não existe um algoritmo polinomial [O(p(n)) em que p(n) é um polinômio] para resolvê-lo. Portanto, algoritmos polinomiais normalmente são uma boa solução para o problema.

Campo elétrico

Campo elétrico é o que produz a força eletrostática entre duas cargas. Identificado pelo vetor E, o campo em cada ponto é definido pela razão entre a força eletrostática exercida e a carga positiva colocada nesse ponto:

Linhas de campo elétrico são usadas para visualizar a orientação e intensidade dos campos. O vetor campo elétrico em qualquer ponto tem a mesma direção da linha de força caso ela seja retilínea e é tangente à linha caso ela não seja. A densidade das linhas indica a intensidade do campo nessa região.

Campo produzido por uma carga pontual q a uma distância r da carga de teste é dado por  , lembrando do k (constante eletrostática) e û (direção e sentido da força) da matéria anterior. Atenção para o sentido: o campo "sai" da carga caso ela seja positiva e "entra" na carga se for negativa.
Campo produzido por um Dipolo elétrico, que é formado por duas partículas separadas por uma distância d, com cargas de valor absoluto q e sinais opostos, depende do momento dipolar elétrico (que aponta da carga negativa para a positiva). O módulo do campo produzido pelo dipolo em um ponto distante sobre o eixo do dipolo (reta que passa pelas duas cargas) é dado por , sendo que z é a distância entre o ponto e o centro do dipolo. Apesar dessa fórmula tratar apenas de pontos sobre o eixo do dipolo, o campo E em qualquer ponto - no eixo ou não - é proporcional a 1/r³, sendo r a distância entre o ponto e o centro do dipolo.
Campo produzido por uma Distribuição contínua de cargas pode ser calculado tratando elementos de carga como cargas pontuais e somando os campos desses elementos por integração. Lidando com linhas de cargas, é conveniente expressar a carga do objeto em termos da densidade de carga, não de carga total. Há a densidade linear (λ - Coulomb / metro), densidade superficial (σ - Coulomb / metro²) e densidade volumétrica (ρ - Coulomb / metro³). Seguem alguns dos exemplos comuns de distribuição contínua de carga e seus campos:

• Anel delgado
  Seja R o raio de um anel delgado com densidade linear de cargas positivas λ. O campo elétrico no ponto P, localizado no eixo central a uma distância z do plano do anel é calculado da seguinte maneira:
  seja ds o comprimento de um elemento de carga do anel. A carga do elemento é definida dq = λ ds (carga por unidade de comprimento). Esse elemento produz um campo dE no ponto P que está a uma distância r do elemento. O campo dE pode ser expresso por  (z² + R² não saiu do nada, é o teorema de pitágoras aplicado na fórmula. Dá pra ver no desenho, pera). Como dE "sai" da borda do anel e aponta para um ponho sobre o eixo centra, ele faz um ângulo Ô com o eixo z e possui duas componentes: uma paralela ao plano do anel e outra perpendicular. Dando a voltinha no anel, as componentes perpendiculares ao eixo z se cancelam, mas as paralelas não! Taí, o campo vai ser a soma delas. O módulo de cada componente paralela é dE cosÔ . Integrando ao longo da circunferência do anel, temos uma integral de dE indo de s = 0 a s = 2πR. Desenvolvendo fica assim:
• Foi exaustivo escrever esse, então seguinte: página 51 do cap. 21 do Halliday tem as dicas passo a passo de como fazer. Mas deu pra entender né. O outro exemplo seria um disco que é resolvido dividindo em vários anéis e somando através de integral o campo de cada anel mesmo.

Força exercida por um campo elétrico sobre uma carga pontual é dada por F = qE, sendo que o vetor F tem o mesmo sentido de E se q for positiva e sentido oposto se q for negativa.

Força exercida por um campo elétrico sobre um dipolo é dependente do momento dipolar p (vetorial). O campo exerce um torque t sobre o dipolo, definido pelo produto vetorial de p e E (t = p x E - tudo vetorial). A energia potencial U do dipolo depende da orientação em relação ao campo (sendo nula quando p é perpendicular a E, mínima quando  p e E apontam no mesmo sentido e estão alinhados e máxima quando estão alinhados apontando em sentidos opostos. U = -p · E (p e E grandezas vetoriais).

Cargas Elétricas

Ia fazer um resumo mas acabei de me lembrar que o livro do Halliday TEM resumo no final do capítulo. Portanto, vou fazer uso dele e complementar com o que eu achar necessário, afinal, física todo mundo teve no ensino médio.

Carga elétrica, cuja unidade no SI é o Coulomb (C), é a propriedade das partículas que define sua interação elétrica. Cargas iguais se repelem e cargas opostas se atraem, portanto, corpos eletricamente carregados positivamente se repelem e carregados negativamente se atraem. Corpos neutros não são necessariamente descarregados: ser neutro significa que o corpo possui a mesma quantidade de carga positiva e negativa. Materiais condutores são aqueles que possuem elétrons livres, e estes se movem com facilidade. Já os materiais isolantes possuem muito pouca ou nenhuma quantidade de elétrons livres. O movimento de carga nos materiais gera corrente elétrica.
Corrente elétrica, cuja unidade no SI é o ampère (A), é a relação entre a quantidade de carga que passa por um certo ponto em determinado tempo. O coulomb é definido como a carga que passa por um ponto em 1 segundo quando existe uma corrente de 1A naquele ponto. Logo, 1C = (1A)(1s). Como a corrente i é dada por uma taxa de variação, ela será expressada por i = dq / dt.
Lei de Coulomb expressa a força eletrostática entre duas cargas pontuais, q1 e q2 em (ou quase em) repouso, separadas por uma distância r. Como a força é uma grandeza vetorial, é adicionado à fórmula um vetor unitário, que vou chamar de û, que serve apenas para dar a direção e o sentido da força. Logo temos:

O cálculo da força entre duas cargas pode ser feito em pares. Ou seja, se temos 3 cargas, a força resultante em cada uma delas é a soma vetorial da força entre ela e cada uma das outras duas (calculou em pares).
Teoremas: 

• uma casca com distribuição uniforme de carga atrai ou repele uma partícula carregada posicionada do lado de fora dessa casca como se a carga estivesse no centro da casca
• se tem uma partícula carregada dentro da casca com distribuição uniforme de carga, não tem força eletrostática da casca nessa partícula

Carga elementar é a constante física (e = 1,602 x 10^-19C) que denota a unidade mínima de carga, que é uma grandeza quantizada. Ou seja, as cargas elétricas podem ser descritas como ne, sendo n um número inteiro qualquer. Ou seja, a carga elétrica é quantizada. A carga também respeita a lei de conservação: a carga elétrica de qualquer sistema isolado é constante.