了解这个子数组求和算法的步骤及其 运行 时间
Understanding the steps in this sum of subarrays algorithm and its run time
我已经盯着这个看了一段时间了，但还没有完全理解。我想我基本了解发生了什么。例如。 A = {1, 2, 3, 4}
总和 = A[0] + [A[0] + A[1]] + [A[0] + A[1] + A[2]] + [A[0] + A[1] ] + A[2] + A[3]]
但是，我无法通过下面的 explanation/notation 理解这些步骤 - 或者至少，它有点模糊。有人可以通过正在发生的事情解释 steps/walk 吗？
示例 1.4（子数组的总和）。问题是对于大小为 n 的数组 a 中大小为 m 的每个子数组 a[j..j +m−1] 计算其元素的部分和 s[j] = ∑ m−1 k=0 a [j+k]; j = 0,...,n−m。这些子阵列的总数是 n−m+1。
乍一看，我们需要计算 n−m+1 个总和，每个项目都有 m 个，因此 运行 时间与 m(n−m+1) 成正比。如果 m 是固定的，时间仍然与 n 线性相关。但如果 m 以 n 的分数增长，例如 m = n 2，则 T(n) = cn 2n 2 +1= 0.25cn2 +0.5cn。线性部分的相对权重，0.5cn，随着n的增大，相对于二次方的权重迅速减小。
嗯，你的解释好像不是你对问题的理解。我认为，您的 示例 1.4 确实是关于跟随。
A = {1, 2, 3, 4}, m = 3.
Sum = (A[0] + A[1] + A[2]) + (A[1] + A[2] + A[3]).
这里有 n-m+1 (4-3+1=2) 个 m(3) 的子和每个元素。所描述的算法可以用这样的代码来执行：
function SumOfSubarrays(A, n, m) {
sum = 0;
//loop for subarrays
for (j = 0; j <= n - m; j++;) {
//loop for elements in each subarray
for (k = 0; k <= m - 1; k++) {
sum += A[j + k];
}
}
}
该算法的时间复杂度线性依赖于n。但是，正如 示例 1.4 中所说，如果 m 增长是 n 的一小部分，那么时间复杂度变为二次方。
您总共需要 m(n−m+1) 操作：(n−m+1) 用于外循环，因为它是多个子数组，m 用于内循环，因为它是每个子数组中的多个元素。如果 m 依赖于 n 那么你有，例如：
m = 0.5 * n
m(n-m+1) = 0.5n(n-0.5n+1) = 0.5n(0.5n-1) = 0.25n^2 - 0.5n
其中二次部分增长更快，因为它是二次的。
我已经盯着这个看了一段时间了，但还没有完全理解。我想我基本了解发生了什么。例如。 A = {1, 2, 3, 4}
总和 = A[0] + [A[0] + A[1]] + [A[0] + A[1] + A[2]] + [A[0] + A[1] ] + A[2] + A[3]]
但是，我无法通过下面的 explanation/notation 理解这些步骤 - 或者至少，它有点模糊。有人可以通过正在发生的事情解释 steps/walk 吗？
示例 1.4（子数组的总和）。问题是对于大小为 n 的数组 a 中大小为 m 的每个子数组 a[j..j +m−1] 计算其元素的部分和 s[j] = ∑ m−1 k=0 a [j+k]; j = 0,...,n−m。这些子阵列的总数是 n−m+1。
乍一看，我们需要计算 n−m+1 个总和，每个项目都有 m 个，因此 运行 时间与 m(n−m+1) 成正比。如果 m 是固定的，时间仍然与 n 线性相关。但如果 m 以 n 的分数增长，例如 m = n 2，则 T(n) = cn 2n 2 +1= 0.25cn2 +0.5cn。线性部分的相对权重，0.5cn，随着n的增大，相对于二次方的权重迅速减小。
嗯，你的解释好像不是你对问题的理解。我认为，您的 示例 1.4 确实是关于跟随。
A = {1, 2, 3, 4}, m = 3.
Sum = (A[0] + A[1] + A[2]) + (A[1] + A[2] + A[3]).
这里有 n-m+1 (4-3+1=2) 个 m(3) 的子和每个元素。所描述的算法可以用这样的代码来执行：
function SumOfSubarrays(A, n, m) {
sum = 0;
//loop for subarrays
for (j = 0; j <= n - m; j++;) {
//loop for elements in each subarray
for (k = 0; k <= m - 1; k++) {
sum += A[j + k];
}
}
}
该算法的时间复杂度线性依赖于n。但是，正如 示例 1.4 中所说，如果 m 增长是 n 的一小部分，那么时间复杂度变为二次方。
您总共需要 m(n−m+1) 操作：(n−m+1) 用于外循环，因为它是多个子数组，m 用于内循环，因为它是每个子数组中的多个元素。如果 m 依赖于 n 那么你有，例如：
m = 0.5 * n
m(n-m+1) = 0.5n(n-0.5n+1) = 0.5n(0.5n-1) = 0.25n^2 - 0.5n
其中二次部分增长更快，因为它是二次的。