algorithm - 您如何计算具有硬限制的函数的大 O？

Question

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

Big O 展示了时间如何根据缩放 n 增加，但是随着 n 缩放，一旦它到达模式的重置，它花费的时间重置回来也为低值。我的想法是，当 k+1 重置时，它是 O(nlogn % k)。另一种想法是，由于它有一个硬性限制，因此该值为 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)。

Answer 1

它是 O(1)，您可以从大 O 的 definition 中推导出它.如果 f(x) 是您解决方案的复杂性，则:

与

以及任何 M > 470040(它是 nlogn for n = 31336)和 x > 0。这从定义中暗示: