注册
登录
笔试面试题
什么是伪多项式？
返回
什么是伪多项式？
作者:
春风助手
发布时间:
2023-10-26 04:27:45 (8月前)
<p>种最坏情况下的时间复杂度取决于输入数值（而不是输入数量）的算法称为伪多项式算法。<br>例如，考虑对正数数组中所有元素的频率进行计数的问题。为此，伪多项式时间解决方案是先找到最大值，然后从1迭代到最大值，然后为每个值在数组中找到其频率。此解决方案需要根据输入数组中最大值的时间，因此需要伪多项式。另一方面，时间复杂度仅基于数组中元素的数量（而不是值）的算法被视为多项式时间算法。 </p>
收藏
举报
1 条回复
动动手指，沙发就是你的了！
登录
后才能参与评论
