Como calcular o custo de um algoritmo?

De forma rápida, existem duas formas de se calcular o custo de um algoritmo:

• Usando o cálculo de complexidade de tempo[1] (em que o custo é expresso por uma função que varia sobre o tamanho da entrada do algoritmo) e
• Usando o cálculo de complexidade de espaço (em que o custo é expresso por uma função que varia também sobre o espaço em memória, primária ou secundária, usado para finalizar o algoritmo).

A mais comum é calcular a complexidade de tempo ou através de uma função de custo associada ao algoritmo[2] ou à complexidade do pior caso expresso em termos da Notação Assintótica do pior caso[3] (que representa um limite superior[4] para o algoritmo).

Para se chegar à função de custo, normalmente se conta quantas instruções são executadas para o algoritmo para resolver um problema. A função de custa é expressa por um polinômio, em relação ao tamanho da entrada.

Por exemplo, no algoritmo

 for(i=0; i<N; i++){
     print(i);
 }

poderíamos dizer que o tempo gasto é

T(N) =
    N*(tempo gasto por uma comparação entre i e N) +
    N*(tempo gasto para incrementar i) +
    N*(tempo gasto por um print)

Isso daria, no caso, a função de custo T(N) em relação ao tamanho da entrada N.

Já a complexidade usando notação assintótica é, geralmente, mais usada para classes de algoritmos por conta da sua simplicidade e abstração. Siga o raciocínio:

Ao ver uma expressão como n+10 ou n²+1, a maioria das pessoas pensa automaticamente em valores pequenos de n. A análise de algoritmos faz exatamente o contrário: ignora os valores pequenos e concentra-se nos valores enormes de n. Para valores enormes de n, as funções n² , (3/2)n² , 9999n² , n²/1000 , n²+100n , etc. crescem todas com a mesma velocidade e portanto são todas equivalentes.

Esse tipo de matemática, interessado somente em valores enormes de n, é chamado comportamento assintótico[5]. Nessa matemática, as funções são classificadas em ordens[6] (como as ordens religiosas da Idade Média); todas as funções de uma mesma ordem são equivalentes. As cinco funções acima, por exemplo, pertencem à mesma ordem.

Essa ideia reflete que precisamos focar, na verdade, em quão rápido uma função cresce com o tamanho da entrada.(essa é a base da “análise de algoritmos” e o centro de como se calcular o custo de um algoritmo).

Nós chamamos isso de taxa de crescimento do tempo de execução. Para manter as coisas tratáveis, precisamos simplificar a função até evidenciar a parte mais importante e deixar de lado as menos importantes.

Por exemplo, suponha que um algoritmo, sendo executado com uma entrada de tamanho n, leve 6n²+100n+300 instruções de máquina. O termo 6n² torna-se maior do que os outros termos, 100n+300 uma vez que n torna-se grande o suficiente. A partir de 20 neste caso.

Abaixo temos um gráfico que mostra os valores de 6n² e 100n+300 para valores de n variando entre 0 e 100:

Podemos dizer que este algoritmo cresce a uma taxa n², deixando de fora o coeficiente 6 e os termos restantes 100n+300. Não é realmente importante que coeficientes usamos, já que o tempo de execução é an²+bn+c, para alguns números a>0, b, e c, sempre haverá um valor de n para o qual an² é maior que bn+c e essa diferença aumenta juntamente com n. Por exemplo, aqui está um gráfico mostrando os valores de 0,6n² e 1000n+3000 de modo que reduzimos o coeficiente de n² por um fator de 10 e aumentamos as outras duas constantes por um fator de 10:

O valor de n para o qual 0,6n² se torna maior que 1000n+3000 aumentou, mas sempre haverá um ponto de cruzamento, independentemente das constantes. E a partir deste valor de cruzamento, 0,6n² sempre crescerá mais rapidamente (e sempre será maior).

Descartando os termos menos significativos e os coeficientes constantes, podemos nos concentrar na parte importante do tempo de execução de um algoritmo — sua taxa de crescimento — sem sermos atrapalhados por detalhes que complicam sua compreensão. Quando descartamos os coeficientes constantes e os termos menos significativos, usamos notação assintótica. Usa-se, normalmente, três formas: notação Θ[7] , notação O[8] , notação Ω[9] .

Por exemplo, suponha que tenhamos nos esforçado bastante e descoberto que um certo algoritmo gasta tempo

