数据结构与算法求解答

Question

求时间复杂度

1. i=1;
   while(i<n)
   i=i*2

2. for(i=0;i<n;i++)
   for(j=i;j<n;j++)
   b［i］［j］=i*2

求解，为什么第一个为log2 n
第二个为什么为n2

Answer 1

1、i每次增加两倍，那么相当于运行x次之后需要满足i^x<n，i^(x+1)>n,那么x的大小就是log2 n
2。第二个数双重for循环，每一重都是0-n,那么你去计算频次的话就是N^2

Answer 2

复杂度是看执行频度的量级,注意是量级，第一个是小于n、i每次增加一倍，执行了多少次呢 i*2^x =n 那么x不就是log2 n了
第二个第一重是0-n,二重循环是i到n，那么执行次数是n+……1,高斯公式，（n+1）n/2、量级是n的平方