给定一个问题，我尝试解决它并假设我已经找到了一个算法。现在，我为该算法进行时间复杂度分析，发现它在多项式时间内运行。现在如何确保我的算法仅在多项式时间内运行，而不是在伪多项式时间内运行？
或者干脆我可以像这样提出我的问题
有没有办法找到算法是否需要伪多项式时间？
例如：
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
我们认为上述解决方案在多项式时间内有效，但实际上该解决方案具有多项式复杂性。
给定一个问题，我尝试解决它并假设我已经找到了一个算法。
假设。
现在，我为该算法进行时间复杂度分析，发现它在多项式时间内运行。
多项式时间相对于什么？输入的数值还是该值编码的长度？
现在如何确保我的算法仅在多项式时间内运行，而不是在伪多项式时间内运行？
如果运行时间由输入编码长度的多项式函数限制，则算法以多项式时间运行。当它被解释为数字时，如果它的运行时间由输入值的多项式函数限制，则它是伪多项式。
或者简单地我可以这样提出我的问题：有没有办法找到算法是否需要伪多项式时间？
请注意您是在计算复杂性，包括输入的值还是输入在计算机上的表示长度(计算机是真正的物理计算机还是概念计算机并不重要(。
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
我们认为上述解决方案在多项式时间内有效，但实际上该解决方案具有多项式复杂性。
此函数的运行时间由n的多项式函数和输入编码长度的指数函数限制。
确定答案的关键是意识到虽然输入是n，但输入大小是log_2(n)(在将数字表示为二进制的计算机上(。