O que é O (…) e como faço para calcular?

Socorro! Eu tenho uma pergunta em que preciso analisar o Big-O de um algoritmo ou algum código.

• Não tenho certeza exatamente o que é Big-O ou como ele se relaciona com Big-Theta ou outros meios de analisar a complexidade de um algoritmo.

• Não tenho certeza se Big-O se refere ao tempo para executar o código ou à quantidade de memória necessária (trocas de espaço / tempo).

• Eu tenho o dever de casa da Ciência da Computação, onde preciso fazer alguns loops, talvez um algoritmo recursivo, e criar o Big-O para isso.

• Estou trabalhando em um programa em que tenho uma escolha entre duas estruturas de dados ou algoritmos com um Big-O conhecido e não tenho certeza qual escolher.

Como entendo como calcular e aplicar o Big-O ao meu programa, lição de casa ou conhecimento geral de Ciência da Computação?

Nota: esta pergunta é um alvo canônico para outras questões do Big-O, conforme determinado pela comunidade . É intencionalmente amplo ser capaz de conter uma grande quantidade de informações úteis para muitas perguntas importantes. Por favor, não use o fato de ser tão amplo como uma indicação de que perguntas semelhantes são aceitáveis.

O (...) refere-se à notação Big-O, que é uma maneira simples de descrever quantas operações um algoritmo leva para fazer alguma coisa. Isso é conhecido como complexidade de tempo .

Na notação Big-O, o custo de um algoritmo é representado por sua operação mais cara em grandes números. Se um algoritmo executasse etapas, ele seria representado O (n ³ ). Um algoritmo que contasse cada item de uma lista operaria em O (n) tempo, chamado tempo linear.n3 + n2 + n

Para obter uma lista dos nomes e exemplos clássicos na Wikipedia: Ordens de funções comuns

Material relacionado:

• Explicação em inglês simples de Big O (SO)
• Existe um sistema por trás da magia da análise de algoritmos? (CS.SE)
• Um guia para iniciantes da notação Big O
• Algoritmos: Design e Análise

Quais são as funções assintóticas? O que é uma assíntota, afinal?

Dada uma função f (n) que descreve a quantidade de recursos (tempo de CPU, RAM, espaço em disco etc.) consumidos por um algoritmo quando aplicados a uma entrada de tamanho n , definimos até três notações assintóticas para descrever seu desempenho para grande n .

Uma assíntota (ou função assintótica) é simplesmente alguma outra função (ou relação) g (n) que f (n) se aproxima cada vez mais à medida que n cresce cada vez mais, mas nunca alcança. A vantagem de falar sobre funções assintóticas é que elas geralmente são muito mais simples de se falar, mesmo que a expressão para f (n) seja extremamente complicada. As funções assintóticas são usadas como parte das notações delimitadoras que restringem f (n) acima ou abaixo.

(Nota: no sentido empregado aqui, as funções assintóticas estão próximas da função original depois de corrigir algum fator constante diferente de zero, pois todas as três grandes notações O / Θ / dis desconsideram esses fatores constantes de sua consideração.)

Quais são as três notações delimitadoras assintóticas e como elas são diferentes?

Todas as três notações são usadas assim:

f (n) = O (g (n))

onde f (n) aqui é a função de interesse eg (n) é outra função assintótica com a qual você está tentando aproximar f (n) . Isso não deve ser tomado como uma igualdade em um sentido rigoroso, mas uma declaração formal entre a rapidez com que f (n) cresce em relação a n em comparação com g (n) , quando n se torna grande. Os puristas costumam usar a notação alternativa f (n) ∈ O (g (n)) para enfatizar que o símbolo O (g (n)) é realmente uma família inteira de funções que compartilham uma taxa de crescimento comum.

A notação Big-ϴ (Theta) estabelece uma igualdade no crescimento de f (n) até um fator constante (mais sobre isso mais adiante). Comporta-se de maneira semelhante a um =operador para taxas de crescimento.

A notação Big-O descreve um limite superior no crescimento de f (n) . Comporta-se de maneira semelhante a um ≤operador para taxas de crescimento.

A notação Big-Ω (Omega) descreve um limite inferior em um crescimento de f (n) . Comporta-se de maneira semelhante a um ≥operador para taxas de crescimento.

