O que é O em Big O?

Bem, meu palpite seria a ordem, que coincide com a wikipedia .

Editar: (minha própria (quaisquer melhorias apreciadas)) tradução do artigo da wikipedia em alemão

A letra maiúscula O (na verdade um omicron maiúsculo na época) como um símbolo para a ordem de (alemão: “Ordnung von”) foi usada pela primeira vez por o teórico dos números alemão Paul Bachman na segunda edição de seu livro sobre a teoria analítica dos números apareceu em 1894. A notação ganhou popularidade devido ao trabalho de Edmund Landau, outro teórico dos números alemão, a quem essa nomenclatura é amplamente associada hoje, especialmente no Terminologia alemã.

Comentários

• Embora possa ser o caso de muitos matemáticos se referirem como tal, originalmente não era assim. Se você leu os livros de teoria dos números do início do século 20, não encontrará essa explicação. É o que é e eu não posso ‘ ler alemão para descobrir o que ele pensava sobre a notação.
• @Jonathan: Post atualizado.
• Muito bom! Procurei em todos os meus livros de teoria dos números e não consegui ‘ encontrar uma explicação para o O em lugar nenhum. +1
• Eu ‘ sempre pronunciei como ordem de , já que apenas dizer O não significa muito.
• Muito informativo! mas ainda assim – por que O pronunciado como ‘ oh ‘ por programadores?

“Grande” significa “maiúsculo” e “O” significa ordem, como em “ordem de complexidade”. Assim denominado devido à convenção de escrever “ordem de complexidade” como O (f (x)), por exemplo, com uma letra maiúscula “O” ou um “Grande O”. Ninguém fala muito sobre isso porque “todos” entendem o que significa, e entendê-lo realmente não ajuda a entender a análise de complexidade.

Para uma compreensão da análise de complexidade, acho que o link postado por topgun_ivard é um bom lugar para começar. Um bom livro introdutório cobrindo estruturas de dados ou algoritmos também pode ajudar.

Comentários

• I ‘ sinto muito, mas a notação de Bachmann-Landau foi inventada por um matemático alemão, então acho que ele dificilmente a teria nomeado após uma palavra em inglês. Na verdade, mesmo que tivesse sido inventada por um matemático americano, provavelmente ainda teria o nome de uma palavra alemã, porque quando foi inventado (por volta de 1920, eu acho), a linguagem internacional da matemática era o alemão. Além disso, não ‘ nem mesmo remotamente tem algo a ver com complexidade.
• @J ö rg: Sim, mas não ‘ que seja apenas Ordnung , que o artigo wiki alemão afirma ser a origem: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
• @Ethel você poderia fazer uma pequena alteração em seu artigo para que eu pudesse votar em você? Você está realmente correto. Você tem que editar antes que eu possa votar.
• @Jonathan, eu ‘ m não tenho certeza exatamente qual pequena alteração você deseja. Você pode simplesmente prosseguir e fazer a edição desejada? Ou poderíamos apenas deixar back2dos ‘ suporte de resposta, parece que ele pode ter terminado com a melhor resposta de qualquer maneira devido a uma excelente pesquisa 🙂
• Hm , interessante. Na Suécia, Big Oh é geralmente chamado de ” ordo ” (latim para, bem, ordem) em vez de ” ordning ” (a palavra sueca para ordem).

O significa ordem.

Foi originalmente introduzido pelo matemático alemão Paul Bachmann no o segundo volume de seus livros sobre teoria dos números Die Analytische Zahlentheorie , publicado em 1894 (p. 401) . Ele observa, após uma fórmula onde ele primeiro usa a notação:

(…) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung em Bezug auf n die Ordnung von n nicht überschreitet (…)

Minha tradução:

(…) onde com a notação O (n) nós indicar uma magnitude cuja ordem com referência a n não exceda a ordem de n (…)

Em contraste com o que outros disseram, nada em seu texto indica que este é de fato um omikron maiúsculo grego. Ele usa muitos caracteres gregos e latinos, então não há realmente como saber. Dado seu uso contínuo de “Ordnung n log n ” etc. no texto, está claro que significa “Ordnung” (alemão para “ordem”, se houver alguma dúvida) em qualquer caso, mas isso ainda poderia deixar em aberto o uso de um extravagante O grego.

