算法复杂度与输入固定大小

我发现了一些关于大O符号的引用，但据我所知，算法复杂度是输入数据大小的函数。算法复杂度与输入固定大小

例如，如果气泡排序的复杂度为O(n^2),n是输入数组的大小。对？

但是，如何确定具有固定输入大小和取决于输入值的算法的复杂性。例如，找到最大公约数（GCD）将如下所示：

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

该算法的复杂性是什么？它是如何确定的？

编辑：更改函数的名称和更正算法的名称。 ShreevatsaR，谢谢你指出。

来源

2010-01-08 del-boy

请阅读现有的SO问题+关于此主题的答案。 – 2010-01-08 04:43:36

你的代码，BTW，发现**最大的**公约数（gcd），也被称为最高公因数（hcf）。一组分数的“最小公分母”是分母最不常见的**倍数**，这是别的。 [对于两个整数x和y，我们有lcm（x，y）= xy/gcd（x，y）。] – ShreevatsaR 2010-01-08 06:00:49

ShreevatsaR，谢谢，我已经改变了它。英语不是我的母语，所以我不确定它叫什么。 – 2010-01-08 06:35:21

人们用大O符号打得有点快和松散。在GCD的情况下，它们通常以两种方式进行：

1）你说得对，算法的复杂性，因此大O符号应该用的大小来表示的位数，而不是根据输入值。这就是P，NP等等的定义。假设二进制输入和任意大数字（比如BigNum表示），并且N是输入的位数，那么GCD需要最多2^N次减法，每次减法需要时间O（N）运行数字被减去。所以它是O（N * 2^N）。如果使用除法而不是减法，GCD当然可以快得多：O（N^2）。因此，当我们说testing primality was proved in 2002 to be done in polynomial time，这是复杂性的技术定义，我们是指数字中的多项式（这是棘手的部分），而不是输入数字本身的多项式（这很容易做到在“亚线性时间”使用审判分区）。

但实际上，对于采用固定数量的整数输入的算法来说，谈论复杂性更为方便，就好像N是输入本身，而不是输入的大小。只要你清楚你的意思是不明确的话，那就没有害处。 2）实际上，整数输入通常是固定大小的，32位或其他，对它们的操作如加法，乘法和除法都是O（1）时间。我们在订单分析中选择性地使用这些事实。从技术上讲，如果你的GCD程序只接受高达（2^32-1）的输入，那么它就是O（1）。它的运行时间有一个固定的上限。分析结束。

虽然技术上正确，但这不是一个非常有用的分析。几乎你在真实计算机上做的任何事情都是基于O（1），因此问题的大小受到硬件的限制。

由于数字是固定大小，但是忽略GCD也是O（1），假设其行为在[1，2^32]范围内，因此接受加法为O（1）延伸到无穷大，并在此基础上进行分析。然后用N表示两个输入的最大值，得出O（N）：O（N）减法，每个减法都需要不变的时间。

同样，一旦你知道什么是职责范围，这是不含糊的，但要小心将我对欧几里得算法的第一个分析与除法O（N^2）减法，O（N）。 N在每个中不相同，并且减法是而不是更快;-)

来源

2010-01-08 13:33:38

输入尺寸是数字x和y的大小的总和（例如，多少位都在数）

来源

2010-01-08 04:47:34 newacct

这是可能的 - 但在这种情况下极其不可能。如果使用'x'和'y'的大小，则估计的阶数为O（10 ⁿ）。如果你使用'x'和'y'的值，那么估计的阶数是O（n）。 – 2010-01-08 07:08:29

大O复杂性是最糟糕的情况下，渐进的运行时行为。它不一定依赖于特定算法的输入大小（输入量） - 尽管通常是这种情况。换句话说，它是限制函数，用于描述输入无限时的运行时间。

就你而言，如果x或y是无界的，渐近运行时也是如此。如果不是，请考虑运行时间，如果x = 1，并且y = Int32.Max？

来源

2010-01-08 05:19:48 Paul

Big-O表示法应指定正在测量的内容。

例如，用于排序算法的Big-O表示法通常用于衡量比较次数。

您的GCD示例可以比较x和y的值与执行指令的数量。让我们仔细看看：

def GCD(x, y): 
    while x != y:    # 1 
     if x < y:    # 2 
      x, y = y - x, x  # 3 
     else:     # 4 
      x, y = x - y, x  # 5 
    return x     # 6

工作从内到外。

无论x和y的值如何，步骤3和5总是需要一条指令。因此，步骤2的if声明将始终采用两条指令。

难度较大的问题是第1步。每次迭代时，x或y将按较小值降低。假设x > y。其中一个会发生两两件事：

如果它开始是x % y == 0，那么循环将被执行(x/y) - 1时间，程序将停止。
否则，x将减少(x/y)次，然后它会小于y并且程序将继续。

你可以很容易地测量的指令数目对于任何给定x和y。您可以很容易地表明，对于给定数字z，您将永远不需要超过z - 1减法 - 或2 * (z-1)指令。（想想gcd(z, 1)。）

来源

2010-01-08 07:03:34

那么行为'O（max（x，y））'呢？ – 2010-01-08 08:26:35

是的。它是'O（max（x，y））'。 – 2010-01-08 16:19:58

算法复杂度与输入固定大小

回答

相关问题