T(N) = 10*N² + 137*N + 15

Nesse caso o termo quadrático 10*N² é mais importante que os outros pois para praticamente qualquer valor de N ele irá dominar o total da soma. A partir de N ≥ 14 o termo quadrático já é responsável pela maioria do tempo de execução e para N > 1000 ele já é responsável por mais de 99%. Para fins de estimativa poderíamos simplificar a fórmula para T(N) = 10*N² sem perder muita coisa.

Vamos começar pelo O-grande, que é uma maneira de dar um limite superior para o tempo gasto por um algoritmo. O(g) descreve a classe de funções que crescem no máximo tão rápido quanto a função g e quando falamos que f ∈ O(g) queremos dizer que g cresce pelo menos tão rápido quanto f. (isso é, claro, um “abuso” matemático. Lembre-se sempre que é uma classe de funções, representando um conjunto de funções)

Formalmente:

Dadas duas funções f e g, dizemos que f ∈ O(g) se existem constantes x0 e c tal que para todo x > x0 vale f(x) < c*g(x)

Nessa definição, a constante c nos dá margem para ignorar fatores constantes (o que nos permite dizer que 10*N é O(N)) e a constante x0 diz que só nos importamos para o comportamento de f e g quando o N for grande e os termos que crescem mais rápido dominem o valor total.

Para um exemplo concreto, considere aquela função de tempo f(n) = 10*N2 + 137*N + 15 de antes.

Podemos dizer que o crescimento dela é quadrático:

Podemos dizer que f ∈ O(N²), já que para c = 11 e N > 137 vale

10*N² + 137*N + 15 < c * N2

Podemos escolher outros valores para c e x0, como por exemplo c = 1000 e N > 1000 (que deixam a conta bem óbvia). O valor exato desses pares não importa, o que importa é poder se convencer de que pelo menos um deles exista.

Na direção oposta do O-grande temos o Ω-grande, que é para limites inferiores. Quando falamos que f é Ω(g), estamos dizendo que f cresce pelo menos tão rápido quanto g. No nosso exemplo recorrente, também podemos dizer que f(n) cresce tão rápido quanto uma função quadrática:

Podemos dizer que f é Ω(N²), já que para c = 1 e N > 0 vale

10*N² + 137*N + 15 > c*N2

Finalmente, o Θ-grande tem a ver com aproximações justas, quando o f e o g crescem no mesmo ritmo (exceto por um possível fator constante). A diferença do Θ-grande para o O-grande e o Ω-grande é que estes admitem aproximações folgadas, (por exemplo, N² ∈ O(N³)) em que uma das funções cresce muito mais rápida que a outra.

Dentre essas três notações, a mais comum de se ver é a do O-grande. Normalmente as análises de complexidade se preocupam apenas com o tempo de execução no pior caso então o limite superior dado pelo O-grande é suficiente.

Para algoritmos recursivos usa-se normalmente uma equação de recorrência[10] para se chegar á função de custo. Então, resolve-se essa equação de recorrência para se chegar à fórmula fechada da recorrência.

Muitas vezes é muito difícil se chegar a uma fórmula fechada, então usa-se outros métodos, como a árvore de recursão e o teorema-mestre[11] para se chegar à análise assintótica (usando a notação O-grande).

Exemplos da taxa de crescimento das principais classes de funções

Notas de rodapé:

[1] Complexidade de tempo – Wikipédia, a enciclopédia livre
[2] Análise de Algoritmos
[3] Big O notation – Wikipedia
[4] Limit superior and limit inferior – Wikipedia
[5] Asymptotic notation
[6] Time complexity – Wikipedia
[7] Notação Big-θ (Grande-Theta) 
[8] Grande-O – Wikipédia, a enciclopédia livre
[9] Notação Big-Ω (Grande-Omega)
[10] http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf
[11] Teorema mestre (análise de algoritmos) – Wikipédia, a enciclopédia livre

Essa foi a minha resposta no Quora à pergunta: “Como calcular o custo de um algoritmo”.

Link: https://pt.quora.com/Como-calcular-o-custo-de-um-algoritmo

Qual a utilidade da orientação a objetos na programação, se podemos simplesmente criar e reutilizar funções?

A maior vantagem da Orientação a Objetos é em prover um nível mais alto de Abstração de Dados e a construção e manutenção facilitada de Tipos Abstratos de Dados (TAD).

