考虑算法复杂性分析中的大上限

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(。用big-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 times都无关紧要。只要它是恒定的数字，时间复杂度始终是 o(n(，即线性

原因是大o 的定义：

f(n) = O(g(n))当我们使用f(n) <= cg(n)时，对于所有n > n'，对于常数c。因此，只要内部循环在恒定的时间内运行，例如 1000000 times。我们有f(n) = 1000000n，我们得到：

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

我们得到 f(n(= o(n(。