31

Em uma resposta veio o termo assintótica. Em comentário veio uma definição.

Acho que seria ter aqui uma definição mais completa. Mas o foco da pergunta é até mais simples:

Em português claro, ainda que impreciso, o que isso quer dizer para o programador que não tem uma boa base matemática? Por que isso importa para ele?

Para o programador médio isto não é claro e o que isto importa:

Em matemática, uma assíntota/assímptota de uma curva C é um ponto ou uma curva de onde os pontos de C se aproximam à medida que se percorre C Quando C é o gráfico de uma função, em geral o termo assímptota refere-se a uma reta.

10
  • lim x-> N F(x)/G(x) = k para N pertencente R + { -infinito , +infinito } e k pertencente a R* implica que G é assíntota da função F no ponto N (ou nos infinitos). Não está totalmente certo mas é bem próximo Commented 11/01/2018 às 11:51
  • 1
    E nada claro :D
    – Maniero
    Commented 11/01/2018 às 11:57
  • A assíntota de Aquiles é a tartaruga Commented 11/01/2018 às 12:00
  • 1
    @Fernando essa pergunta fornece exemplos de assíntotas para a complexidade temporal de um algoritmo, e as respostas tratam de outros algoritmos também: pt.stackoverflow.com/q/236960/64969 Commented 11/01/2018 às 12:08
  • 2
    @Fernando não sei se é o foco, mas é uma sugestão para quem for responder.
    – Maniero
    Commented 11/01/2018 às 12:08

2 Respostas 2

39
+50

Um conto grego

A assíntota de Aquiles é a tartaruga

Corolário do Paradoxo de Zeno

Um dia, Aquiles, o Herói, e uma tartaruga discutiram. A tartaruga afirmou para Aquiles que, se ela começasse na frente, ela iria vencer uma corrida de qualquer distância contra o Herói. Curioso, Aquiles perguntou

-Por que disso? Se eu sou mais rápido que você, eu irei vencer.

Para então a tartaruga responder:

-Se eu começar na frente, você precisa primeiro alcançar a posição que eu estava. Mas até você chegar lá, eu terei andado, estarei mais adiante. Então, você deverá chegar a minha nova posição, e eu estarei na sua frente. Então você precisará de infinitos passos desses até chegar em mim, pois então para me ultrapassar precisará de mais do que infinitos passos.

Lide com isso, Aquiles

Noção informal de assíntota

No paradoxo de Zeno, não importa quantas vezes Aquiles tente ultrapassar a tartaruga, ele nunca conseguirá. Pois, a cada passo, Aquiles está se aproximando da tartaruga. Aquiles se torna assintoticamente próximo da tartaruga.

Veja os seguinte infográfico, evolução das posições de Aquiles e da tartaruga:

Evolução das posições de Aquiles e da tartaruga pelo tempo

Dá para perceber que Aquiles fica cada vez mais próximo da tartaruga a cada passagem de tempo. A esse tipo de comportamento nós chamamos de assíntota. Daí, a assíntota de Aquiles é a tartaruga.

Quando você quer saber o comportamento geral de uma função, você quer saber qual a assíntota da função. Por exemplo:

metade de: x ao quadrado menos x

Ao infinito, essa função tende a ter o mesmo comportamento que x^2. Então podemos dizer que o comportamento de f(x) = (x^2 - x)/2 é assintoticamente x^2.

Isso tem aplicação prática?

Bem, isso quer dizer que o bubble sort piora tão rápido quando o insertion sort, e também que o merge sort será melhor em casos maiores. Mais tarde, na seção Por que isso importa para o programador?, eu detalharei mais.

Como identificar assíntotas?

De modo geral, você precisa de um "Aquiles" e de uma "tartaruga". A tartaruga será a assíntota de Aquiles.

A função dada como exemplo ela se aproxima de x^2, mas nunca chega nela.

Outro caso também, eu poderia pegar a função 1/x. No infinito positivo, ela tende a ser zero, mas nunca o é:

Desenho da função hiperbólica 1/x

Note que quando x=10, a função vale 0.1. Quando x=80, a função por sua vez agora valeria 0.0125. Ficando cada vez mais próxima de 0, mas nunca de fato chegando lá.

Por que isso importa para o programador?

Em um mundo normal de aplicações corporativas que não se preocupam em calcular qual o desconto (em porcentual) que eu devo aplicar no preço de venda para que o valor com o ICMS-ST alcance o total de R$10,00 no preço final (dica: tem uma fórmula que condensa a soma infinita), assíntotas servem basicamente para descrever comportamentos de algoritmos.

Então, para o programador médio, o que importa é comportamento assintótico, normalmente associado à complexidade temporal/espacial de um algoritmo.

