如何查找算法是否花费伪多项式时间？ [英] How to find if an algorithm takes pseudopolynomial time??

问题描述

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

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 ?

例如：

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.

推荐答案

给出一个问题，我尝试解决这个问题并假设我找到了一个算法。

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.

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

Polynomial time with respect to what? The numeric value of the input or the length of that value's encoding?

现在如何确保算法仅在多项式时间内运行而不是伪多项式时间？

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

如果运行时间受编码长度的多项式函数限制，则算法以多项式时间运行输入的如果它的运行时间受输入值的多项式函数限定为数字，则它是伪多项式。

The algorithm runs in polynomial time if the running time is bounded by a polynomial function of the length of the encoding of the input. It is pseudopolynomial if its running time is bounded by a polynomial function of the value of the input when it is interpreted as a number.

或简而言之，我可以这样提出我的问题：是否有任何方法可以找到算法是否需要伪多项式时间？

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

是否计算复杂度输入的值或计算机上输入的表示形式的长度（计算机是真正的物理计算机还是概念计算机都没有关系）。

Be careful about whether you are computing the complexity w.r.t. the value of the input or the length of the input's representation on the computer (whether the computer is a real physical computer or a conceptual computer doesn't matter).

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 的多项式函数限定

The running time of this function is bounded by a polynomial function of n and by an exponential function of the length of the input's encoding.

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

The key to determining the answer is realizing that while the input is n, the input size is log_2(n) (on computers that represent numbers as binary).

这篇关于如何查找算法是否花费伪多项式时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！