数据结构与算法求解答

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