A seguir, uma lista de perguntas que flertam com esse conceito (o autor sabendo disso ou não):

Em todos os casos, se pede algo em relação ao comportamento assintótico (ou como parte da resposta, ou como parte da pergunta).

Também vale para o programador saber que comportamento assintótico nem sempre é tudo. As vezes temos constantes escondidas que, quando não se está "perseguindo tartarugas no infinito", se tornam muito mais importantes. Por exemplo, o quick sort possui o tempo de execução normalmente mais rápido do que o merge sort.

Como provar a ordem assintótica de um algoritmo?

Esta pergunta já tem uma resposta aqui:

Como provar a ordem assintótica de um algoritmo? 3 respostas

Formalmente, o que é uma assíntota?

Uma assíntota é um ponto ou curva para o qual uma função tende. Por exemplo, o centro é a assíntota para a seguinte função polar exponencial:

função f(t) = e^(-0.1 t)

Ela é plotada assim:

plotagem da função f(t) = e^(-0.1 t)

Quanto maior o θ, mais próxima a função fica de (0,0). Então (0,0) é a assíntota de f(t) = e^(-0.1 t).

Uma curva pode interceptar sua assíntota. Por exemplo, f(x) = sen(10*x)/x + x tem como assíntota g(x) = x:

f(x) = sen(10*x)/x + x tem como assíntota g(x) = x

Nem toda assíntota precisa ser uma reta, mas pode ser uma curva. Como o caso de f(x) = |1/x| + x**2, cuja assíntota nos infinitos é g(x) = x**2:

plotagem de f(x) = |1/x| + x**2 e da assíntota g(x) = x**2

Então, a assíntota A de uma função F é um valor (exemplo da espiral) ou função (outros dois exemplos) que, dada a evolução de F em termo de alguma variável, F se aproxima arbitrariamente próxima de A.

Como descobrir uma assíntota de uma função?

Eu normalmente uso os seguintes passos (para funções que usam coordenadas cartesianas, não polares) para descobrir a ordem da assíntota:

  1. conjecture OA
  2. divida* F/OA ou OA/F
  3. se errou, repita

A divisão, entretanto, não pode ser feita de qualquer forma. Normalmente, se deseja saber qual o comportamento extremo da função, então a divisão é com o limite da variável indo ao infinito. Nesse caso de comportamento no infinito, OA é da mesma ordem da assíntota de F se elas forem co-dominantes conforme definida nesta resposta:

verificando dominância entre duas funções

Também condensado nessa resposta do @Isac para a mesma pergunta (obs: com c != 0):

verificando co-dominância

Descoberta a ordem, o valor obtido pela divisão é o coeficiente do maior termo. Isso significa que o termo mais significante da assíntota tem coeficiente conhecido, c. Agora, remova o termo mais significativa e calcule novamente. Como?

Bem, achamos OA a função co-dominante de F. Sabemos que F = OA * c + G, para c = lim OA/F. Então, agora, é achar o valor da assíntota de G e somar a c*OA, fazendo isso recursivamente até que, em algum momento, lim G = 0. Essa será a curva da assíntota de F.

Exemplo

Para f(x) = x + sen(10*x)/x. Vamos primeiro supor que a ordem da função assintótica OA é x**2:

Verificando a dominância f(x) = x + sen(10*x)/x e x**2

Essa divisão dá 0, portanto OA domina f(x). Portanto, a primeira conjectura da ordem da função assintótica deu errado. Nesse caso, repitamos.

Vamos agora supor que a ordem da função assintótica OA é x:

Verificando a dominância f(x) = x + sen(10*x)/x e x

Eles são co-dominantes, então a ordem assintótica é, realmente, OA. Para o próximo passo, precisamos remover c*OA de f(x) e verificar g(x):

Calculando g(x)

Chegamos a conclusão que g(x) = sen(10 x)/x. Agora, precisamos de outro termo para definir a assíntota de g(x)?

Verificando se g(x) se anula no infinito

Não, não precisamos. Portanto, A(x) = x é a assíntota para f(x) = x + sen(10*x)/x.

Existem outras assíntotas que não as do infinito?

Sim, existem. Normalmente, elas se encontram em pontos de descontinuidade.

Tome a hipérbole f(x) = 1/x:

Desenho da função hiperbólica 1/x

Ela apresenta descontinuidade em x = 0. Portanto, o ponto x = 0 é um candidato a ser uma assíntota vertical da função. Para achar uma assíntota vertical no ponto x = a, é preciso atender um desses quatro critérios:

fórmulas critério para assíntota vertical em x = a

