algorithm - truques - little big city dinheiro infinito




Big O, como você o calcula/aproxima? (16)

A maioria das pessoas com um diploma em CS certamente saberá o que significa Big O. Isso nos ajuda a medir a eficiência (in) eficiente de um algoritmo e, se você souber em qual categoria o problema que está tentando resolver, pode descobrir se ainda é possível extrair esse pequeno desempenho extra. 1

Mas estou curioso, como você calcula ou aproxima a complexidade de seus algoritmos?

1 mas, como se costuma dizer, não exagere, a otimização prematura é a raiz de todo mal , e a otimização sem uma causa justificada também merece esse nome.


A notação Big O é útil porque é fácil trabalhar com e oculta complicações e detalhes desnecessários (para algumas definições de desnecessário). Uma boa maneira de descobrir a complexidade dos algoritmos de dividir e conquistar é o método de árvore. Digamos que você tenha uma versão do quicksort com o procedimento mediano, portanto, divida a matriz em sub-arrays perfeitamente equilibrados sempre.

Agora construa uma árvore correspondente a todas as matrizes com as quais você trabalha. Na raiz, você tem a matriz original, a raiz tem dois filhos, que são os sub-arranjos. Repita isso até ter matrizes de elemento único na parte inferior.

Como podemos encontrar a mediana no tempo de O (n) e dividir a matriz em duas partes no tempo de O (n), o trabalho realizado em cada nó é O (k), onde k é o tamanho da matriz. Cada nível da árvore contém (no máximo) toda a matriz, de modo que o trabalho por nível é O (n) (os tamanhos das sub-matrizes somam n, e como temos O (k) por nível, podemos adicionar isso) . Existem apenas níveis de log (n) na árvore, pois cada vez que reduzimos a entrada pela metade.

Portanto, podemos limitar a quantidade de trabalho por O (n * log (n)).

No entanto, o Big O esconde alguns detalhes que às vezes não podemos ignorar. Considere calcular a sequência de Fibonacci com

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

e vamos apenas assumir que a e b são BigIntegers em Java ou algo que pode lidar com números arbitrariamente grandes. A maioria das pessoas diria que este é um algoritmo O (n) sem vacilar. O raciocínio é que você possui n iterações no loop for e O (1) trabalha ao lado do loop.

Mas os números de Fibonacci são grandes, o n-ésimo número de Fibonacci é exponencial em n; portanto, apenas o armazenamento será da ordem de n bytes. Realizar adição com números inteiros grandes exigirá O (n) quantidade de trabalho. Portanto, a quantidade total de trabalho realizado neste procedimento é

1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)

Portanto, esse algoritmo é executado em tempo quadrádico!


Basicamente, o que aparece 90% do tempo é apenas analisar loops. Você tem loops simples, duplos e triplos aninhados? Você tem O (n), O (n ^ 2), O (n ^ 3) tempo de execução.

