程序段时间复杂度分析及优化

本文将对以下六个程序段的时间复杂度进行分析，并给出详细的解释：

1. 循环依赖变量

x=90; y=100;

while(y>0)
    if(x>100)
        {x=x-10;y--;}
    else x++;

时间复杂度为O(y)，因为while循环的执行次数取决于y的值。

2. 双重循环

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

时间复杂度为O(nm)，因为嵌套的两个for循环的执行次数分别为n和m。

3. 矩阵求和

s=0;
for i=0; i<n; i++)
    for(j=0; j<n; j++)
        s+=B[i][j];
sum=s;

时间复杂度为O(n^2)，因为嵌套的两个for循环的执行次数都为n。

4. 指数增长循环

i=1;
while(i<=n)
    i=i*3;

时间复杂度为O(log3(n))，因为每次循环i都会乘以3，直到i>n为止，所以i的取值次数为log3(n)。

5. 递减循环

x=0;
for(i=1; i<n; i++)
    for (j=1; j<=n-i; j++)
        x++;

时间复杂度为O(n^2)，因为嵌套的两个for循环的执行次数分别为n和n-i。

6. 平方根循环

x=n; //n>1
y=0;
while(x≥(y+1)* (y+1))
    y++;

时间复杂度为O(√n)，因为while循环的执行次数取决于y的值，而y的取值范围为0到√n。

总结

通过分析以上程序段的时间复杂度，我们可以看到，循环次数和时间复杂度之间存在密切关系。在编写程序时，应该尽量避免使用嵌套循环，并使用更有效率的算法，以降低程序的时间复杂度，提高程序的执行效率。