学习文章:C语言中的窗口滑动技术
- C语言中的窗口滑动技术
循环几乎是每个复杂问题的一部分。太多的循环/嵌套循环会增加所需的时间,从而增加程序的时间复杂性。窗口滑动技术是一种计算技术,用于减少程序中使用的嵌套循环的数量,通过用单个循环代替嵌套循环来提高程序的效率。
如果你熟悉计算机网络中的滑动窗口协议,这种技术也很类似,本教程通过不同的例子解释了这种技术的使用方法。
一般来说,当我们使用这样的嵌套循环时 。
for(i = 1; i <= n; i++)
{
for(j = i; j < k; j++)
{
}
}
迭代: 外循环执行\(n\)次;每执行一次外循环,内循环就执行\((k-i)\)次。执行整个循环所需的平均时间大约为$O(N^2) $。因此,开发人员不建议使用循环。
让我们举一个例子来清楚地理解这个概念 。
假设我们要找到一个数组中\(’k’\)个连续元素的最大和,用户提供\(k\)值:
首先,如果我们使用传统的方法,对于数组中的每个元素\(i\),我们将从\(i+1\)到\(n-1\)遍历数组,其中\(n\)是数组的大小,我们需要对每个元素都这样做,然后比较总和,得到最大总和。
- 暴力方法
#include<stdio.h>
int main()
{
/*
找到一个数组中’k’个连续元素的最大和
*/
int n, size, sum=0, max = 0, j;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n], i;
printf("Enter the elements of the array: ");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the size of sub-array: ");
scanf("%d", &size);
for(i = 0; i < (n - size) + 1; i++)
{
/*
其实也是滑动窗口的思想
*/
sum = 0;
for(j = i; j < i + size; j++)
{
sum = sum + arr[j];
}
if(sum > max)
{
max = sum;
}
}
printf("The maximum sum of %d consecutive elements of the array: %d\n", size, max);
}
输出 :
Enter the size of the array: 10
Enter the elements of the array: 8 2 1 7 3 2 5 8 1 3
Enter the size of the sub-array: 3
The maximum sum of 3 consecutive elements of the array: 20
现在,滑动窗口技术来了
这里的概念是,我们创建一个大小为\(k\)的窗口,我们将通过一个单位指数不断地滑动它。在这里,窗口并不是什么技术术语。我们不是像在循环中那样使用一个单一的值,而是在每次迭代中同时使用多个元素。
比如说给定一个大小为10的数组:
假设我们需要3个连续索引的最大和,创建一个3个大小的窗口,并在整个数组中不断滑动(遍历)它。这里有一个形象的表示。
迭代1:
迭代2 :
迭代3:
迭代4:
迭代5:
迭代6:
迭代7:
迭代8:
- 使用这种方法,将没有内循环,一个单循环的迭代次数将是\((n – k + 1)\),在这种情况下是8。
- 所以,滑动窗口是一种用于减少嵌套循环的技术,用一个单循环代替它,以减少总的时间复杂性。
- 请注意,在每次迭代中,当窗口滑动到下一个索引时, 我们都会删除前一个窗口的第一个元素,并添加一个新的元素,即下一个继任索引。
下面是代码:
#include <stdio.h>
int maxsum(int a[], int k, int n);
int main()
{
int n, i, k;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements: ");
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the value of k: ");
scanf("%d", &k);
int max = maxsum(arr, k, n);
printf("The maximum sum of %d consecutive elements in the array: %d\n", k, max);
}
int maxsum(int a[], int k, int n)
{
int i, sum, maxm = 0;
for (i = 0; i < k; i++)
{
maxm = maxm + a[i]; //记录第一个窗口元素和
}
sum = maxm; //初始化sum
for (i = k; i < n; i++)
{
sum += a[i] - a[i - k]; //当窗口滑动到下一个索引时, 我们都会删除前一个窗口的第一个元素,并添加一个新的元素
if (sum > maxm)
{
maxm = sum;
}
}
return maxm;
}
输出:
Enter the size of the array: 10
Enter the elements: 8 2 1 7 3 2 5 8 1 3
Enter the value of k: 3
The maximum sum of 3 consecutive elements in the array: 15
- 暴力方法在两个嵌套循环中需要\(O(k*n)\)时间。
- 通过使用滑动窗口技术,时间复杂度降低到\(O(n)\)。
以下是将该技术应用于手头任何问题的步骤:
- 首先,我们必须看到,窗口的大小是恒定的,不应该改变。我们可以只对这样的问题使用该技术。
- 在确保窗口大小没有变化后,计算第一个窗口的结果,与数组其他部分的计算结果进行比较。
- 现在,用一个循环来逐个滑动窗口的索引,直到最后,不断更新所需的值。