Resposta
Um algoritmo é polinomial (tem tempo de execução polinomial) se for algum $ k, C > 0 $, seu tempo de execução nas entradas de tamanho $ n $ é no máximo $ Cn ^ k $. Equivalentemente, um algoritmo é polinomial se para algum $ k > 0 $, seu tempo de execução nas entradas de tamanho $ n $ é $ O (n ^ k) $. Isso inclui linear, quadrático, cúbico e muito mais. Por outro lado, algoritmos com tempos de execução exponencial não são polinomiais.
Existem coisas entre – por exemplo, o algoritmo mais conhecido para fatorar é executado no tempo $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ para alguma constante $ C > 0 $; tal tempo de execução é conhecido como subexponencial . Outros algoritmos podem ser executados em tempo $ O (\ exp (A \ log ^ C n)) $ para algum $ A > 0 $ e $ C > 1 $, e são conhecidos como quase-polinômios . Esse algoritmo foi recentemente reivindicado para registro discreto sobre pequenas características.
Comentários
- Veja também aqui .
- O que são k e C?
- Eles são parâmetros.
- Então algoritmos de tempo constante são considerados polinomiais, correto?
- Algoritmos de tempo constante são um caso especial de algoritmos de tempo polinomial.
Resposta
A execução de um algoritmo pode levar algum tempo de computação. Depende principalmente da complexidade do algoritmo. Os cientistas da computação criaram uma maneira de classificar o algoritmo com base em seu comportamento de quantas operações ele precisa realizar (mais operações levam mais tempo).
Uma dessas classes mostra complexidade de tempo polinomial. Ou seja, a complexidade operacional é proporcional a $ n ^ c $ enquanto n é o tamanho da entrada e c é alguma constante. Obviamente, o nome vem por causa de $ n ^ c $ que é um polinômio .
Existem outros “tipos” de algoritmos que ocupam um tempo constante, independentemente do tamanho da entrada. Alguns ocupam $ 2 ^ n $ tempo (sim, realmente sllloooow na maior parte do tempo).
Eu simplesmente simplifiquei demais para o leigo e posso ter introduzido erros. Portanto, leia mais https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Comentários
- Li no Wolfram que algoritmos de tempo polinomial são considerados " rápidos " . No entanto, ouço muitas pessoas dizerem que preferem algoritmos de tempo logarítmico ou linear em vez de algoritmos de tempo polinomial. Estou entendendo mal o uso da palavra " rápido "?
- Logarítmico e linear também são polinomiais. Acho que ' rápido ' provavelmente significa algo como ' muito mais provável de ser prático para uso real '.
Resposta
Em termos leigos, o tempo de execução do seu algoritmo.
A ordem dos algoritmos (crescimento) pode ser em Big-oh (O), little-oh (o), ômega (Ω) ou theta (Θ).
Se você está tendo problemas para calcular o RR, veja algumas perguntas que fiz antes e vote se você entendeu.
Digamos que você tenha um loop for:
for(i=1 to n) x++ A ordem ou complexidade de tempo desse trecho de código é: O (n)
Por que big-oh? Porque nós queremos o pior caso em que este trecho de código é executado.
Leia aqui (eles definem a complexidade de um algoritmo e informam como os algoritmos são feitos em tempo polinomial):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Resumo:
http://www.multiwingspan.co.uk/a23.php?page=types
Comentários
- Isso não ' responde exatamente à pergunta: tempo polinomial não é " o tempo de execução do seu algoritmo ". Em vez disso, o tempo de execução de um algoritmo pode ser polinomial e assim por diante. Você poderia tornar a resposta melhor tornando-a mais precisa. Por exemplo, realmente precisamos ler três artigos da Wikipedia sobre algo, ou realmente precisamos saber alguma coisa sobre Big Oh?