No entanto, a origem do omikron é mais provavelmente um retrônimo devido a Donald Knuth, que introduziu os símbolos ômega (Ω) e teta (Θ) para conceitos relacionados em seu artigo Big Omicron e Big Omega e Big Theta , ou possivelmente Hardy e Littlewood que introduziram um símbolo ômega anteriormente.

Comentários

• Interessante. Suponho que esteja certo. Acabei de pesquisar as definições nos livros de Landau ‘ se Bachmann ‘ s, e eles de fato a) usam um latim Oh, não um Omikron grego, b) ambos usam a palavra ” Ordnung ” e c) Landau explicitamente afirma que significa ” Ordnung “. Estou corrigido.
• Que palavra melhor poderia ser encontrada? Quer dizer, de um alemão? Ordnung ist das halbe Leben!
• Acho que a primeira frase da sua resposta (correta, votada, incrível) deveria ser: ‘ O significa ” Ordnung ” (alemão significa ” Pedido “) . ‘ Esta resposta ajudaria a chamar a atenção de outros leitores.

Gosto deste artigo , espero que você também o considere útil!

Citando uma seção do artigo:
letras gregas grandes

O grande O é freqüentemente mal utilizado. Big O ou Big Oh é, na verdade, abreviação de Big Omicron. Ele representa o limite superior da complexidade assintótica. Portanto, se um algoritmo é O (n log n), existe uma constante c tal que o limite superior é cn log n.

Θ (n log n) (Big Theta) é mais fortemente limitado do que isso. Tal algoritmo significa que existem duas constantes c1 e c2 tais que c1n log n < f (n) < c2n log n.

Ω (n log n) (Big Omega) diz que o algoritmo tem um limite inferior de cn log n.

Existem outros, mas estes são os mais comuns e Big O é o mais comum de todos. Essa distinção normalmente não é importante, mas vale a pena notar. Afinal, a notação correta é a notação correta.

O que é Big O?

A notação Big O busca descrever a complexidade relativa de um algoritmo reduzindo a taxa de crescimento para a chave fatores quando o fator chave tende para o infinito. Por esta razão, você ouvirá frequentemente a frase complexidade assintótica. Ao fazer isso, todos os outros fatores são ignorados. É uma representação relativa da complexidade.

O que não é Big O?

Big O não é um teste de desempenho de um algoritmo. Também é nocional ou abstrato, pois tende a ignorar outros fatores. A complexidade do algoritmo de classificação é normalmente reduzida ao número de elementos sendo classificados como sendo o fator principal. Isso é bom, mas não leva em consideração questões como:

Uso da memória: um algoritmo pode usar muito mais memória do que outro. Dependendo da situação, isso pode ser qualquer coisa de completamente irrelevante a crítico; Custo de comparação: pode ser que comparar elementos seja realmente caro, o que pode alterar qualquer comparação no mundo real entre algoritmos; Custo de mover elementos: copiar elementos normalmente é barato, mas não é necessariamente o caso; etc.

Comentários

• Simplesmente vincular um artigo não é ‘ muito útil. É ‘ geralmente uma boa ideia parafrasear ou citar a seção que você considera especialmente relevante para o tópico.
• Os votos negativos são realmente necessários? O artigo que ele vinculou é muito relevante e o IMHO muito útil.Enquanto isso, a resposta mais votada é um link para um artigo da Wikipedia. +1 para compensar a hipocrisia da mente-colmeia.
• -1, porque o artigo, embora seja um artigo muito bom e bem escrito, não ‘ não tenho nada a ver com a pergunta.
• @Jorg, eu nunca disse que o artigo resolveria o problema, mas compartilhei porque o achei útil quando estava examinando esses conceitos.
• @topgun_ivard: Então, o que acontece se ele se tornar um link morto? A paráfrase permite 1) que o público deste tópico obtenha uma versão das notas do Coles do seu link (tempo é dinheiro) e 2) garante que sua postagem não seja tornada irrelevante em um link inativo.

