algorithm - i 以变量(不是 1 或 0)开始的 for 循环的时间复杂度

Question

我想知道 for 循环 for(i=m;i<=n;i++) 的时间复杂度，其中 m 和 n 都是变量。我认为它将是 O(n-m)，因为循环取决于 m 和 n 的值。 请指导我!

Answer 1

解释

假设您的循环只执行以恒定时间运行的语句，即 O(1)，您只需计算循环迭代次数即可。

你的循环头

 for (i = m; i <= n; i++)

将生成 i 为 m、m + 1、m + 2、 的迭代m + 3, ... , n - 2, n - 1, n。所以从 m 到 n，两端都包括在内。

正是 n - m + 1 次迭代(简单示例 2、3、4、5 和 5 - 2 + 1 = 4)。

因此，渐近时间复杂度为

O(n - m + 1) = O(n - m)

就像你说的。