Existem algumas ferramentas que podem determinar executar análise de código para o Big-O complexidade?

Question

Eu não vi nada lá fora, e eu suspeito que a dificuldade com a definição de "n" uma vez que para em geral para analisar uma função complexa que haveria mais do que apenas uma ou duas variáveis ??para definir.

Existem ferramentas de análise para a complexidade ciclomática, mas existem aqueles para o tempo (e / ou espaço) complexidade? Se assim for quais, se não, por que não? É inviável? Impossível? Alguém só não chegou ao redor dele?

O ideal seria algo como complexidade global para a aplicação (que define diferentes possíveis "n" s), bem como para cada método no aplicativo

Edit: Então, parece que uma solução exata é impossível por causa da Travar Problema no entanto, é algum tipo de aproximação heurística possível? Sei que para efeitos práticos, um bom profiler vai lhe dar informações muito mais útil, mas parece que um problema interessante.

Além disso, como sobre aquele que calcula para um determinado subconjunto de programas?

Answer 1

Infelizmente não é esse problema chamado o problema Travar ...

Answer 2

Não, isso não é possível, devido ao problema da parada.

Se você gostaria de fazer isso para melhorar seus aplicativos, você pode considerar a criação de perfis em seu lugar. Isso permitiria que você a pin-point que está realmente tomando a maior parte do tempo. Desta forma, você não gastar tempo otimizando a O (n ^ 3) algoritmo que só roda em pequenos conjuntos de dados.

Answer 3

Alguns thoughs:

computadores reais são aproximadamente determinísticos máquinas de estados finitos, por isso o problema da parada não é realmente uma limitação prática. A limitação prática é um algoritmo que leva mais tempo para executar do que você se sentir como espera, descartando quaisquer métodos de força bruta de análise.

Para ter uma idéia da complexidade de um algoritmo, você sempre pode executá-lo em um conjunto de entradas aleatórias e medir o tempo necessário. Em seguida, traçar uma curva através dos dados.

Analisando a complexidade de tempo de algoritmos pode ser bastante complicado, exigindo alguns passos criativos. (Ver, por exemplo análise de quick). O problema está relacionado intimamente a prova de teoremas lógicos e verificação do programa. Pode ser possível construir uma ferramenta útil que permite a solução semi-automática de complexidade, ou seja, uma ferramenta que procura sistematicamente soluções dadas dicas de um ser humano, mas certamente não é fácil.

Answer 4

Nunca vi uma ferramenta para fazer isso, mas nós utilizamos de perfil ferramentas para ter uma idéia melhor quais são os gargalos. Nem sempre é óbvio e eu fui surpreendido algumas vezes por coisas que eu pensei que levou muito tempo realmente tomar muito pouco e vice-versa. No mundo da NET, eu usei ANTS eo < a href = "http://www.jetbrains.com/profiler/" rel = "nofollow"> noreferrer JetBrains ferramentas.