algorithm - 分析给定的程序

Question

有人给我一段代码，让我分析它。我感到很困惑。我需要弄清楚 foo 运行了多少次，并使用它来确定 n 的函数。我知道 foo 运行了多少次，但我无法确定正确的功能。这是代码:

j = 1;
while( j <= n/2 )
{
   i = 1;
   while( i <= j )
   {
      foo;
      i++;
   }
   j++;
}

我知道 foo 的运行模式是将 n 的一半添加到运行中。例如，当 n = 2 时，foo 运行 1 次，当 n = 4 时， foo 运行 3 次，当 n = 6 时，foo 运行 6 次，等等。像这样:

n = 2   runs -> j = 1 *          1 run


n = 4   runs -> j = 1 * 
                j = 2 * *        3 runs

n = 6   runs -> j = 1 * 
                j = 2 * *
                j = 3 * * *      6 runs

n = 8   runs -> j = 1 *
                j = 2 * *
                j = 3 * * *
                j = 4 * * * *    10 runs

也许我只是想多了，但我已经盯着我的笔记本看了好几个小时，试图根据遵循这种行为的 n 来想出一些功能。谁能帮忙？

编辑 我还有一个问题。我怎么知道这个函数是在 Big-O 还是 Big-Theta 中？这与使用 while 循环而不是 for 循环有关吗？

Answer 1

一旦我们意识到大部分工作是由内部 while 循环完成的，我们就可以将运行时间(对于给定的 n)计算为内部 while 循环运行的次数:

1+2+3+...n/2 

这是 summation formula

= O(n²).