Big O 理解二次 n(n+1)/2 图
Big O Understand Quadratic n(n+1)/2 diagram
阅读关于二次 n(n+1)/2 的 DS 和算法。这里有2张图Figure 4.1a & 4.1b.
我理解图 4.1a 但不理解图 4.1b。
我知道图 4.1b 是 n/2（x 轴）的倍数（n+1）（y 轴）。这个图中的锯齿线我看不懂。
任何帮助都很好。
视觉呈现
真的很简单。
您从 4(a) 中取出最后一个柱并将其粘贴到 4(a) 的第一个柱上。这导致图表的第一个柱状图 4(b)。然后，您使用图表 4(a) 的倒数第二个柱和第二个柱，将它们放在彼此的顶部，您将获得图表 4(b) 的第二个柱。您也可以对其他栏执行此操作。
这只是公式的直观表示，因此您可以轻松地看到它是 n(n+1)/2。
数学思想
当你用更多的数学术语来思考它时，它也很合乎逻辑。
我们有 n 个求和数。
1 + 2 + 3 + ... + (n-3) + (n-2) + (n-1) + n
现在将 1 to n 中的相同数字以相反的顺序写在下面，因此从 n to 1.
n + (n-1) + (n-2) + n(n-3) + ... + 3 + 2 + 1
现在合并这两个序列并智能地重新排列被加数并设置一些括号。
[n + 1] + [(n-1) + 2] + [(n-2) + 3] + [(n-3) + 4] + ... =
我们还有 n 个求和数，每个都是 (n + 1)
但因为我们刚刚写了两次相同的数字，所以我们需要除以
我们的结果 2.
(n + 1) + (n + 1) + (n + 1) + (n + 1) + ... = n (n+1) /2
使用归纳法的数学证明
鉴于假设n (n+1) /2，不难通过归纳证明这实际上是正确的。参见 Wikipedia。
阅读关于二次 n(n+1)/2 的 DS 和算法。这里有2张图Figure 4.1a & 4.1b.
我理解图 4.1a 但不理解图 4.1b。
我知道图 4.1b 是 n/2（x 轴）的倍数（n+1）（y 轴）。这个图中的锯齿线我看不懂。
任何帮助都很好。
视觉呈现
真的很简单。
您从 4(a) 中取出最后一个柱并将其粘贴到 4(a) 的第一个柱上。这导致图表的第一个柱状图 4(b)。然后，您使用图表 4(a) 的倒数第二个柱和第二个柱，将它们放在彼此的顶部，您将获得图表 4(b) 的第二个柱。您也可以对其他栏执行此操作。
这只是公式的直观表示，因此您可以轻松地看到它是 n(n+1)/2。
数学思想
当你用更多的数学术语来思考它时，它也很合乎逻辑。
我们有 n 个求和数。
1 + 2 + 3 + ... + (n-3) + (n-2) + (n-1) + n
现在将 1 to n 中的相同数字以相反的顺序写在下面，因此从 n to 1.
n + (n-1) + (n-2) + n(n-3) + ... + 3 + 2 + 1
现在合并这两个序列并智能地重新排列被加数并设置一些括号。
[n + 1] + [(n-1) + 2] + [(n-2) + 3] + [(n-3) + 4] + ... =
我们还有 n 个求和数，每个都是 (n + 1)
但因为我们刚刚写了两次相同的数字，所以我们需要除以
我们的结果 2.
(n + 1) + (n + 1) + (n + 1) + (n + 1) + ... = n (n+1) /2
使用归纳法的数学证明
鉴于假设n (n+1) /2，不难通过归纳证明这实际上是正确的。参见 Wikipedia。