C++ 嵌套循环
一个循环可以嵌套在另一个循环中。C++ 允许至少256 层的嵌套。当一个循环在另一个循环中创建，形成多层循环时，称为嵌套循环。其中，内层循环会在外层循环的每次迭代中完全执行。 嵌套循环主要用于多维数据结构，例如矩阵或网格，或用于解决需要重复嵌套迭代的问题。
嵌套 for 循环
当一个 for 循环 嵌套在另一个 for 循环中时，称为嵌套 for 循环。这是最常见的嵌套形式。
语法
C++ 中 嵌套 for 循环 语句的语法如下 -
for ( init; condition; increment ) {
for ( init; condition; increment ) {
statement(s);
}
statement(s); // 你可以添加更多语句。
}
Example
#include <iostream>
using namespace std;
int main() {
for (int i = 1; i <= 3; i++) { // 外循环
for (int j = 1; j <= 2; j++) { // 内循环
cout << "Outer: " << i << ", Inner: " << j << endl;
}
}
return 0;
}
这将产生以下结果 -
Outer: 1, Inner: 1 Outer: 1, Inner: 2 Outer: 2, Inner: 1 Outer: 2, Inner: 2 Outer: 3, Inner: 1 Outer: 3, Inner: 2
嵌套 while 循环
当一个 while 循环 嵌套在另一个 while 循环中时，称为嵌套 while 循环。这主要用于需要动态确定迭代次数的情况。
语法
C++ 中 嵌套 while 循环 语句的语法如下 -
while(condition) {
while(condition) {
statement(s);
}
statement(s); // 你可以添加更多语句。
}
Example
#include <iostream>
using namespace std;
int main() {
int i = 1;
while (i <= 3) {
int j = 1;
while (j <= 2) {
cout << "Outer: " << i << ", Inner: " << j << endl;
j++;
}
i++;
}
return 0;
}
这将产生以下结果 -
Outer: 1, Inner: 1 Outer: 1, Inner: 2 Outer: 2, Inner: 1 Outer: 2, Inner: 2 Outer: 3, Inner: 1 Outer: 3, Inner: 2
嵌套 do-while 循环
当一个 do-while 循环 嵌套在另一个 do-while 循环中时，称为嵌套 do-while 循环。这确保了循环在检查条件之前至少执行一次。
语法
C++ 中 嵌套 do...while 循环 语句的语法如下 -
do {
statement(s); // 你可以添加更多语句。
do {
statement(s);
} while( condition );
} while( condition );
Example
#include <iostream>
using namespace std;
int main() {
int i = 1;
do {
int j = 1;
do {
cout << "Outer: " << i << ", Inner: " << j << endl;
j++;
} while (j <= 2);
i++;
} while (i <= 3);
return 0;
}
这将产生以下结果 -
Outer: 1, Inner: 1 Outer: 1, Inner: 2 Outer: 2, Inner: 1 Outer: 2, Inner: 2 Outer: 3, Inner: 1 Outer: 3, Inner: 2
嵌套循环示例
以下程序使用嵌套 for 循环查找 2 到 100 之间的素数 -
#include <iostream>
using namespace std;
int main () {
int i, j;
for(i = 2; i<100; i++) {
for(j = 2; j <= (i/j); j++)
if(!(i%j)) break; // if factor found, not prime
if(j > (i/j)) cout << i << " is prime";
}
return 0;
}
这将产生以下结果 -
2 is prime 3 is prime 5 is prime 7 is prime 11 is prime 13 is prime 17 is prime 19 is prime 23 is prime 29 is prime 31 is prime 37 is prime 41 is prime 43 is prime 47 is prime 53 is prime 59 is prime 61 is prime 67 is prime 71 is prime 73 is prime 79 is prime 83 is prime 89 is prime 97 is prime
嵌套循环如何影响计算复杂度
嵌套循环直接影响程序的计算复杂度，因为嵌套深度增加会增加执行的操作数量。
如果外循环执行 n 次，内循环在外循环每次迭代中执行 m 次，则总迭代次数等于 n*m，因此时间复杂度等于 O(mn);如果两个循环的范围相似，均为 nm，则复杂度约为 O(n^k)，其中 k 是嵌套深度。
例如:(O(n^2)) 多维数组(如矩阵和对)、(O(n^3)) 三元组、(O(n^4))等等。
- 执行时间增加:
每个额外的嵌套循环都会使总迭代次数呈指数级增长，因此，较大的输入大小 n 会影响更高时间复杂度((O(n^k)))的性能。 - 可扩展性问题:
嵌套循环可能会导致大型数据集的性能不佳，例如，使用 O(n^2) 处理大小为 1000 * 1000 的矩阵需要进行 1,000,000 次操作，这会降低其可扩展性。
优化嵌套循环
由于嵌套循环在处理一些问题时是一个重要的概念，因此对其进行优化将进一步提高算法的性能，尤其是在处理大型数据集时。
嵌套循环通常会导致指数级时间复杂度(例如 O(n)、O(n))，因此对其进行优化会对执行时间产生影响。
以下是一些优化技巧。
1. 避免不必要的嵌套
循环越多，程序运行速度越慢。因此，请尽量避免任何不必要的嵌套，有时重新排列循环或更改其顺序可以减少嵌套循环的需要。
2. 使用高效的数据结构
根据具体问题，您可以使用堆、队列和堆栈来优化访问模式。使用哈希集或哈希映射，它们可以实现插入和删除操作的常数时间复杂度。这通常用于大型数组或列表，以避免对其进行复杂的迭代。
3.提前中断(退出条件)
您可以根据需要提前中断循环，或者继续减少不必要的工作。
4. 使用分治法或动态规划
分治算法通过将问题分解为更小的子问题来帮助减少嵌套，这些子问题可以进一步独立求解，然后再组合起来。通过动态规划，您可以将指数时间复杂度问题转换为多项式时间复杂度问题。
5. 并行化
如果嵌套循环是独立的并且可以并行计算，则可以使用多线程或多处理，这可以加快程序速度。
6.应用数学优化和内置函数或库
数学优化有助于减少某些问题对嵌套循环的需求。
