作为我最近看到的编程作业的一部分，学生们被要求找出解决难题的函数的大 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)。
最佳答案
它是O(1)，您可以从大O的definition中得出它。 。如果 f(x) 是解决方案的复杂度，则:
与
以及任意 M > 470040(n = 31336 的 nlogn)和 x > 0。从定义中这意味着:
关于algorithm - 如何在具有硬限制的函数上计算大 O？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19553958/