Complexidade de Algorítimos

QUESTÕES
O que é um problema computável?
É um problema que pode ser resolvido através de algoritmos que não caia em loop infinito, ou seja, tenha um numero finito de ciclos.
Por que é importante a análise da complexidade computacional de um algoritmo?
Pois quanto mais “caro” computacionalmente um algoritmos, este se torna menos eficiente, isso em relação a recursos do computador, portanto, o estudo da analise da complexidade se torna importante para obter um bom desempenho do algoritmos eficientes nas resoluções de problemas.
O que entendemos por tamanho de um problema?
O tamanho de um problema é entendido pelo tamanho da abertura do algoritmo, ou seja, quantidade de variáveis que este algoritmo irá receber.
O que é um problema polinomial (P)?
Um problema polinomial tem solução de complexidade até ordem polinomial.Quais são as funções limitantes superiores mais conhecidas? big-OhDesignação O(1) Constante
O(logn) Logarítmica
O(n) Linear
O(nlogn) nlognO(n²) Quadrática
O(n³) Cúbica
O(n^c), c número real Polinomial
O(c^n), c número real, maior que 1 Exponencial
O(n!) Fatorial
O que é um problema não-deterministicamente polinomial (NP)?
Um problema não-deterministicamente polinomial é um problema computável cujas soluções até então conhecidas são de ordem exponencial e não se sabe se existe uma solução melhor, de complexidade polinomial.O que é um problema NP-completo?
Um problema NP-completo é um problema "representante" de uma classe de problemas NP, de tal sorte que os problemas da classe são redutíveis a ele em tempo polinomial. Por exemplo, o problema de caixeiro-viajante é um poblema redutível ao problema de ciclo hamiltoniano.Dados dois algoritmos A e B para solucionar um problema. O algoritmo A tem complexidade de ordem quadrática (p.ex.,f(N)=N ²) e o algoritmo B, de ordem linear (p.ex.,f(N)=aN;), para todos os tamanhos N do problema. Pode-se concluir que B requer menos tempos de execução do que A para todos os tamanhos N?
Não.