时间复杂度分析题，有没有高人帮帮忙的

Question

给定以下两个算法：

算法A：

for(int i = 0; i < N; i++)

 

   for(int j = 0; j< N; j++)

 

    {

 

         S;

 

    }

算法B：

for(int i = 0; i < N; i++)

 

   for(int j = i; j< N; j++)

 

    {

 

         S;

 

    }

其中N是一个比较大的自然数，S是有若干基本语句组成的程序段。

1）在相同的计算机上，算法A比算法B运行速度慢？

2）算法A的时间复杂度比算法B要高？

请判断以上两个命题是否正确？并说明理由。

Answer 1

1）正确，因为i递增，那么第二次循环的次数就减少
2）两个的时间复杂度一样，时间复杂度看的是最差的情况下，所以两者的时间复杂度都未O(n2)
有用记得采纳呀！