嵌套for循环的时间复杂度 [英] Time complexity of nested for-loop

问题描述

我需要计算以下代码的时间复杂度:

for (i = 1; i <= n; i++)
{
  for(j = 1; j <= i; j++)
  {
   // Some code
  }
}

是 O(n ^ 2)吗?

解决方案

是的，嵌套循环是一种快速获得大O表示法的方法.

通常(但并非总是)，一个循环嵌套在另一个循环中会导致O(n²).

考虑一下，对于i的每个值，内循环都会执行i次，. 外循环执行n次.

因此，您将看到如下执行模式: 1 + 2 + 3 + 4 + ... + n次

因此，我们可以说代码执行次数超过n次(下限)来限制代码执行的次数，但是就n而言，我们执行代码多少次?

好吧，在数学上我们可以说它将执行不超过n²次，这给了我们最坏的情况，因此我们的O-n界限为O(n²). (有关如何在数学上讲这一点的更多信息，请参见幂级数)

Big-Oh并不总是准确地衡量要完成的工作量，但通常可以给出最坏情况的可靠估计.

---

4年后修改:，因为该帖子似乎获得了可观的访问量.我想更全面地说明我们如何使用幂级数将执行绑定到O(n²)

从网站上:1 + 2 + 3 + 4 ... + n =(n²+ n)/2 =n²/2 + n/2.那么，如何将其转换为O(n²)?我们(基本上)在说的是n²> =n²/2 + n/2.这是真的?让我们做一些简单的代数.

• 将两侧乘以2得到:2n²> =n²+ n?
• 将2n²扩展为:n²+n²> =n²+ n?
• 从两侧减去n²得到:n²> = n?

很明显，假设n始终是整数，则n²> = n(由于n = 0或1，因此不严格大于n).

实际的大O复杂性与我刚才所说的略有不同，但这是要点.实际上，对于具有足够大的输入量，Big O复杂性询问是否可以将一个常数应用到一个函数，使其大于另一个函数(请参见 解决方案

Yes, nested loops are one way to quickly get a big O notation.

Typically (but not always) one loop nested in another will cause O(n²).

Think about it, the inner loop is executed i times, for each value of i. The outer loop is executed n times.

thus you see a pattern of execution like this: 1 + 2 + 3 + 4 + ... + n times

Therefore, we can bound the number of code executions by saying it obviously executes more than n times (lower bound), but in terms of n how many times are we executing the code?

Well, mathematically we can say that it will execute no more than n² times, giving us a worst case scenario and therefore our Big-Oh bound of O(n²). (For more information on how we can mathematically say this look at the Power Series)

Big-Oh doesn't always measure exactly how much work is being done, but usually gives a reliable approximation of worst case scenario.

---

4 yrs later Edit: Because this post seems to get a fair amount of traffic. I want to more fully explain how we bound the execution to O(n²) using the power series

From the website: 1+2+3+4...+n = (n² + n)/2 = n²/2 + n/2. How, then are we turning this into O(n²)? What we're (basically) saying is that n² >= n²/2 + n/2. Is this true? Let's do some simple algebra.

• Multiply both sides by 2 to get: 2n² >= n² + n?
• Expand 2n² to get:n² + n² >= n² + n?
• Subtract n² from both sides to get: n² >= n?

It should be clear that n² >= n (not strictly greater than, because of the case where n=0 or 1), assuming that n is always an integer.

Actual Big O complexity is slightly different than what I just said, but this is the gist of it. In actuality, Big O complexity asks if there is a constant we can apply to one function such that it's larger than the other, for sufficiently large input (See the wikipedia page)

这篇关于嵌套for循环的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！