Existem muitas outras notações assintóticas , mas elas não ocorrem com tanta frequência na literatura de ciência da computação.

As notações Big-O e seus tipos costumam ser uma maneira de comparar a complexidade do tempo .

O que é complexidade de tempo?

Complexidade temporal é um termo sofisticado para a quantidade de tempo T (n) que um algoritmo leva para executar em função do tamanho de entrada n . Isso pode ser medido na quantidade de tempo real (por exemplo, segundos), no número de instruções da CPU, etc. Geralmente, supõe-se que o algoritmo seja executado no seu computador cotidiano da arquitetura von Neumann . Mas é claro que você pode usar a complexidade do tempo para falar sobre sistemas de computação mais exóticos, onde as coisas podem ser diferentes!

Também é comum falar sobre complexidade de espaço usando a notação Big-O. Complexidade de espaço é a quantidade de memória (armazenamento) necessária para concluir o algoritmo, que pode ser RAM, disco, etc.

Pode ser que um algoritmo seja mais lento, mas use menos memória, enquanto outro seja mais rápido, mas use mais memória. Cada um pode ser mais apropriado em diferentes circunstâncias, se os recursos forem limitados de maneira diferente. Por exemplo, um processador incorporado pode ter memória limitada e favorecer o algoritmo mais lento, enquanto um servidor em um datacenter pode ter uma grande quantidade de memória e favorecer o algoritmo mais rápido.

Calculando Big-ϴ

Calcular o Big-ϴ de um algoritmo é um tópico que pode preencher um pequeno livro ou aproximadamente meio semestre da turma de graduação: esta seção abordará o básico.

Dada uma função f (n) no pseudocódigo:

int f(n) {
  int x = 0;
  for (int i = 1 to n) {
    for (int j = 1 to n) {
      ++x;
    }
  }
  return x;
}

Qual é a complexidade do tempo?

O loop externo é executado n vezes. Para cada vez que o loop externo é executado, o loop interno é executado n vezes. Isso coloca o tempo de execução em T (n) = n ² .

Considere uma segunda função:

int g(n) {
  int x = 0;
  for (int k = 1 to 2) {
    for (int i = 1 to n) {
      for (int j = 1 to n) {
        ++x;
      }
    }
  }
  return x;
}

O loop externo é executado duas vezes. O loop do meio é executado n vezes. Para cada vez que o loop do meio é executado, o loop interno é executado n vezes. Isso coloca o tempo de execução em T (n) = 2n ² .

Agora, a pergunta é: qual é o tempo de execução assintótico de ambas as funções?

Para calcular isso, realizamos duas etapas:

• Remova as constantes. À medida que os algoritmos aumentam no tempo devido a entradas, os outros termos dominam o tempo de execução, tornando-os sem importância.
• Remova todos, exceto o maior termo. À medida que n vai para o infinito, n ² ultrapassa rapidamente n .

A chave aqui é o foco nos termos dominantes e simplifica esses termos .

T (n) = n ² ϴ ϴ (n ² )
T (n) = 2n ² ∈ ϴ (n ² )

Se tivermos outro algoritmo com vários termos, o simplificaremos usando as mesmas regras:

T (n) = 2n ² + 4n + 7 ϴ ϴ (n ² )

A chave de todos esses algoritmos é que nos concentramos nos maiores termos e removemos constantes . Não estamos analisando o tempo de execução real, mas a complexidade relativa .

Calculando Big-Ω e Big-O

Primeiro, lembre-se de que, na literatura informal , “Big-O” é frequentemente tratado como sinônimo de Big-Θ, talvez porque as letras gregas sejam difíceis de digitar. Portanto, se alguém inesperadamente pede o Big-O de um algoritmo, eles provavelmente quer o Big-Θ.

Agora, se você realmente deseja calcular Big-Ω e Big-O nos sentidos formais definidos anteriormente, você tem um grande problema: existem infinitas descrições de Big-Ω e Big-O para qualquer função! É como perguntar quais são os números menores ou iguais a 42. Existem muitos possibilidades.

Para um algoritmo com T (n) ∈ n (n ² ) , qualquer uma das seguintes são formalmente válidas a serem feitas:

