与输入算法复杂度是固定大小 [英] Algorithm complexity with input is fix-sized

问题描述

我发现的是大O符号一定的参考，但据我可以理解算法复杂度是输入数据的大小的功能。

I found some references about big O notation, but as far as I can understand algorithm complexity is a function of size of input data.

例如，如果泡沫的复杂性排序是为O（n ^ 2）， N 的大小输入数组。对吧？

For example, if complexity of bubble sort is O(n^2), n is the size of input array. Right?

但是，我怎么能确定的算法，它有固定的投入规模和取决于输入值的复杂性。例如，寻找最大公约数（GCD）是这样的：

But, how can I determinate complexity of algorithm that has fixed input size and depends of values of input. For example, finding Greatest Common Divisor (GCD) would look like this:

def GCD(x, y):
    while x != y:
        if x < y:
            x, y = y - x, x
        else:
            x, y = x - y, x
    return x

这是什么算法的复杂性？它是怎样确定的？

What is complexity of this algorithm? And how is it determined?

编辑：函数变更名称和算法的修正名称。 ShreevatsaR，谢谢指点出来。

Changed name of the function and corrected name of algorithm. ShreevatsaR, thanks for pointing it out.

推荐答案

人打了一下朝三暮四大O符号。在GCD的情况下，他们一般做2种方式：

People play a bit fast and loose with big-O notation. In the case of GCD, they generally do it in 2 ways:

1）你是对的，算法的复杂性，因此，大O记法，应在在位输入的大小，而不是输入的值方面来表述。这就是磷，NP，等等进行定义。假设二进制输入和任意-大量（如BIGNUM重新presentation）和N-输入的比特的数目，您的GCD需要至多2 ^ N减法，其中每一个需要时间为O（N）的运行过号码的每个数字被减去。因此，它是O（N * 2 ^ N）。当然GCD可以做到更快，如果你用除法，而不是减法：O（N ^ 2）

1) You're right, algorithmic complexity, and hence big-O notation, should be stated in terms of the size in bits of the input, not in terms of the values of the input. That's how P, NP, and so on are defined. Assuming binary input and arbitrarily-large numbers (like a BigNum representation), and N the number of bits of input, your GCD requires at most 2^N subtractions, each of which requires time O(N) to run over each digit of the numbers being subtracted. So it's O(N*2^N). GCD can of course be done much faster if you use division rather than subtraction: O(N^2).

所以，当我们说测试素性证明于2002年在多项式时间内完成，这就是技术定义复杂性，我们的意思多项式的位数（这是棘手的部分），而不是多项式在输入号码本身（这是很轻松做子线性时间使用审判庭）。

So, when we say that testing primality was proved in 2002 to be done in polynomial time, that's the technical definition of complexity, and we mean polynomial in the number of digits (which is the tricky part), not polynomial in the input number itself (which is trivially easy to do in "sub-linear time" using trial division).

但在实践中，为此采取的整数输入一个固定数的算法，这是更方便谈论复杂性，就好像Ñ分别输入本身，而不是输入的大小。这不，只要你清楚你的案件的意思，可能是不明确的危害。

But in practice, for algorithms which take a fixed number of integer inputs, it's more convenient to talk about complexity as though N were the input itself, not the size of the input. It's not harmful as long as you're clear what you mean in cases that might be ambiguous.

2）在实践中，整数输入常常固定大小，32位或什么，并在其上​​操作，例如加法，乘法和除法是O（1）时间。我们在为了分析选择使用这些事实。从技术上讲，如果你的GCD计划只接受输入最多（2 ^ 32-1），那么它是O（1）。它具有固定的上限在其运行时间。结束分析。

2) In practice, integer inputs are often fixed-size, 32 bit or whatever, and operations on them such as addition, multiplication and division are O(1) time. We use these facts selectively in our order analysis. Technically if your GCD program only accepts inputs up to (2^32-1), then it is O(1). It has a fixed upper bound on its running time. End of analysis.

虽然技术上是正确的，这不是一个非常有用的分析。几乎所有的东西你做一个真正的电脑上是O（1）在同一基础上，这个问题的大小是由硬件的限制。

Although technically correct that's not a very useful analysis. Almost anything you do on a real computer is O(1) on the same basis, that the size of the problem is constrained by the hardware.

它通常是更方便地接受，除了为O（1），因为数字是固定大小的，但忽略了GCD也是O（1），pretend，它的范围是[1,2行为^ 32）延伸到无穷远，并分析它的基础上。然后，用N的两个输入端的最大值，它出来O（N）：O（N）的增减，每次服用一定时间

It's usually more convenient to accept that addition is O(1) because the numbers are fixed-size, but ignore that GCD is also O(1), pretend that its behaviour in the range [1, 2^32) extends to infinity, and analyse it on that basis. Then with N the max of the two inputs, it comes out O(N): O(N) subtractions, each taking constant time.

同样，这一点也不含糊，一旦你知道什么样的职权范围，但要小心填错比较第一分析我给Euclid算法与分裂，O（N ^ 2），对这种分析的算法减法， 上）。 N不是在每个相同的，并且是减法的不的快; - ）

Again, this is not ambiguous once you know what the terms of reference are, but beware of incorrectly comparing the first analysis I gave of Euclid's algorithm with division, O(N^2), against this analysis of the algorithm with subtraction, O(N). N is not the same in each, and subtraction is not faster ;-)

这篇关于与输入算法复杂度是固定大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！