Vídeo: Matemática Elementar - Aula 06 - Logaritmos, funções exponenciais e logarítmicas 2025
Uma função em matemática é simplesmente uma maneira de mapear algumas entradas para uma resposta. Exigido de forma diferente, uma função é uma transformação (baseada em operações matemáticas) que transforma (mapeia) a sua entrada para uma resposta.
Para certos valores de entrada (geralmente indicados pelas letras x ou n), você tem uma resposta correspondente usando a matemática que define a função. Por exemplo, uma função como f (n) = 2 n diz que, quando a sua entrada é um número n, sua resposta é o número n multiplicado por 2.
Usar o tamanho da entrada faz sentido dado que esta é uma era crítica e as vidas das pessoas estão repletas de uma quantidade crescente de dados. Fazer com que tudo seja uma função matemática é um pouco menos intuitiva, mas uma função que descreve como um algoritmo relaciona sua solução com a quantidade de dados que recebe é algo que você pode analisar sem suporte específico de hardware ou software. Também é fácil de comparar com outras soluções, dado o tamanho do seu problema. A análise de algoritmos é realmente um conceito insensível porque reduz uma série complexa de etapas em uma fórmula matemática.
Além disso, a maior parte do tempo, uma análise de algoritmos nem sequer interessa em definir a função exatamente. O que você realmente quer fazer é comparar uma função de destino com outra função. Essas funções de comparação aparecem dentro de um conjunto de funções propostas que funcionam mal quando comparadas ao algoritmo de destino. Desta forma, você não precisa conectar números em funções de maior ou menor complexidade; Em vez disso, você lida com funções simples, premade e bem conhecidas. Pode parecer áspero, mas é mais eficaz e é semelhante a classificar o desempenho de algoritmos em categorias, ao invés de obter uma medida de desempenho exata.
O conjunto de funções generalizadas é chamado de Big O, e muitas vezes você encontra este pequeno conjunto de funções (coloque entre parênteses e precedido por um O >) usado para representar o desempenho de algoritmos. A figura mostra a análise de um algoritmo. Um sistema de coordenadas cartesianas pode representar sua função medida pela simulação de RAM, onde o abscissa (a coordenada x) é o tamanho da entrada e a ordenada (a coordenada y) é sua número de operações resultantes. Você pode ver três curvas representadas. O tamanho da entrada é importante. No entanto, a qualidade também é importante (por exemplo, ao solicitar problemas, é mais rápido pedir uma entrada que já está quase ordenada).Consequentemente, a análise mostra um pior caso, f 1 (n), um caso médio, f 2 (n), e um melhor caso f 3 (n). Embora o caso médio possa lhe dar uma idéia geral, o que você realmente se importa é o pior caso, porque problemas podem surgir quando seu algoritmo se esforça para alcançar uma solução. A função Big O é a que, após um certo valor
n0
(o limite para considerar uma entrada grande), sempre resulta em um número maior de operações com a mesma entrada que a função do pior caso > f1
. Assim, a função Big O é ainda mais pessimista do que a que representa o seu algoritmo, de modo que não importa a qualidade da entrada, você pode ter certeza de que as coisas não podem piorar do que isso.
Complexidade de um algoritmo em caso de melhor, médio e pior caso de entrada.
Muitas funções possíveis podem resultar em resultados pior, mas a escolha das funções oferecidas pela notação Big O que você pode usar é restrita porque o objetivo é simplificar a medida de complexidade, propondo um padrão. Consequentemente, esta seção contém apenas as poucas funções que fazem parte da notação Big O. A lista a seguir descreve-os em crescente ordem de complexidade:
Ao mesmo tempo, independentemente da quantidade de entrada que você fornecer. No final, é um número constante de operações, não importa quanto tempo sejam os dados de entrada. Esse nível de complexidade é bastante raro na prática.
- Complexidade logarítmica O (log n): O número de operações cresce a uma taxa mais lenta do que a entrada, tornando o algoritmo menos eficiente com pequenas entradas e mais eficiente com as maiores. Um algoritmo típico desta classe é a pesquisa binária.
- Complexidade linear O (n): As operações crescem com a entrada em uma proporção de 1: 1. Um algoritmo típico é iteração, que é quando você digitaliza a entrada uma vez e aplica uma operação a cada elemento dela.
- Complexidade linearítmica O (n log n): A complexidade é uma mistura entre a complexidade logarítmica e linear. É típico de alguns algoritmos inteligentes usados para solicitar dados, como Mergesort, Heapsort e Quicksort.
- Complexidade quadrática O (n 2
- ): As operações crescem como um quadrado do número de entradas. Quando você tem uma iteração dentro de outra iteração (iterações aninhadas, em ciência da computação), você tem complexidade quadrática. Por exemplo, você tem uma lista de nomes e, para encontrar os mais parecidos, você compara cada nome com todos os outros nomes. Alguns algoritmos de ordenação menos eficientes apresentam tal complexidade: tipo de bolha, classificação de seleção e classificação de inserção. Esse nível de complexidade significa que seus algoritmos podem ser executados por horas ou mesmo dias antes de alcançar uma solução. Complexidade cúbica O (n 3
- ): As operações crescem ainda mais rápido do que a complexidade quadrática porque agora você possui várias iterações aninhadas. Quando um algoritmo tem essa ordem de complexidade e você precisa processar uma quantidade modesta de dados (100 000 elementos), seu algoritmo pode ser executado por anos.Quando você tem uma série de operações que é uma potência da entrada, é comum se referir ao algoritmo como executado em tempo polinomial. Complexidade exponencial O (2 n
- ): O algoritmo leva duas vezes o número de operações anteriores para cada novo elemento adicionado. Quando um algoritmo tem essa complexidade, mesmo pequenos problemas podem demorar para sempre. Muitos algoritmos que fazem buscas exaustivas têm complexidade exponencial. No entanto, o exemplo clássico para esse nível de complexidade é o cálculo dos números Fibonacci. Complexidade fatorial O (n!): Um pesadelo real de complexidade devido ao grande número de combinações possíveis entre os elementos. Imagine: se a sua entrada é de 100 objetos e uma operação em seu computador leva 10
- -6 segundos (uma velocidade razoável para cada computador, hoje em dia), você precisará de cerca de 10 140 anos para completar a tarefa com sucesso (uma quantidade impossível de tempo desde que a idade do universo é estimada em 10 14 anos). Um problema de complexidade fatorial famoso é o problema dos vendedores ambulantes, em que um vendedor deve encontrar a rota mais curta para visitar muitas cidades e voltar para a cidade inicial.