A função deve tender ao infinito (positivo ou negativo) quando x tender ao valor a, seja o limite pela esquerda ou o limite pela direita.

No caso da hipérbole, quando x -> 0 pela direita, f(x) -> +infinito. Isso já é o suficiente para considerar x = 0 hipérbole vertical de 1/x.


Fontes das imagens:

5
  • 1
    E vem ele com as dissertações :) Amanhã eu leio, agora vou embarcar
    – Maniero
    Commented 15/01/2018 às 3:12
  • Pra você: i.sstatic.net/k0UNy.gif , haha Commented 15/01/2018 às 3:13
  • 2
    +1 pela historinha da tartaruga que elucidou!
    – user77310
    Commented 15/01/2018 às 4:20
  • @RafaelSalomão nunca mais olhará para tartarugas da mesma forma, haha Commented 15/01/2018 às 9:56
  • 1
    Acho que alguém ganhará um bounty, mas só depois do carnaval, o povo tá de férias :)
    – Maniero
    Commented 15/01/2018 às 10:07
14

Vou ser o mais breve e o mais simples possível e me concentrar em responder:

  1. O que isso quer dizer para o programador que não tem uma boa base matemática?

    Este é o meu caso, não considero ter uma boa base matemática. Mas para mim, o conceito: assíntota me leva a pensar na Notação Assintótica tem relação com a análise de algoritmo e é usado como uma ferramenta de análise para o fim de realizar: Análise Assintótica. Desta forma, podemos assumir que:

    Em geral, cada passo em uma descrição em pseudocódigo ou implementação em linguagem de alto nível corresponde a um pequeno número de oprações primitivas (exceto para chamadas de métodos, naturalmente). Assim, podemos realizar uma análise simplificada de um algoritmo escrito em pseudocódigo que estima o número de operações primitivas executadas, execeto por um fator constante, contando os passos do pseudocódigo (mas deve-se ter cuidado uma vez que uma linha de pseudocódigo pode denotar vários passos em alguns casos).[Goodrich, Michael; Tamassia, Roberto - 2007, 159 p.]

    Para isso usamos a Notação Assintótica, um bom exemplo: Big-O (veja definição aqui: [Luiz Vieira - 56868], muito bem respondida por sinal), ômega: Ω e theta: θ são bem convenientes porque permitem a concentração nos aspectos gerais, em vez dos detalhes.

  2. Por que isso importa para ele?

    Quando assumimos o papel, isto é, usamos o "boné" de programador é muito importante, na análise de algoritmos concentrar-se na taxa de crescimento do tempo de execução.

    E é importante sabermos diferenciar algoritmos eficientes e ineficientes, é natural fazer esta distinção entre os algoritmos que rodam em tempo polinominal e aqueles que requerem tempo exponencial respectivamente.

    Ou seja, faz-se a distinção entre algoritmos que rodam em tempo O(nc) para alguma contante c > 1 e aquele cujo tempo de execução é O(bn) para alguma contante b > 1. ([Goodrich, Michael; Tamassia, Roberto - 2007]).

    Com base nisso podemos usar o gráfico de complexidade abaixo para fazer a distinção visualmente.

    Gráfico que apresenta a relação da Notação Big-O (grande Ó) e as suas complexidades Figura: Gráfico que apresenta a relação da Notação Big-O e suas complexidades
    FONTE: [Maniero - 268308]

    E é claro que é importante para o programador saber que:

    Pode-se usar a Notação Assintótica O (Big-O) para ordenar classes de funções por seu crescimento assintótico.

    Isto é, se uma função f(n) precede uma função g(n) na sequência conforme a tabela abaixo:

    f(n) é O(g(n))

    Tabela: sequência ordenada das classes de funções por seu crescimento assintótico Tabela: sequência ordenada das classes de funções por seu crescimento assintótico
    FONTE: Elaboradas pelo autor da resposta.


Nota1: quanto a base matemática, diremos que devemos manter o hábito de praticar, fazendo listas de exercícios, das funções (fatos matemáticos) aplicáveis na análise de algoritmo.

Nota2: Na tabela cima, assumi o critério de eficiente e ineficiente apenas por ser bem convenientes porque é para concentração nos aspectos gerais, em vez dos detalhes.


Referência:
[Goodrich, Michael; Tamassia, Roberto - 2007], 4 ed. - Porto Alegre: Bookman © 2007, Estrutura de dados e algoritmos em Java: 4 Edição.
[Maniero - 268308], Stack Overflow , Resposta: Como melhorar o desempenho de meu código com “for”?. Acesso em: 14 jan. 2018
[Luiz Vieira - 56868], Stack Overflow , Resposta: Definição da notação “Big O”. Acesso em: 14 jan. 2018

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .