输入的算法复杂度是固定大小的

Question

我找到了一些关于大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,谢谢你的指出.

Answer 1

人们用大O符号快速松散地玩.就GCD而言,它们通常以两种方式进行:

1)你是对的,算法复杂度,因此大O符号,应该根据输入的位大小来表示,而不是根据输入的值来表示.这就是P,NP等的定义方式.假设二进制输入和任意大数(如BigNum表示)和N输入的位数,您的GCD最多需要2 ^ N个减法,每个减法需要时间O(N)来运行每个数字.数字被减去.所以它是O(N*2 ^ N).如果使用除法而不是减法,GCD当然可以更快地完成:O(N ^ 2).

因此,当我们说2002年在多项式时间内证明测试素性时,这是复杂性的技术定义,我们指的是数字的多项式(这是棘手的部分),而不是输入数字本身的多项式(使用试验分割在"次线性时间"中很容易做到).

但实际上,对于采用固定数量的整数输入的算法,谈论复杂性更方便,就好像N是输入本身,而不是输入的大小.只要你清楚自己在可能含糊不清的情况下的意思,它就没有害处.

2)在实践中,整数输入通常是固定大小,32位或其他,并且对它们的操作(例如加法,乘法和除法)是O(1)时间.我们在订单分析中有选择地使用这些事实.从技术上讲,如果你的GCD程序只接受最多(2 ^ 32-1)的输入,那么它是O(1).它的运行时间有一个固定的上限.分析结束.

虽然技术上正确,但这不是一个非常有用的分析.你在真实计算机上做的几乎任何东西都是O(1)在同一基础上,问题的大小受到硬件的限制.

接受添加为O(1)通常更方便,因为数字是固定大小的,但忽略GCD也是O(1),假设它在[1,2 ^ 32]范围内的行为延伸到无穷大,并在此基础上进行分析.然后,对于两个输入中的最大值,N得出O(N):O(N)次减法,每次减去恒定时间.

一旦你知道参考条款是什么,这一点并不含糊,但要注意错误地将我给出的Euclid算法的第一次分析与除法O(N ^ 2)进行比较,并将此算法与减法算法O分析( N).N不是在每个相同的,并且是减法不更快;-)