如何在具有硬限制的函数上计算大O? [英] How do you calculate big O on a function with a hard limit?

问题描述

作为我最近看到的编程任务的一部分，要求学生找出解决难题的功能的O值.我很无聊，决定自己编写程序.但是，我的解决方案使用了我在问题中看到的模式来跳过大部分计算.

As part of a programming assignment I saw recently, students were asked to find the big O value of their function for solving a puzzle. I was bored, and decided to write the program myself. However, my solution uses a pattern I saw in the problem to skip large portions of the calculations.

大O显示了时间如何根据缩放比例n增加，但是随着n缩放比例，一旦达到图案的重置，重置所花费的时间也将恢复为较低的值.我的想法是，当k+1重置时，它是O(nlogn % k).另一个想法是，由于它具有硬限制，因此值为O(1)，因为该值是任何常数的大O.是这些权利之一，如果没有，应该如何限制?

Big O shows how the time increases based on a scaling n, but as n scales, once it reaches the resetting of the pattern, the time it takes resets back to low values as well. My thought was that it was O(nlogn % k) when k+1 is when it resets. Another thought is that as it has a hard limit, the value is O(1), since that is big O of any constant. Is one of those right, and if not, how should the limit be represented?

作为重置的示例，k值为31336. 在n = 31336处需要31336步，但在n = 31337处需要1.

As an example of the reset, the k value is 31336. At n=31336, it takes 31336 steps but at n=31337, it takes 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)复杂度的标准合并排序.

MergeSort is a standard merge sort with O(nlogn) complexity.

推荐答案

它是O(1)，您可以从大O的定义.如果f(x)是您解决方案的复杂性，则:

It's O(1) and you can derive this from big O's definition. If f(x) is the complexity of your solution, then:

与

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

and with any M > 470040 (it's nlogn for n = 31336) and x > 0. And this implies from the definition that:

这篇关于如何在具有硬限制的函数上计算大O?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！