Será que quis aplicar a teoria da complexidade computacional na vida real?

Question

Estou fazendo um curso de complexidade computacional e, até agora, tinha a impressão de que ele não vai ser de muita ajuda para um desenvolvedor.

Eu posso estar errado, mas se você ter ido por esse caminho antes, você poderia fornecer um exemplo de como a teoria da complexidade que você ajudou no seu trabalho? Toneladas de graças.

Answer 1

O (1): código simples sem alças. Apenas flui. Pesquisas em uma tabela de pesquisa são O (1), também.

O (log (n)): algoritmos optimizados de forma eficiente. Exemplo: algoritmos de árvore binária e busca binária. que geralmente não machucar. Você tem sorte se você tem tal algoritmo em questão.

O (n): um único circuito através de dados. Dói muito grande n.

O (n * log (n)): um algoritmo que faz algum tipo de divisão e estratégia de conquistar. Os danos para n grande. Exemplo típico: merge sort

O (n * n): um ciclo aninhado de algum tipo. Os danos do mesmo com n pequeno. Comum com os cálculos de matrizes ingênuos. Você quer evitar este tipo de algoritmo, se puder.

O (n ^ x para x> 2): um mau construção com múltiplos laços aninhados. Os danos por muito pequena n.

O (x ^ n, n e pior!): Bizarro (e muitas vezes recursiva) algoritmos você não quer ter no código de produção, excepto em casos muito controladas, por muito pequena n e se há realmente nenhuma alternativa melhor é . tempo de computação podem explodir com n = n + 1.

Movendo o seu algoritmo para baixo de uma classe de complexidade mais elevada pode fazer o seu algoritmo de mosca. Pense de transformação de Fourier, que tem um O (n * n) algoritmo que era inutilizável com hardware 1960, excepto em casos raros. Então Cooley e Tukey fez algumas reduções de complexidade inteligentes por re-utilizando valores já calculados. Isso levou à introdução generalizada de FFT em processamento de sinais. E, no final, é também por isso que Steve Jobs fez uma fortuna com o iPod.

Um exemplo simples: programadores C Naive escrever esse tipo de loop:

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

Isso é um O (n * n) algoritmo por causa da implementação de strlen (). Nidificação Loops conduz à multiplicação de complexidade dentro do grande-O. O (n) no interior do (n) dá o (n * n). O (n ^ 3) no interior do (n) dá o (n ^ 4). No exemplo, pré-cálculo do comprimento da cadeia irá imediatamente voltar o laço em O (n). Joel também tem escrito sobre isso.

No entanto, a classe de complexidade não é tudo. Você tem que manter um olho sobre o tamanho do n. Retrabalhar um O (n * log (n)) algoritmo para O (n) não vai ajudar se o número de instruções (agora lineares) cresce massivamente devido à reformulação. E se n for pequeno de qualquer maneira, otimizando não vai dar muito bang, também.

Answer 2

Embora seja verdade que se pode obter muito longe no desenvolvimento de software sem a menor compreensão da complexidade algorítmica. Eu acho que eu usar meu conhecimento da complexidade o tempo todo; no entanto, neste momento é muitas vezes sem perceber. As duas coisas que aprender sobre a complexidade lhe dá como desenvolvedor de software são uma maneira de comparar algoritmos não semelhantes que fazem a mesma coisa (algoritmos de classificação são o exemplo clássico, mas a maioria das pessoas realmente não escrever suas próprias sortes). A coisa mais útil que lhe dá uma maneira de descrever rapidamente um algoritmo.

Por exemplo, considere SQL. SQL é usado todos os dias por um grande número de programadores. Se você fosse para ver a seguinte consulta, sua compreensão da consulta é muito diferente se você já estudou complexidade.

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

Se você estudou a complexidade, então você entenderia se alguém disse que era O (n ^ 2) para um determinado DBMS. Sem a teoria da complexidade, a pessoa teria que explicar sobre varreduras de tabela e tal. Se somarmos um índice para a tabela Order

CREATE INDEX ORDER_USERID ON Order(UserId)

Em seguida, a consulta acima poderia ser O (n log n), que faria uma enorme diferença para um grande banco de dados, mas para um pequeno, não é nada em tudo.

Pode-se argumentar que a teoria da complexidade não é necessário entender como bancos de dados trabalhar, e eles seria correto, mas a teoria da complexidade dá uma linguagem para pensar sobre e falar sobre algoritmos que trabalham com dados.

Answer 3