• T (n) ∈ O (n ² )
• T (n) ∈ O (n ³ )
• T (n) ∈ O (n ⁵ )
• T (n) ∈ O (n ¹²³⁴⁵ × e ⁿ )
• T (n) ∈ n (n ² )
• T (n) ∈ Ω (n)
• T (n) ∈ Ω (log (n))
• T (n) ∈ Ω (log (log (n)))
• T (n) ∈ Ω (1)

Mas é incorreto indicar T (n) ∈ O (n) ou T (n) ∈ Ω (n ³ ) .

O que é complexidade relativa? Quais classes de algoritmos existem?

Se compararmos dois algoritmos diferentes, sua complexidade conforme a entrada chega ao infinito normalmente aumentará. Se observarmos diferentes tipos de algoritmos, eles podem permanecer relativamente iguais (digamos, diferindo por um fator constante) ou podem divergir bastante. Esta é a razão para executar a análise Big-O: para determinar se um algoritmo executará razoavelmente com entradas grandes.

As classes de algoritmos são divididas da seguinte maneira:

• Constant (1) - constante. Por exemplo, escolher o primeiro número em uma lista sempre levará a mesma quantidade de tempo.

• Θ (n) - linear. Por exemplo, a iteração de uma lista sempre levará um tempo proporcional ao tamanho da lista, n .

• Log (log (n)) - logarítmico (a base normalmente não importa). Algoritmos que dividem o espaço de entrada em cada etapa, como pesquisa binária, são exemplos.

• Θ (n × log (n)) - tempos lineares logarítmicos (“linearítmicos”). Esses algoritmos geralmente dividem e conquistam ( log (n) ) enquanto ainda iteram ( n ) todas as entradas. Muitos algoritmos de classificação populares (classificação por mesclagem, Timsort) se enquadram nessa categoria.

• Θ (n ^m ) - polinômio ( n elevado a qualquer constante m ). Essa é uma classe de complexidade muito comum, frequentemente encontrada em loops aninhados.

• Θ (m ⁿ ) - exponencial (qualquer constante m aumentada para n ). Muitos algoritmos recursivos e gráficos se enquadram nessa categoria.

• Θ (n!) - fatorial. Certos algoritmos gráficos e combinatórios são de complexidade fatorial.

Isso tem algo a ver com o melhor / médio / pior caso?

Não. O Big-O e sua família de notações falam sobre uma função matemática específica . Eles são ferramentas matemáticas empregadas para ajudar a caracterizar a eficiência dos algoritmos, mas a noção de melhor / média / pior caso não tem relação com a teoria das taxas de crescimento descrita aqui.

Para falar sobre o Big-O de um algoritmo, é preciso se comprometer com um modelo matemático específico de um algoritmo com exatamente um parâmetro n, que deve descrever o "tamanho" da entrada, em qualquer sentido que seja útil. Mas no mundo real, os insumos têm muito mais estrutura do que apenas seus comprimentos. Se este era um algoritmo de ordenação, eu poderia alimentar nas cordas "abcdef", "fedcba"ou "dbafce". Todos eles têm comprimento 6, mas um deles já está classificado, um está invertido e o último é apenas uma confusão aleatória. Alguns algoritmos de classificação (como o Timsort) funcionam melhor se a entrada já estiver classificada. Mas como incorporar essa não homogeneidade em um modelo matemático?

A abordagem típica é simplesmente assumir que a entrada vem de alguma distribuição aleatória e probabilística. Em seguida, você calcula a média da complexidade do algoritmo em todas as entradas com comprimento n. Isso fornece um modelo de complexidade de caso médio do algoritmo. A partir daqui, você pode usar as notações Big-O / Θ / as como de costume para descrever o comportamento médio dos casos.

Mas se você estiver preocupado com ataques de negação de serviço, poderá ser mais pessimista. Nesse caso, é mais seguro supor que as únicas entradas são aquelas que causam mais sofrimento ao seu algoritmo. Isso fornece um modelo de complexidade do pior caso do algoritmo. Depois, você pode falar sobre Big-O / Θ / Ω etc. do modelo de pior caso .

Da mesma forma, você também pode focar seu interesse exclusivamente nas entradas com as quais seu algoritmo tem menos problemas para chegar a um modelo de melhor caso , depois olhar para Big-O / Θ / Ω etc.