运行n-2次的循环的时间复杂度是多少？

Question

我有一个运行n-2时间的循环，这个例子的时间复杂度是多少。

for(int m=1; m<arr.length-1; m++) {

}

我不相信它是O(n)，因为它永远不会运行n次，即使在最坏的情况下也不会。

Answer 1

O(n)的意思是"on of n“。具体来说，定义是，如果存在一些f(n)和c，那么对于所有的n > k，f(n) < c * g(n)，某些函数都是c。在本例中，设置f(n) = n - 2和g(n) = n，您可以看到对于k = 10和c = 2，对于所有n > 10都是n < 2 * (n - 2)，所以n - 2实际上是O(n)。