Não que isso não seja impossível com a programação estruturada (baseada em funções) – mas fazer e construir TAD’s assim, via programação estruturada é mais complicado e com manutenção mais difícil).

Na Orientação a Objetos o nível de abstração é muito maior e a construção de TAD’s (Tipos Abstratos de Dados) fica mais fácil e natural.

Você pode entender um Tipo Abstrato de Dados como uma expansão das capacidades naturais de uma Linguagem de Programação voltada à resolução de problemas reais. Um exemplo clássico é um tipo de dado racional (uma fração).

Originalmente, boa parte das implementações das linguagens de programação imperativas não oferecem esse tipo de dados de forma primitiva (pense em uma linguagem como C que tem 4 tipos de dados básicos ou primitivos: int, char, float e double). A questão de como representar uma fração racional (um número racional) é um problema.

Usamos, então, TAD’s para solucionar esse problema. Você pode pensar em TAD como uma especificação de um conjunto de dados aliado a algumas operações sobre esses dados. Conceitualmente, um tipo de dados (primitivo) da linguagem (como int ou float do C) também tem essa mesma definição: um range (uma faixa) de valores e um conjunto de operações. No caso do int, por exemplo, essa faixa (range) vai de -2.147.483.648 e 2.147.483.647 (que seriam 4 bytes -> 232232 ) e permite as operações de soma, subtração, multiplicação, divisão, incremento e decremento).

Então. Pense em um TAD como essa expansão que permite você representar coisas (abstrações) do mundo real no computador (uma máquina finita e com limitações de memória, hardware, etc.). Então um tipo de dados racional (uma fração) poderia ser definido e representado (em C) através de um tipo composto (um registro/estrutura) da seguinte maneira:

typedef struct { 
    float num;  //seria o numerador da fração
    float den; // obviamente o denominador
}Fracao;  //o nome do novo tipo de dados

Mas, não esqueça, para abstrair tudo certinho o TAD precisa de operações, portanto, em seguida você fazer funções para criação, adição, subtração, multiplicação, divisão, MDC e quaisquer outras que fossem necessárias para complementar o TAD.

Normalmente se faz isso em C em mais de um arquivo, separando a definição do tipo, da sua interface (as suas funções). Isso funciona. Mas, dar manutenção nisso é bem complicado e quaisquer modificações exigiria alterar código em muitos lugares.

Agora pense nisso em um programa de milhares de linhas com centenas de TAD’s criados assim?

Na Orientação a Objetos tanto a abstração da realidade quanto a criação de TAD’s é simplificada no conceito de classe onde tanto a definição do tipo e as operações (as funções, que na OOP chamamos de métodos) estão todas juntas, como uma peça autônoma de código. Quando você altera qualquer comportamento (ou acrescenta ou retira atributos – propriedades) da classe (do tipo) isso é refletido imediatamente em todos os objetos criados a partir deste modelo (deste tipo).

Em uma linguagem Orientada a Objetos como Java, ou Python, ficaria tudo encapsulado/junto em um código só (em um arquivo só). Da seguinte forma (em Java):

class Fracao {
    int num;
    int den;
public Fracao(){ //construtor
    //a regra da criação da fração viria aqui
    //como não poder criar fração com den == 0
}
public adicao(Fracao y){
    //código da soma
}
public subtração(Fracao y){
    //código da soma
}
public multiplicação(Fracao y){
    //código da soma
}
.... //quaisquer outros métodos ou operações
}

Então a resposta é basicamente essa: para fornecer um nível de abstração maior e de construção de TAD’s mais coeso, mais estruturado e mais funcional.

Além disso há a vantagem de representar o mundo real de forma mais semanticamente correta ou parecida (nível mais alto de abstração) e outras potencialidades como a reutilização de código via herança, interfaces, encapsulamento e polimorfismo.

Há desvantagens também. Não é uma panaceia e não resolve todos os problemas de programação do mundo. Mas, para sistemas grandes, complexos e com alto grau de manutenção ela é muito indicada.

Essa é a resposta que dei no site Quora a essa pergunta.

O link original da resposta é:

https://pt.quora.com/Qual-a-utilidade-da-orienta%C3%A7%C3%A3o-a-objetos-na-programa%C3%A7%C3%A3o-se-podemos-simplesmente-criar-e-reutilizar-fun%C3%A7%C3%B5es