嵌套循环的时间复杂度分析

嵌套循环的时间复杂度分析

问题： 下面程序的时间复杂度为 ( )。

for(i=0; i<m; i++) for(j=0; j<n; j++) a[i][j]=i*j;

A. O(mn) B. O(nn) C. O(m*m) D. O(m+n)

答案： A. O(m*n)

解析：

在这段代码中，我们有两个嵌套的循环。外部循环以 i 从 0 到 m-1 迭代，内部循环以 j 从 0 到 n-1 迭代。每次内部循环迭代时，都会执行一个简单的乘法操作。

• 内部循环的迭代次数为 n。* 外部循环的迭代次数为 m。

因此，总的操作次数为 m * n，即时间复杂度为 O(m*n)。

总结：

嵌套循环的时间复杂度通常是外部循环迭代次数和内部循环迭代次数的乘积。在本例中，外部循环迭代 m 次，内部循环迭代 n 次，所以时间复杂度为 O(m*n)。