不同范围嵌套for循环的时间复杂度

Question

我正在课程中学习时间复杂度，我想澄清以下代码的时间复杂度：

for i in range(0,n):
        for j in range(0,n-2):
             //code in constant time

我知道大小为 n 的嵌套 for 循环的时间复杂度是 n^2。上述循环的时间复杂度也是n^2吗？

Answer 1

是的，上面代码的时间复杂度也将是 O(n^2)，因为第一个循环范围从 0 到 n，因此给出“n”，但我认为您很难理解 n^2 作为内部循环是如何进行的范围是 n-2 但首先要理解它背后的数学，如果我们看到 n*(n-2) 它会给我们 n^2 - 2n 在这个多项式中我们看到表达式的最高幂是 n^2，所以只是为了找到时间复杂性（尤其是最坏的情况）我们采用多项式的最高次数，并忽略具有该最高次数的任何系数。

例如：让我们再举一个例子来帮助您理解，如果形成一些复杂的多项式，例如 5n^3 - 3n^2 + 4^n，那么简单的 TC（时间复杂度）就是 O(n^3)，这是最坏情况的 TC。

希望这可以帮助您更好地理解主题。