Para a maioria dos tipos de programação de trabalho a parte teórica e as provas não pode ser útil em si, mas o que eles estão fazendo é tentar dar-lhe a intuição de ser capaz de dizer imediatamente "este algoritmo é O (n ^ 2), de modo não podemos executá-lo sobre estes um milhão de pontos de dados". Mesmo no processamento mais elementar de grandes quantidades de dados que você estará correndo para isso.

Pensando rapidamente a teoria da complexidade tem sido importante para mim no processamento de dados de negócios, GIS, gráficos de programação e algoritmos de compreensão em geral. É uma das lições mais úteis que você pode começar a partir de estudos CS em comparação com o que você geralmente auto-estudo de outra forma.

Answer 4

Os computadores não são inteligentes, eles vão fazer o que você instruí-los a fazer. Compiladores podem otimizar o código um pouco para você, mas eles não podem otimizar algoritmos. cérebro humano funciona de forma diferente e é por isso que você precisa entender o Big O. Considere calcular números de Fibonacci. Todos nós sabemos F (n) = F (n-1) + F (n-2), e começando com 1,1 você pode facilmente calcular seguintes números sem muito esforço, em tempo linear. Mas se você disser computador para calculá-lo com essa fórmula (de forma recursiva), não seria linear (pelo menos, em linguagens imperativas). De alguma forma, nosso cérebro algoritmo otimizado, mas compilador não pode fazer isso. Então, você tem que trabalho na algoritmo para torná-lo melhor.

E, em seguida, você precisa de treinamento, para detectar otimizações do cérebro que parecem tão óbvio, para ver quando o código pode ser ineficaz, conhecer os padrões de algoritmos maus e bons (em termos de complexidade computacional) e assim por diante. Basicamente, esses cursos servem várias coisas:

• entender os padrões executoras e estruturas de dados e qual o efeito que eles têm sobre o tempo que seus programa precisa de acabamento;
• treinar sua mente para detectar potenciais problemas no algoritmo, quando poderia ser ineficiente em grandes conjuntos de dados. Ou entender os resultados de profiling;
• aprender maneiras bem conhecidas para melhorar os algoritmos reduzindo sua complexidade computacional;
• prepare-se para passar uma entrevista na empresa legal:)

Answer 5

É extremamente importante. Se você não entender como estimar e descobrir quanto tempo os seus algoritmos terá que correr, então você vai acabar escrevendo algum código bastante lento. Eu penso sobre a complexidade compuational o tempo todo quando escrevendo algoritmos. É algo que deve ser sempre em sua mente durante a programação.

Isto é especialmente verdadeiro em muitos casos, porque enquanto seu aplicativo pode funcionar bem no seu computador desktop com um pequeno conjunto de dados de teste, é importante entender o quão rápido seu aplicativo irá responder uma vez que você ir viver com ele, e há centenas de milhares de pessoas se.

Answer 6

Sim, eu freqüentemente usam a notação Big-O, ou melhor, eu uso os processos de pensamento por trás dele, e não a própria notação. Em grande parte porque tão poucos desenvolvedores na organização (s) I freqüente compreendê-lo. Eu não quero ser desrespeitoso com as pessoas, mas na minha experiência, o conhecimento dessas coisas é uma daquelas coisas que "ordena os homens dos meninos".

Gostaria de saber se esta é uma daquelas perguntas que só podem receber respostas "sim"? Parece-me que o conjunto de pessoas que entendem a complexidade computacional é aproximadamente equivalente ao conjunto de pessoas que pensam que é importante. Assim, qualquer pessoa que pode responder que não, talvez, não entende a questão e, portanto, seria pule para a próxima pergunta ao invés de pausa para responder. Apenas um pensamento; -)

Answer 7

Existem pontos no tempo quando você vai enfrentar problemas que exigem pensando sobre eles. Há muitos problemas do mundo real que exigem manipulação da grande conjunto de dados ...

Os exemplos são:

• aplicativo Mapas ... como o Google Maps - como você iria processar o mundial de dados linha de estrada e atraí-los? e você precisa levá-los rápido!
• Aplicação de Logística ... acho viajando homem de vendas em esteróides
• A mineração de dados ... todas as grandes empresas requer um, como é que você mina de um banco de dados contendo 100 mesas e 10m + linhas e chegar a um resultado útil antes das tendências ficar desatualizado?

Tomar um curso de complexidade computacional irá ajudá-lo na análise e escolher / criar algoritmos que são eficientes para tais cenários.

Acredite em mim, algo tão simples como a redução de um coeficiente, digamos, de T (3n) até T (2 N) pode fazer uma diferença enorme quando o "n" é medido em dias ou mesmo meses.

Answer 8

