A palavra "eficiente" geralmente se refere ao tempo polinomial ou tempo polilogarítmico?
https://cs.stackexchange.com/questions/122217
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu não sou especialista em CS, mas quase sempre vi a palavra "eficiente" aplicada a um algoritmo para significar "de tempo de execução polinomial". Por exemplo. Esta questão e o artigo da Wikipedia em Teoria da complexidade computacional Use a palavra dessa maneira.
No entanto, outras fontes (por exemplo, os artigos da Wikipedia em nc e p-completo ) Reserve a palavra "eficiente" para algoritmos com runtimes polilogarítmicos e usar "tracial" para algoritmos com runtimes polinomiais.
Esta terminologia conflitante é obviamente confusa. Claro, qualquer discussão formal (boa) da complexidade algorítmica definirá precisamente sua terminologia, mas em geral, são um dos dois usos acima claramente mais convencionais do que a outra? Se alguém usa o termo "eficiente" em uma discussão informal da complexidade computacional sem definir, é mais provável que eles significam "tempo polinomial" ou "tempo polilogarítico"?Solução
Não há uma resposta verdadeira.Depende do contexto.O contexto mais comum é aquele em que o tempo polinomial é considerado mais ou menos sinônimo de eficiente, por isso, se você não tivesse mais contexto, eu certamente acho "tempo polinomial".O tempo polilogármico é usado apenas em contextos muito estreitos.
Em geral, se você acha que seu público pode não ter certeza do significado, então eu recomendo que você defina seus termos.
Outras dicas
talvez esta seja uma referência à tese de Cobham https://en.wikipedia.org / wiki / cobham% 27s_thesis? wprov= sfla1 .Geralmente a palavra usada é "viável" embora.
