algorithm - 如何查找算法是否需要伪多项式时间？

Question

给定一个问题，我尝试解决它并假设我已经找到了一个算法。现在我对该算法进行时间复杂度分析，发现它在多项式时间内运行。现在我如何确保我的算法只在多项式时间内运行而不是在伪多项式时间内运行？

或者我可以这样提出我的问题

有什么方法可以判断一个算法是否需要伪多项式时间？

例如:

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

我们认为上述解决方案在多项式时间内有效，但实际上该解决方案具有伪多项式复杂度。

Answer 1

Given a question, I try to solve it and assume that I have found an algorithm.

假设。

Now I do Time Complexity analysis for that algorithm and find that it runs in polynomial time.

关于什么的多项式时间？输入的数值或该值编码的长度？

Now How can I make sure that my algorithm runs only in polynomial time and not pseudopolynomial time?

如果运行时间受输入编码长度的多项式函数限制，则算法在多项式时间内运行。当输入被解释为数字时，如果其运行时间受输入值的多项式函数的限制，则它是伪多项式的。

Or simply I can put up my question like this: Is there any way to find if an algorithm takes pseudo polynomial time ?

请注意您是否在计算复杂度 w.r.t。输入的值或输入在计算机上的表示的长度(计算机是真实的物理计算机还是概念计算机并不重要)。 p>

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

We think that the above solution works in polynomial time but actually this solution has pesudo polynomial complexity.

此函数的运行时间受限于 n 的多项式函数和输入编码长度的指数函数。

确定答案的关键是意识到当输入为 n 时，输入 size 为 log_2(n)(在计算机上将数字表示为二进制)。