algorithm - 在算法复杂度分析中考虑大上限

Question

我在考虑算法的复杂性分析，然后想到了这个例子:有一个医疗中心有几个医生；每个医生可以在一周的每个工作日的一个小时时段内访问。现在，假设我们有一组医生，并且每个医生都有一个已排序的预定就诊集合，如果我们想查找某个特定时段是否有任何医生空闲，我们可以编写一个非常基本的算法来执行此操作:

for (Doctor doc: doctors) {
    for (Visit visit: doc.visits) {
        if (visit.hour == hour && visit.day == day) {
            return false;
        }
        if (visit.day > day) {
            break;
        }
    }
}
return true;

虽然我知道这不是解决问题的最有效方法，但我想知道它的时间复杂度；一开始我想到了 O(n^2) 的时间复杂度，因为医生和访问的数量会增加，代码包含两个嵌套循环，内部循环包含几个常量时间操作。

不过转念一想，医生的数量肯定是有一个上限的，就是中心国的人口数(如果连外国医生都算进去，还是有上限的，世界人口~ 75 亿)；所以时间复杂度似乎降低到线性 O(n)，因为内部循环只执行恒定次数。用大 O 术语来说:O(C*N) = O(n)，其中 C 是常量上限。

不满意，我还以为这个软件不会在医疗中心运行一个多世纪，因为我敢肯定在那段时间里它会被重写；所以该软件将只接受到 2117 年的访问，即 - 假设每年 230 个工作日，每天 8 个时段，184k 个时段，再次是上限。如果你认为软件可以持续一个多世纪，那么上界就变成了太阳的预期生命周期(大约50亿年)，之后地球上的生命就会消失。更高的上限，但仍然是上限。所以时间复杂度现在看起来是 O(1)，因为 O(C1*C2) = O(1)，其中 C1 是医生上限，C2 是访问上限。

这个推理正确吗？通常在分析算法复杂性时将大数假设为常量是否正确？

Answer 1

如果每个医生都有相同数量的visits ，也就是说，如果下面的循环

for (Visit visit: doc.visits)

总是运行固定次数，那么运行十亿次或者运行10、20次都无所谓。只要是常量，时间复杂度永远是O(n)，是线性的

Reason 是 Big O 的定义:

f(n) = O(g(n))当我们有 f(n) <= cg(n) , 对于所有 n > n'对于一些常量 c .因此，只要内循环运行一定的时间，比如 1000000 次。我们有f(n) = 1000000n我们得到:

f(n) = 1000000n <= 1000001n, for all n > 0 and c = 1000001

我们得到 f(n) = O(n)。