O que é Big O notação? Você usá-lo? [duplicado]

StackOverflow https://stackoverflow.com/questions/133008

Foi útil?

Solução

Uma coisa importante a maioria das pessoas esquece quando se fala de Big-O, assim, eu sinto a necessidade de mencionar que:

Você não pode usar Big-O para comparar o velocidade de dois algoritmos. Big-O diz apenas quanto mais lento um algoritmo terá (aproximadamente) se você dobrar o número de itens processados, ou quanto mais rápido ele vai ficar se você reduzir o número pela metade.

No entanto, se você tem dois algoritmos completamente diferentes e um (A) é O(n^2) eo outro (B) é O(log n), não é dito que A é mais lento do que B. Na verdade, com 100 itens, A pode ser dez vezes mais rápido do que B. Diz apenas que, com 200 itens, A vai crescer mais lento pelo fator n^2 e B vai crescer mais lento pelo fator log n. Então, se você referência tanto e você sabe o quanto A tempo leva para processar 100 itens, e quanto tempo B necessidades para os mesmos 100 itens, e A é mais rápido que B, você pode calcular o que quantidade de itens B vai ultrapassar A na velocidade (como a velocidade da B diminui muito mais lento que o de A, ele vai ultrapassar A mais cedo ou mais tarde, isso é com certeza).

Outras dicas

Big O notação denota o fator limitante de um algoritmo. É uma expressão simplificada de como o tempo de execução de um algoritmo escalas com relação à entrada.

Por exemplo (em Java): 

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

Agora, pense sobre o que este está realmente fazendo. Ela está passando por todos os caracteres de entrada e adicioná-los juntos. Isso parece simples. O problema é que String é imutável . Assim, cada vez que você adicionar uma carta para a string que você tem que criar uma nova seqüência. Para fazer isso você tem que copiar os valores da string antiga para a nova string e adicione o novo personagem.

Isto significa que você irá copiar a primeira letra n vezes em que n é o número de caracteres na entrada. Você será copiar os tempos caráter n-1, assim, no total, serão cópias (n-1)(n/2).

Esta é (n^2-n)/2 e para a Big O notação usamos apenas o maior fator de magnitude (geralmente) e soltar quaisquer constantes que são multiplicados por ele e vamos acabar com O(n^2).

Usando algo como um StringBuilder será ao longo das linhas de O (NLog (n)). Se você calcular o número de caracteres no início e definir a capacidade do StringBuilder você pode obtê-lo para ser O(n).

Então, se tivéssemos 1000 caracteres de entrada, o primeiro exemplo iria realizar aproximadamente um milhão de operações, StringBuilder iria realizar 10.000, ea StringBuilder com setCapacity iria realizar 1000 operações para fazer a mesma coisa. Esta é estimativa grosseira, mas a notação O(n) é sobre ordens de magnitudes, não exata de tempo de execução.

Não é algo que eu uso por dizer em uma base regular. É, no entanto, constantemente no fundo da minha mente quando se tenta descobrir o melhor algoritmo para fazer alguma coisa.

Uma questão muito semelhante já foi solicitado em Big-O para Eight Year Olds? . Esperemos que as respostas não irá responder à sua pergunta, embora o consulente pergunta lá tinha um pouco de conhecimento matemático sobre tudo o que você pode não ter tão esclarecer se você precisa de uma explicação mais completa.

Todo o programador deve estar ciente de que Big O notação é, como ele se aplica em acções com estruturas comuns de dados e algoritmos (e, portanto, escolher os DS corretas e algoritmo para o problema que eles estão resolvendo), e como calculá-lo para a sua próprios algoritmos.

1) É uma ordem de medição da eficiência de um algoritmo quando se trabalha sobre uma estrutura de dados.

2) Ações como 'adicionar' / 'tipo' / 'Remover' pode assumir diferentes quantidades de tempo com diferentes estruturas de dados (e algoritmos), por exemplo, 'add' e 'encontrar' são O (1) para uma hashmap , mas O (log n) para uma árvore binária. Ordenar é O (nlog n) para QuickSort, mas o (n ^ 2) para BubbleSort, quando se lida com uma matriz simples.