EDITAR: Acontece que estou errado. No entanto, talvez isso ajude alguém a manter seus símbolos corretos, então não vou excluí-los.

Na verdade, é não a letra latina Ah, , é a letra grega Omicron . Infelizmente, essas duas têm exatamente o mesmo glifo, então, com o tempo, a versão original foi corrompida e agora é apenas Oh .

A escolha do símbolo não tem nenhum significado particular, ele foi escolhido como um dispositivo mnemônico :

• Omicron tem as letras MICRO e a semântica do símbolo Omicron significa aproximadamente “menor que”
• Omega tem as letras MEGA , e a semântica do símbolo Omega significa aproximadamente “maior que”
• Theta (Θ) parece um pouco com um sinal de igual , e a semântica do símbolo Theta significa aproximadamente “igual a”

É isso. Não há nenhum significado real para isso, é apenas um jogo de palavras, se você vai, para ajudá-lo a lembrar a semântica mais e asily.

Comentários

• Embora eu adorasse acreditar em sua proposição mnemônica (é uma ideia muito legal), vou precisar ver alguma prova de que esta é a real intenção original de Bachmann. Forneça e eu ‘ marcarei com +1 você.
• @Jonathan Henson: Aparentemente, fui enganado pelo Prof. Knuth 🙂

“f (x) é grande-oh de g (x)”

É uma maneira matemática de prever o crescimento de funções.

Sejam feg funções do conjunto de inteiros ou o conjunto ou números reais para o conjunto de números reais. Dizemos que f (x) é O (g (x)) se houver constantes C e k tais que | f (x) | < = C | g (x) | onde quer que x> k.

Você leria isso como “f (x) é grande-oh de g (x)”

O grande-O às vezes é chamado de símbolo de Landau depois o matemático alemão Edmund Landau. Eu não acho que signifique nada além disso. Você também tem as notações big-Omega e big-Theta semelhantes. Os símbolos são tão arbitrários como sempre usando theta para denotar os ângulos em seus triângulos em sua geometria planar do colégio classe.

Correção @ back2dos forneceu uma explicação satisfatória para o O no que se refere ao pedido. Job. Veja a resposta dele.

Donald Knuth aplicou-o para estudar a complexidade dos programas de computador.

Se você quiser descobrir o motivo pelo qual a notação foi usada, você deve ler

“Analytische Zahlentheorie” por Paul Bachmann de 1892

ATUALIZAÇÃO: tentando limpar minha resposta e ser mais preciso

A notação Big O é uma maneira de caracterizar funções de acordo com suas taxas de crescimento. representa ordem (primeira ordem sendo n segunda ordem sendo n-quadrado etc.). E se eu não sou equivocado, esse seria o pior cenário para um tempo de execução (ou armazenamento) de métodos dados N elementos. Quanto maior a ordem, pior é o desempenho do método.
Por exemplo, pesquisar um registro em uma matriz é O (1) (acredito em alguma implementação de tabelas hash que também seja o caso). Adicionar um valor ao final de uma lista de links seria O (N) porque você tem que chegar ao final da lista antes de adicionar o elemento etc.

Esta resposta deve ser um pouco mais correta do que minha primeira tentativa 🙂

Comentários

• -1 porque isso é simplesmente incorreto E respondeu a uma pergunta diferente da que foi feita. A questão era por que a letra ” O ” é usada, não ” como o Big A notação funciona? “. Você ‘ está incorreto sobre como Big-oh funciona tão bem, embora … o loop em uma matriz seja O (n) onde n é o tamanho da matriz, não O (1) . A notação não tem nada a ver com ” ciclos ” de um algoritmo … it ‘ uma medida do limite superior do tempo de execução de um algoritmo.
• Não quero discutir com você aqui, mas ‘ é mais ou menos o que eu quis dizer. O que significa tempo de execução certo?Bem, o tempo de execução é determinado pelo que deve ser processado na máquina. Acho que uso o ciclo liberalmente aqui. Por ciclo, acho que deveria ter dito iterar por completo ou algo parecido. Você está certo sobre o limite superior, porém, ele não determina a média. Portanto, eu aceito o downgrade.