寻找算法的 T(n)

Question

好吧，当我的教授在 class 复习它时，它看起来很简单，但是当我开始做作业时，我变得很困惑。这是作业范例。

for (int i = 0; i < n; i++)    // I know this runs at T(n)
 for (int j = n - 1; j >= i; j--)
 cout << i << " " << j << endl;

举个我理解的例子

for(int i=0; i<n-1; i++) {
  for(int j=i+1; j<n; j++) {
    1 Simple statement
   }

对于那个例子，我只是插入了 0、1 和 2。对于 0，它运行代表 n-1，1 代表 n-2 和 2 n-3。所以我认为对于家庭作业示例，如果我插入 0，n+1 将运行，因为 j 必须大于或等于 i，即 0。如果它不明显，我会很困惑。如果有人能告诉我如何解决它，那会让我开心。谢谢大家。

Answer 1

让我们深入研究一下函数。让我们选择一些数字。

比如说，n = 5

所以我们的代码看起来像这样（神奇的伪代码使用了包含循环，并不是说它太重要了）

(1)for i = 0 to 4
  (2)for j = 4 to i
     (3)print i j
  next
next

所以这是一个偏好问题，但通常假设循环每次执行（比较和递增）花费 1 个简单语句。所以我们假设语句 (1) 和 (2) 的成本为 2。语句 (3) 的成本为 1。

现在确定T(n)。

我们的外层循环 for i = 0 to 4 恰好运行了 n 次。我们的内部循环 for j = 4 to i 。 . .我们将在那里挖掘一分钟。

对于我们的示例，n = 5 循环 (2) 将像这样执行

j = 4; i = 0;  j = 4; i = 1;  j = 4; i = 2;  j = 4; i = 3  j = 4; i = 4;
j = 3; i = 0;  j = 3; i = 1;  j = 3; i = 2;  j = 3; i = 3;
j = 2; i = 0;  j = 2; i = 1;  j = 2; i = 2;
j = 1; i = 0;  j = 1; i = 1;
j = 0; i = 0;

所以它形成了这种金字塔形状，每次我们少做 1 次迭代。这个特定的例子运行 5 + 4 + 3 + 2 + 1 = 15 次。

我们可以将其记为 SUM(i; i = 0 to n)。

我们从预计算中知道：= (1/2)(n)(n+1).

并且 (3) 将执行与该内部循环完全相同的次数，因为它是唯一的语句。所以我们的总运行时间将是。 . . 成本(1) + 成本(2) + 成本(3) (2)(n) + 2(1/2)(n)(n+1) + (1/2)(n)(n+1)

我们可以将其清理为

(3/2)(n)(n+1) + 2n = T(n).

也就是说，这假设循环成本为 2，语句成本为 1。通常说循环成本为 0，语句成本为 1 更有意义。如果是这种情况，则 T(n) = (1/2) (n)(n+1).

鉴于 T(n)，我们知道 T(n) 是 O(n^2)。

希望对您有所帮助！

Answer 2

没那么难。

3 个单循环示例：

for (int i = 0; i < n; i++)
for(int i = 0; i < n-1; i++)
for(int i = 2; i < n-1; i++)

第一个循环执行它的内容 n 次（i=0,1,2,3,...,n-1）。
同理，第二个循环也就n-1次。
第三个是 n-3 因为它不是从 0 开始，而是 2
（如果 n 小于 3，即 n-3<0，它根本不会执行）

在像

这样的嵌套循环中

for(int i = 0; i < n-1; i++) {
  for(int j = 0; j < n; j++) {
    //something
  }
}

对于外循环的每一次通过，都会执行整个内循环，即。您可以将两个单循环计数相乘以获得 "something" 总共执行的频率。在这里，它是(n-1) * n = n^2 - n。

如果内循环依赖于外循环的值，它会变得有点复杂：

for(int i = 0; i < n-1; i++) {
  for(int j = i+1; j < n; j++) {
    //something
  }
}

单独的内部循环是 n - (i+1) 次，外部循环是 n-1 次（i 从 0 到 n-2）。
虽然有 "proper" 种计算方法，但有点逻辑思维通常更容易，就像您已经做的那样：

i-value => inner-loop-time
0 => n-1
1 => n-2
...
n-2 => n - (n-2+1) = 1

所以你需要总和 1+2+3+...+(n-1)。
对于计算从 1 到 x 的总和，以下公式有帮助：

sum[1...x] = x*(x+1)/2

所以，从 1 到 n-1 的总和是

sum[1...n-1] = (n-1)*(n-1+1)/2 = (n^2 - n)/2

这就是上述循环的解决方案（您的第二个代码）。

关于第一个代码：
外循环：n
内循环：包括从 n-1 到 i，或者从 i 到 <=n-1,
或者从 i 到 <n，那是 n-i 倍

i >= innerloop
0 n
1 n-1
2 n-2
...
n-1 1

...从1到n的和是(n^2 + n)/2.

Answer 3

调查问题的一种简单方法是对其建模并查看结果数据。

在您的情况下，问题是：内部循环根据外部循环变量的值执行多少次迭代？

let n = 10 in [0..n-1] |> List.map (fun x -> x,n-1-x);;

上面的第 1 行是显示发生情况的模型。如果您现在查看结果输出，您会很快注意到一些事情...

val it : (int * int) list = [(0, 9); (1, 8); (2, 7); (3, 6); (4, 5); (5, 4); (6, 3); (7, 2); (8, 1); (9, 0)]

你注意到了什么？对于给定的 N 你运行外循环 N 次 - 这是微不足道的。现在我们需要对第二个数字求和，我们就有了解决方案：

sum(N-1..0) = sum(N-1..1) = N * (N-1) / 2.

因此 cout 调用的总次数为 N * (N-1) / 2。

实现相同目的的另一种简单方法是稍微修改您的函数：

int count(int n) {
   int c = 0;
   <outer for loop>
       <inner for loop>
           c++;
   return c;
}

寻找算法的 T(n)

Finding the T(n) of An Algorithm

c++

algorithm

big-o