3) Os cálculos pode ser feito por olhar para a profundidade de loop do seu algoritmo geral. Nenhuma laçadas, O (1), loops iteração sobre todo o conjunto (mesmo que eles quebram em algum ponto) O (n). Se o circuito divide o espaço de busca em cada iteração? O (N log N). Tire o maior O () para uma seqüência de loops, e multiplicar o O () quando você laços ninho.

Sim, é mais complexo do que isso. Se você estiver realmente interessado obtenha um livro de texto.

notação 'Big-O' é usado para comparar as taxas de crescimento das duas funções de uma variável (digamos n) como n fica muito grande. Se a função f cresce muito mais rapidamente do que a função g dizemos que g = O (f) dar a entender que para n grande o suficiente, f sempre ser maior do que g até um fator de escala.

Acontece que esta é uma idéia muito útil em ciência da computação e, particularmente, na análise de algoritmos, porque muitas vezes são precisamente preocupados com as taxas de crescimento das funções que representam, por exemplo, o tempo levado por dois algoritmos diferentes. Muito grosseira, pode-se determinar que um algoritmo com t1 de tempo de execução (n) é mais eficiente do que um algoritmo com t2 de tempo de execução (n) se t1 = O (t2) para n suficientemente grande, que é tipicamente o 'tamanho' do o problema -. como o comprimento da matriz ou o número de nós no gráfico ou qualquer

Esta disposição, que n se torna grande o suficiente, nos permite puxar um monte de truques úteis. Talvez o mais frequentemente utilizado é que você pode simplificar funções até os seus termos de crescimento mais rápido. Por exemplo n ^ 2 + n = O (n ^ 2) porque, como n se torna grande o suficiente, o termo n ^ 2 recebe muito maior do que n que o termo n é praticamente insignificante. Assim, podemos soltá-lo da consideração.

No entanto, isso não significa que a notação big-O é menos útil para pequenas n, porque os termos mais lento de crescimento que temos esquecido ainda são bastante significativos para afetar o tempo de execução.

O que temos agora é uma ferramenta para comparar os custos de dois algoritmos diferentes, e um atalho para dizer que um é mais rápido ou mais lento do que o outro. notação Big-O pode ser abusado que é uma pena, pois é imprecisa já chega! Há condições equivalentes, para dizer que uma função cresce menos rapidamente do que o outro, e que duas funções crescer no mesmo ritmo.

Oh, e posso usá-lo? Sim, o tempo todo - quando eu estou tentando descobrir o quão eficiente o meu código é que ele dá um grande 'aproximação back-of-the-de envelope para o custo.

O "Intuitition" por trás Big-O

Imagine uma "competição" entre duas funções ao longo x, como x se aproxima do infinito:. F (x) eg (x)

Agora, se de algum ponto da (alguns x) uma função sempre tem um valor maior que o outro, então vamos chamar essa função "mais rápido" do que o outro.

Assim, por exemplo, se para todo x> 100 você vê que f (x)> g (x), então f (x) é "mais rápido" do que g (x).

Neste caso, diríamos g (x) = O (f (x)). f (x) representa uma espécie de "limite de velocidade" das sortes para g (x), uma vez que, eventualmente, ele passa-lo e deixa-lo para trás para sempre.

Este não é exatamente a definição de big-O notação , que também afirma que f (x) só tem de ser maior do que C * g (x) para alguma constante C (que é apenas outra maneira de dizer que você não pode ajudar g (x) vencer a competição pela multiplicação por um factor constante - f (x) será sempre vencer no final). A definição formal também utiliza valores absolutos. Mas eu espero que eu consegui fazê-lo intuitiva.

Ele também pode valer a pena considerar que a complexidade de muitos algoritmos é baseado em mais de uma variável, particularmente em problemas multidimensionais. Por exemplo, recentemente tive que escrever um algoritmo para o seguinte. Dado um conjunto de n pontos, e m polígonos, extrair todos os pontos que se encontram em qualquer um dos polígonos. A complexidade é baseado em torno de duas variáveis ??conhecidas, n e m, e do desconhecido de quantos pontos estão em cada polígono. A notação grande ó aqui é um pouco mais complexo do que O (f (n)) ou mesmo O (f (n) + G (m)). Big O é bom quando você está lidando com um grande número de itens homogêneos, mas não espere que este seja sempre o caso.

