Existe uma lista mestra da notação Big-O para tudo?
-
05-07-2019 - |
Pergunta
Existe uma lista mestra da notação Big-O para tudo? estruturas de dados, algoritmos, operações realizadas em cada, média-caso, pior caso, etc.
Solução
Dicionário de Algoritmos e Estruturas de Dados é uma lista bastante abrangente, e inclui complexidade (Big- o) nas descrições dos algoritmos. Se precisar de mais informações, vai ser em uma das referências ligadas, e há sempre Wikipedia como um fallback.
Outras dicas
O href="https://rads.stackoverflow.com/amzn/click/com/0262032937" rel="nofollow noreferrer"> Cormen livro é mais sobre a ensiná-lo a provar o Big -O seria para um determinado algoritmo, em vez de memorização de algoritmo para o seu desempenho Big-o. O primeiro é muito mais valioso do que o último, e requer um investimento de sua parte.
Tente " Introdução aos Algoritmos " por Cormen, Leisersen e Rivest . Se não é lá o seu provavelmente não vale a pena conhecer.
Em c ++ as normas STL é definida pelas características Big-O dos algoritmos, bem como os requisitos de espaço. Dessa forma, você pode alternar entre implementações de STL competindo e ainda saber que o seu programa tinha as características de execução do mesmo ish. Particularily boas implementações STL poderia listas caso, mesmo especiais de tipos particulares de ser melhor do que os-requisitos normais.
Ela fácil para escolher o iterador ou lista de tipo correto para um problema particular, porque você poderia facilmente pesar entre consumo de espaço e velocidade.
Claro Big-O é apenas uma linha guia como todas as constantes são removidos. Se um algoritmo executado em K * O (n), ele seria classificado como O (n), mas se k é suficientemente elevada que poderia ser pior do que o (n ^ 2) para alguns valores de n e m.
Introdução aos Algoritmos, segunda edição , aka CLRS (Cormen, Leiserson, Rivest, Stein) , é a coisa mais próxima que eu posso pensar.
Se isso não funcionar, então tente The Art of Computer Programming , por Knuth. Se não for naqueles, você provavelmente precisará fazer alguma pesquisa real.
Para qualquer um, que está chegando a esta pergunta de Google.