嵌套循环的运行时间估计/大O表示

Question

我无法理解代表某些代码中执行的操作数的函数f（x）的含义。

int sum = 0; // + 1 
for (int i = 0; i < n; i++) 
    for (int j = 1; j <= i; j++) 
     sum = sum + 1; // n * (n + 1)/2 

（请注意，在对最后的评论分子没有2，但在以下的功能。）

然后我的笔记说，F（X）= 2N（N + 1）/ 2 + 1 = O（n^2）

我明白，因为有两个for循环，无论f（x）是什么，它将= O（n^2），但为什么是时间估计是什么？ j < =我给你n *（n + 1）？那么分母中的2呢？

Answer 1

想想，在这段代码的整个执行过程中，内循环将运行多少次。请注意，

• 当i = 0时，它运行零次;
• 当i = 1时，它运行一次;
• 当i = 2时，它运行两次;
• 当i = 3时，它运行三次;
• ...;和
• 当我= n - 1时，它运行n - 1次。

这意味着总次数最内层循环运行由下式给出

0 + 1 + 2 + 3 + 4 + ... +（N - 1）

这是一个著名的求和并且它解决了向

0 + 1 + 2 + 3 + 4 + ... +（N - 1）= N（N - 1）/ 2

这是第n个第一个triangular number它是值得提交到内存。

给出的数字-n（n + 1）/ 2 - 似乎是不正确的，但它非常接近真实数字。我认为他们假定循环会运行1 + 2 + 3 + ... + n次而不是0 + 1 + 2 + ... + n - 1次。

由此可以更容易地看出O（术语）的术语来自何处。注意n（n - 1）/ 2 = n，所以在我们掉落常数和低阶项的大O陆地上，我们只剩下n 。