Também é importante notar que o número real de iterações sobre os dados é muitas vezes dependente de dados. Quicksort é geralmente rápida, mas dar-lhe pré-classificados de dados e ele diminui. Meus pontos e polígonos alogorithm acabou muito rápido, perto de O (n + (log m (m)), com base no conhecimento prévio de como os dados era susceptível de ser organizado e os tamanhos relativos dos n e m. Seria cair mal em dados de diferentes tamanhos relativos organizada aleatoriamente.

A última coisa a considerar é que muitas vezes há um comércio direto off entre a velocidade de um algoritmo e a quantidade de espaço que ele usa. Pombo buraco classificação é um exemplo muito bom disso. Voltando aos meus pontos e polígonos, vamos dizer que todos os meus polígonos eram simples e rápido para desenhar, e eu poderia atraí-los preenchidos na tela, digamos, em azul, em um determinado período de tempo cada. Então, se eu tirar minhas m polígonos em uma tela preta que levaria tempo O (m). Para verificar se algum dos meus n pontos estava em um polígono, eu simplesmente verificar se o pixel em que ponto é verde ou preto. Assim, a verificação é O (n), e a análise total é O (m + n). Desvantagem, claro, é que eu preciso perto de armazenamento infinito se eu estou lidando com coordenadas reais para precisão milimétrica .... ... hum ho.

Ele também pode valer a pena considerar amortizado tempo, ao invés de apenas pior caso. Isso significa, por exemplo, que se você executar o algoritmo n vezes, será O (1) , em média, mas pode ser pior, às vezes.

Um bom exemplo é uma tabela dinâmica, que é basicamente uma matriz que se expande à medida que você adiciona elementos a ele. A implementação ingênua seria aumentar o tamanho da matriz em 1 para cada elemento adicionado, o que significa que todos os elementos precisam ser copiados cada vez que um novo é adicionado. Isso resultaria em um O (n 2 ) algoritmo se você estava concatenando uma série de matrizes usando esse método. Uma alternativa é dobrar a capacidade da matriz cada vez que você precisar de mais armazenamento. Mesmo que acrescentar é uma O (n) operação às vezes, você só precisa copiar O (n) elementos para cada n elementos adicionados, assim que a operação é o (1) , em média. Isto é como as coisas como StringBuilder ou std :: vector são implementadas.

O que é Big O notação?

Big O notação é um método de expressar a relação entre muitos passos de um algoritmo exigirá relacionados com o tamanho dos dados de entrada. Isto é referido como a complexidade algorítmica. Por exemplo a triagem de uma lista de tamanho N usando bolha Ordenar leva O (n ^ 2) passos.

faço para usar o Big O notação?

Eu uso Big O notação na ocasião para transmitir a complexidade algorítmica de colegas programadores. Eu uso a teoria subjacente (por exemplo, técnicas de análise de Big S) o tempo todo quando eu penso sobre o que algoritmos para uso.

exemplos concretos?

Eu tenho usado a teoria da análise de complexidade para criar algoritmos para estruturas de dados pilha eficientes que não necessitam de realocação de memória e que suportam tempo médio de O (N) para a indexação. Eu tenho usado Big O notação para explicar o algoritmo para outras pessoas. Também utilizado análise complexidade de compreender, quando o tempo de triagem ó linear (N) é possível.

De Wikipedia .....

Big O notação é útil ao analisar algoritmos para a eficiência. Por exemplo, o tempo (ou o número de passos) que leva para completar um problema de tamanho n pode ser encontrado para ser T (n) = 4n² -. 2n + 2

Como n cresce grande, o termo n² virá a dominar, de modo que todos os outros termos podem ser negligenciadas - por exemplo, quando n = 500, o termo 4n² é 1000 vezes maior do que o termo 2N. Ignorando este último teria efeito negligenciável sobre o valor da expressão para a maioria dos propósitos.

Obviamente eu nunca tê-lo usado ..

Você deve ser capaz de avaliar a complexidade de um algoritmo. Isto combinado com o conhecimento de quantos elementos levará pode ajudá-lo a determinar se ele é mal adequado para a sua tarefa.

Ele diz quantas iterações de um algoritmo tem no pior caso.

para procurar um item em uma lista, você pode percorrer a lista até que você tem o item. No pior dos casos, o item está em último lugar.

Vamos dizer que existem n itens na lista. Na pior das hipóteses você levar n iterações. No Big O notiation é O (n).

Ele diz factualy quão eficiente um algoritmo é.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top