что такое полиномиальное время{объясните на простом языке для новичка}?

Answer 1

полином - многочлен.

если время работы алгоритма можно выразить размера входных данных как многочлен - это называется полиномиальным временем. А заодно полиномиальным называется случай, когда время можно оценить сверху степенной функцией.

например, простое перемножение матриц размером n*n требует С*n^3 операций, где С - некоторая константа. Учитывая, что размер входных данных при этом n^2, трудоемкость получается С*n^1. 5. Строго говоря, n^1, 5 - не полином, но когда говорят о трудоемкости это считается полиномиальной трудоемкостью, потому, как лежит между n^1 и n^2