Há muitos bons conselhos aqui, e tenho certeza que a maioria dos programadores têm usado seus conhecimentos complexidade de vez em quando.

No entanto devo dizer complexidade computacional entendimento é de extrema importância no campo de jogos! Sim, você ouviu, que o material "inútil" é o tipo de vida programação de jogos coisas por diante.

Eu aposto muito poucos profissionais provavelmente se preocupam com o Big-O, tanto quanto os programadores de jogos.

Answer 9

Eu uso cálculos complexidade regularmente, em grande parte porque eu trabalho no domínio geoespacial com grandes conjuntos de dados, por exemplo, processos envolvendo milhões e, ocasionalmente bilhões de coordenadas cartesianas. Uma vez que você começar a bater problemas multidimensionais, a complexidade pode ser um problema real, como algoritmos gananciosos que seria O (n) em uma dimensão de repente hop ao O (n ^ 3) em três dimensões e que não tem muitos dados para criar um gargalo sério. Como mencionei no um post semelhante , você também vê grande O notação tornando-se complicado quando você começar a lidar com grupos de objetos complexos de tamanho variável. A ordem de complexidade também pode ser muito dependente dos dados, com casos típicos desempenho muito melhor do que os casos gerais de bem desenhado ad hoc algoritmos.

Também vale a pena testar seus algoritmos sob um profiler para ver se o que você tem projetado é o que você conseguiu. Acho que a maioria dos gargalos são resolvidos muito melhor com o algoritmo de ajuste de velocidade do processador melhorado para todas as razões óbvias.

Para mais leitura em algoritmos gerais e suas complexidades achei Sedgewicks trabalho tanto informativo e acessível. Para algoritmos espaciais, O'Rourkes livro sobre geometria computacional é excelente.

Answer 10

Em sua vida normal, não perto de um computador, você deve aplicar os conceitos de complexidade e processamento paralelo. Isso permitirá que você a ser mais eficiente. coerência de cache. Esse tipo de coisa.

Answer 11

Sim, o meu conhecimento de algoritmos de ordenação veio a calhar um dia, quando eu tinha de classificar uma pilha de exames do estudante. I ordenar merge (mas não quicksort ou heapsort). Durante a programação, eu só empregar quaisquer triagem de rotina as ofertas da biblioteca. (Não tive a sorte realmente grande quantidade de dados ainda.)

Eu faço teoria da complexidade uso na programação o tempo todo, principalmente em decidir quais estruturas de dados para uso, mas também no momento de decidir se ou quando para resolver as coisas, e para muitas outras decisões.

Answer 12

' Sim ' e ' não '

Sim ) Eu freqüentemente usar a notação O grande quando desenvolvimento e implementação de algoritmos. Por exemplo. quando você deve lidar com 10 ^ 3 itens e à complexidade do primeiro algoritmo é O (n log (n)) e do segundo O (n ^ 3), você pode simplesmente dizer que primeiro algoritmo é quase em tempo real, enquanto o segundo requerem cálculos consideráveis.

Às vezes conhecimentos sobre NP complexidades aulas podem ser úteis. Ele pode ajudá-lo a perceber que você pode parar de pensar em inventar algoritmo eficiente quando algum problema NP-completo pode ser reduzido para o problema que você está pensando.

não ) O que eu descrevi acima é uma pequena parte da teoria complexidades. Como resultado, é difícil dizer que eu usá-lo, eu uso minor-menor parte dela.

Eu deveria admitir que há muitos projeto de desenvolvimento de software que não toque algoritmo de desenvolvimento ou uso deles de forma sofisticada. Em tais casos, a teoria da complexidade é inútil. Os usuários comuns de algoritmos freqüentemente operam utilizando palavras 'rápido' e 'lento', 'x segundos' etc.

Answer 13

@ Martin:? Você pode por favor elaborar sobre os processos de pensamento por trás dele

pode não ser tão explícito como sentar e trabalhar para fora a notação Big-O para uma solução, mas ele cria uma consciência do problema - e que orienta você em direção à procura de uma resposta mais eficiente e longe de problemas nas abordagens que você pode tomar. por exemplo. O (N * N) versus algo mais rápido, por exemplo, busca de palavras armazenadas em uma lista contra armazenado em um trie (exemplo inventado)

Eu acho que isso faz a diferença com o que as estruturas de dados que vou escolher para usar, e como eu vou trabalhar em um grande número de registros.

Answer 14

Um bom exemplo pode ser quando seu chefe lhe diz para fazer algum programa e você pode demonstrar, usando a teoria da complexidade computacional que o que seu chefe está pedindo que você faça não é possível.