2

作为我最近看到的一项编程作业的一部分，学生们被要求找出解决难题的函数的大 O 值。我很无聊，决定自己写程序。但是，我的解决方案使用我在问题中看到的模式来跳过大部分计算。

大 O 显示时间如何根据缩放增加n，但随着n缩放，一旦达到模式的重置，它所花费的时间也会重置回低值。我的想法是它是O(nlogn % k)什么时候k+1重置的。另一个想法是，因为它有一个硬限制，所以值是O(1)，因为这是任何常数的大 O。其中之一是对的，如果不是，应该如何表示限制？

作为复位示例，k值为 31336。在 n=31336 时，需要 31336 步，但在 n=31337 时，需要 1。

代码是：

def Entry(a1, q):
    F = [a1]
    lastnum = a1
    q1 = q % 31336
    rows = (q / 31336)
    for i in range(1, q1):
        lastnum = (lastnum * 31334) % 31337
        F.append(lastnum)

    F = MergeSort(F)
    print lastnum * rows + F.index(lastnum) + 1

MergeSort是具有O(nlogn)复杂性的标准归并排序。

4

3 回答 3

2

嗯，我用来思考大 O 问题的一种简单方法是把 n 想象成这么大，它也可能是无穷大。如果您对非常大的数字上的字节级操作不特别了解（因为 q % 31336 会随着 q 趋于无穷大而扩大，实际上并不是恒定的），那么您的直觉是正确的，它是 O(1)。

想象 q 接近无穷大，您可以看到 q % 31336 显然在 0 和 31335 之间，正如您所指出的。这一事实限制了数组元素的数量，从而将排序时间限制为某个常数（n * log(n) ==> 31335 * log(31335) * C，对于某个常数 C）。所以整个算法的时间是恒定的。

但是，在现实世界中，乘法、除法和取模都根据输入大小进行缩放。如果您有兴趣弄清楚这一点，可以查找 Karatsuba 算法。我会把它留作练习。

于 2013-10-23T23:36:41.687 回答
2

它是O(1)，你可以从大 O 的定义中得出这个。如果f(x)是您的解决方案的复杂性，那么：

等式 2

和

等式 2

和任何M > 470040（它的nlogn）n = 31336和x > 0。这从定义中暗示：

等式 1

于 2013-10-23T23:36:43.363 回答
-2

如果这个问题有几个不同的实例，每个实例都有自己的k值，那么该方法的复杂度不是 O(1)，而是O(k·ln k).

于 2013-10-24T00:13:11.013 回答