Muito raramente (a menos que você esteja escrevendo uma plataforma com uma extensa biblioteca base (como, por exemplo, o .NET BCL ou o STL do C ++), você encontrará algo mais difícil do que apenas olhar seus loops (para obter instruções, while, goto, etc ...)


Divida o algoritmo em partes que você conhece a grande notação O e combine através de grandes operadores O. Essa é a única maneira que eu conheço.

Para mais informações, consulte a página da Wikipedia sobre o assunto.


Embora seja útil saber como descobrir o tempo grande para o seu problema específico, conhecer alguns casos gerais pode ajudar bastante a tomar decisões em seu algoritmo.

Aqui estão alguns dos casos mais comuns, retirados de http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O (1) - Determinando se um número é par ou ímpar; usando uma tabela de pesquisa de tamanho constante ou tabela de hash

O (logn) - Localizando um item em uma matriz classificada com uma pesquisa binária

O (n) - Localizando um item em uma lista não classificada; adicionando dois números de n dígitos

O (n 2 ) - Multiplicando dois números de n dígitos por um algoritmo simples; adicionando duas matrizes n × n; classificação por bolha ou inserção

O (n 3 ) - Multiplicando duas matrizes n × n por algoritmo simples

O (c n ) - Encontrar a solução (exata) para o problema do vendedor ambulante usando programação dinâmica; determinar se duas instruções lógicas são equivalentes usando força bruta

O (n!) - Resolvendo o problema do vendedor ambulante por meio da pesquisa de força bruta

O (n n ) - frequentemente usado em vez de O (n!) Para derivar fórmulas mais simples para complexidade assintótica


Eu penso sobre isso em termos de informação. Qualquer problema consiste em aprender um certo número de bits.

Sua ferramenta básica é o conceito de pontos de decisão e sua entropia. A entropia de um ponto de decisão é a informação média que ele fornecerá. Por exemplo, se um programa contém um ponto de decisão com duas ramificações, sua entropia é a soma da probabilidade de cada ramificação vezes o log 2 da probabilidade inversa dessa ramificação. É o quanto você aprende executando essa decisão.

Por exemplo, uma instrução if com duas ramificações, ambas igualmente prováveis, tem uma entropia de 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Portanto, sua entropia é de 1 bit.

Suponha que você esteja pesquisando uma tabela de N itens, como N = 1024. Esse é um problema de 10 bits porque log (1024) = 10 bits. Portanto, se você puder pesquisá-lo com instruções IF com resultados igualmente prováveis, deve tomar 10 decisões.

É o que você obtém com a pesquisa binária.

Suponha que você esteja fazendo uma pesquisa linear. Você olha para o primeiro elemento e pergunta se é o que deseja. As probabilidades são 1/1024, e 1023/1024, não. A entropia dessa decisão é 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * cerca de 0 = cerca de 0,01 bits. Você aprendeu muito pouco! A segunda decisão não é muito melhor. É por isso que a pesquisa linear é tão lenta. De fato, é exponencial o número de bits que você precisa aprender.

Suponha que você esteja fazendo indexação. Suponha que a tabela seja pré-classificada em vários compartimentos e você use alguns dos bits da chave para indexar diretamente para a entrada da tabela. Se houver 1024 posições, a entropia será 1/1024 * log (1024) + 1/1024 * log (1024) + ... para todos os 1024 resultados possíveis. Isso é 1/1024 * 10 vezes 1024 resultados ou 10 bits de entropia para essa operação de indexação. É por isso que a pesquisa de indexação é rápida.

Agora pense em classificação. Você tem N itens e uma lista. Para cada item, você precisa procurar para onde o item está na lista e adicioná-lo à lista. Portanto, a classificação leva aproximadamente N vezes o número de etapas da pesquisa subjacente.

Portanto, tipos baseados em decisões binárias com resultados aproximadamente igualmente prováveis ​​tomam todas as etapas O (N log N). Um algoritmo de classificação O (N) é possível se for baseado na pesquisa de indexação.

Descobri que quase todos os problemas de desempenho algorítmico podem ser analisados ​​dessa maneira.


Familiaridade com os algoritmos / estruturas de dados que eu uso e / ou análise rápida do aninhamento de iterações. A dificuldade é quando você chama uma função de biblioteca, possivelmente várias vezes - muitas vezes você pode não ter certeza se está chamando a função desnecessariamente às vezes ou qual implementação elas estão usando. Talvez as funções da biblioteca devam ter uma medida de complexidade / eficiência, seja Big O ou outra métrica, disponível na documentação ou mesmo no IntelliSense .


Lembrete pequeno: a big O notação big O é usada para denotar complexidade assintótica (ou seja, quando o tamanho do problema cresce até o infinito) e oculta uma constante.

Isso significa que entre um algoritmo em O (n) e um em O (n 2 ), o mais rápido nem sempre é o primeiro (embora exista sempre um valor de n tal que, para problemas de tamanho> n, o primeiro algoritmo seja o mais rápido).

Note que a constante oculta depende muito da implementação!

Além disso, em alguns casos, o tempo de execução não é uma função determinística do tamanho n da entrada. Faça a classificação usando a classificação rápida, por exemplo: o tempo necessário para classificar uma matriz de n elementos não é uma constante, mas depende da configuração inicial da matriz.

Existem diferentes complexidades de tempo:

  • Pior caso (geralmente o mais simples de entender, embora nem sempre seja muito significativo)
  • Caso médio (geralmente muito mais difícil de descobrir ...)

  • ...

Uma boa introdução é Uma Introdução à Análise de Algoritmos, de R. Sedgewick e P. Flajolet.

Como você diz, a premature optimisation is the root of all evil , e (se possível) a criação de perfis sempre deve ser usada ao otimizar o código. Pode até ajudá-lo a determinar a complexidade de seus algoritmos.


Para o 1º caso, o loop interno é executado ni vezes, portanto, o número total de execuções é a soma de i passando de 0 a n-1 (porque menor que, não menor que ou igual) do ni . Você obtém finalmente n*(n + 1) / 2 , então O(n²/2) = O(n²) .

Para o segundo loop, i está entre 0 e n incluído no loop externo;então o loop interno é executado quando jfor estritamente maior que n, o que é impossível.


Se o seu custo for um polinômio, mantenha o prazo mais alto, sem o multiplicador. Por exemplo:

O ((n / 2 + 1) * (n / 2)) = O (n 2/4 + n / 2) = O (n 2/4) = O (n 2 )

Isso não funciona para séries infinitas, veja bem. Não existe uma receita única para o caso geral, embora em alguns casos comuns sejam aplicadas as seguintes desigualdades:

O (log N ) <O ( N ) <O ( N log N ) <O ( N 2 ) <O ( N k ) <O (e n ) <O ( n !)


Se você deseja estimar a ordem do seu código empiricamente, em vez de analisá-lo, você pode manter uma série de valores crescentes de n e cronometrar seu código. Plote seus horários em uma escala de log. Se o código for O (x ^ n), os valores deverão cair em uma linha de inclinação n.

Isso tem várias vantagens em apenas estudar o código. Por um lado, você pode ver se está no intervalo em que o tempo de execução se aproxima de sua ordem assintótica. Além disso, você pode achar que algum código que você pensou que fosse da ordem O (x) é realmente da ordem O (x ^ 2), por exemplo, devido ao tempo gasto nas chamadas da biblioteca.


Vendo as respostas aqui, acho que podemos concluir que a maioria de nós realmente aproxima a ordem do algoritmo olhando -o e usando o bom senso em vez de calculá-lo com, por exemplo, o método mestre, como pensávamos na universidade. Com isso dito, devo acrescentar que mesmo o professor nos incentivou (mais tarde) a pensar sobre isso em vez de apenas calculá-lo.

Também gostaria de adicionar como isso é feito para funções recursivas :

suponha que tenhamos uma função como ( código do esquema ):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

que calcula recursivamente o fatorial do número fornecido.

O primeiro passo é tentar determinar a característica de desempenho para o corpo da função apenas neste caso, nada de especial é feito no corpo, apenas uma multiplicação (ou o retorno do valor 1).

Portanto, o desempenho para o corpo é: O (1) (constante).

Em seguida, tente e determine isso para o número de chamadas recursivas . Nesse caso, temos n-1 chamadas recursivas.

Portanto, o desempenho das chamadas recursivas é: O (n-1) (a ordem é n, pois jogamos fora as partes insignificantes).

Em seguida, junte os dois e você terá o desempenho para toda a função recursiva:

1 * (n-1) = O (n)

Peter , para responder às suas questões levantadas; o método que descrevo aqui realmente lida com isso muito bem. Mas lembre-se de que isso ainda é uma aproximação e não uma resposta matematicamente correta. O método descrito aqui também é um dos métodos que aprendemos na universidade e, se bem me lembro, foi usado para algoritmos muito mais avançados do que o fatorial que usei neste exemplo.
É claro que tudo depende de quão bem você pode estimar o tempo de execução do corpo da função e o número de chamadas recursivas, mas isso é verdade para os outros métodos.


ótima pergunta!

Isenção de responsabilidade: esta resposta contém declarações falsas, veja os comentários abaixo.

Se você estiver usando o Big O, estará falando do pior caso (mais sobre o que isso significa mais tarde). Além disso, há teta capital para o caso médio e um grande ômega para o melhor caso.

Confira este site para uma adorável definição formal de Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f (n) = O (g (n)) significa que existem constantes positivas c e k, de modo que 0 ≤ f (n) ≤ cg (n) para todos os n ≥ k. Os valores de c e k devem ser fixos para a função f e não devem depender de n.

Ok, agora o que queremos dizer com complexidades de "melhor ou pior"?

Isto é provavelmente mais claramente ilustrado através de exemplos. Por exemplo, se estivermos usando a pesquisa linear para encontrar um número em uma matriz classificada, o pior caso é quando decidimos procurar o último elemento da matriz, pois isso levaria tantas etapas quanto os itens da matriz. O melhor caso seria quando procurarmos o primeiro elemento, uma vez que concluiríamos após a primeira verificação.

O objetivo de todas essas complexidades de adjetivo- case é que estamos procurando uma maneira de representar graficamente a quantidade de tempo que um programa hipotético é executado em termos de tamanho de variáveis ​​específicas. No entanto, para muitos algoritmos, você pode argumentar que não há um tempo único para um tamanho específico de entrada. Observe que isso contradiz o requisito fundamental de uma função, qualquer entrada não deve ter mais que uma saída. Então, criamos várias funções para descrever a complexidade de um algoritmo. Agora, mesmo que a busca em uma matriz de tamanho n possa levar uma quantidade variável de tempo, dependendo do que você está procurando na matriz e dependendo proporcionalmente a n, podemos criar uma descrição informativa do algoritmo usando o melhor caso, o caso médio e classes de pior caso.

Desculpe, isso é tão mal escrito e falta muita informação técnica. Mas espero que isso facilite a reflexão sobre as classes de complexidade de tempo. Depois de se familiarizar com isso, torna-se uma simples questão de analisar seu programa e procurar itens como forops, que dependem do tamanho da matriz e do raciocínio com base nas estruturas de dados, que tipo de entrada resultaria em casos triviais e que entrada resultaria nos piores casos.


Eu não sei como resolver isso programaticamente, mas a primeira coisa que as pessoas fazem é que amostremos o algoritmo para certos padrões no número de operações realizadas, digamos 4n ^ 2 + 2n + 1, temos 2 regras:

  1. Se tivermos uma soma de termos, o termo com a maior taxa de crescimento é mantido, com outros termos omitidos.
  2. Se temos um produto de vários fatores, fatores constantes são omitidos.

Se simplificarmos f (x), onde f (x) é a fórmula para o número de operações realizadas (4n ^ 2 + 2n + 1 explicado acima), obteremos o valor de O grande [O (n ^ 2) neste caso]. Mas isso teria que explicar a interpolação de Lagrange no programa, que pode ser difícil de implementar. E se o valor real de O grande fosse O (2 ^ n), e pudéssemos ter algo como O (x ^ n), então esse algoritmo provavelmente não seria programável. Mas se alguém me provar errado, me dê o código. . . .


Além de usar o método master (ou uma de suas especializações), eu testo meus algoritmos experimentalmente. Isso não pode provar que uma classe de complexidade específica seja alcançada, mas pode garantir que a análise matemática é apropriada. Para ajudar com essa garantia, uso ferramentas de cobertura de código em conjunto com meus experimentos, para garantir que estou exercitando todos os casos.

Como um exemplo muito simples, diga que você queria fazer uma verificação de integridade na velocidade da classificação da lista do .NET Framework. Você pode escrever algo como o seguinte e analisar os resultados no Excel para garantir que eles não excedam uma curva n * log (n).

Neste exemplo, medo o número de comparações, mas também é prudente examinar o tempo real necessário para cada tamanho de amostra. No entanto, você deve ter ainda mais cuidado ao medir o algoritmo e não incluir artefatos da sua infraestrutura de teste.

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

O que geralmente é esquecido é o comportamento esperado dos seus algoritmos. Ele não altera o Big-O do seu algoritmo , mas está relacionado à declaração "otimização prematura ..."

O comportamento esperado do seu algoritmo é - muito confuso - com que rapidez você pode esperar que seu algoritmo trabalhe com dados que provavelmente verá.

Por exemplo, se você está procurando um valor em uma lista, é O (n), mas se você sabe que a maioria das listas que você vê tem seu valor antecipadamente, o comportamento típico do seu algoritmo é mais rápido.

Para realmente defini-lo, você precisa ser capaz de descrever a distribuição de probabilidade do seu "espaço de entrada" (se precisar classificar uma lista, com que frequência essa lista já será classificada? Com ​​que frequência é totalmente revertida? Como geralmente é classificada principalmente?) Nem sempre é possível que você saiba disso, mas às vezes sabe.


Para o código A, o loop externo será executado por n+1tempos, o tempo '1' significa o processo que verifica se eu ainda atende ao requisito. E loop interno executa ntempos, n-2tempos .... Assim 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²),.

Para o código B, embora o loop interno não interaja e execute foo (), o loop interno será executado por n vezes, dependendo do tempo de execução do loop externo, que é O (n)





performance