作者LPH66 (-858993460)
看板Prob_Solve
标题Re: [问题] 程式执行复杂度
时间Sun Oct 2 01:54:43 2011
※ 引述《suhorng ( )》之铭言：
: : 2. for(a=1; a<=n; a*=2)
: : for(b=1; b<=a; b*=2)
: : c++;
: 上界 O( (log n)^2 ) 是容易的: 外层回圈跑 O(log n) 次
: 内层回圈每次也跑不超过 O(log n) 次
: 下界不会><
这其实和下面这个是一样的:
for(x=0; x<=logn; x++)
for(y=0; y<=x; y++)
z++;
(把 a,b,n 都取 log 就会知道是一样的了
我这是令 x=loga y=logb 写出来的)
所以自然是 O((logn)^2)
: : 4. k=0;
: : for(i=1; i<n; i++)
: : for(j=1; j<i*i; j++)
: : for(j%i==0)
: 我把它当成if
: : for(z=0; z<j; z++)
: : k++;
: z那层: i+(2i)+(3i)+(4i)+...+(i-1)i = O(i^3)
: //因为跑z的时候j是i的倍数
: 最後 O(Σi^3) = O(n^4)
其实可以这样看 它等同於
for(i=1; i<n; i++)
for(J=1; J<i; J++)
for(z=0; z<i*J; z++)
k++;
n i n i
所以就是 Σ Σ i*J = Σ i Σ J 後面就和上面的算式一样了
i=1 J=1 i=1 J=1
--
1985/01/12 三嶋鸣海 1989/02/22 优希堂悟 1990/02/22 冬川こころ 1993/07/05 小町
つぐみ 欢迎来到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬
チサト 1998/06/18 守野くるみ 打越钢太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遥
2002/12/17 八神ココ 2011/01/11 HAL18於朱仓岳坠机 ∞与∫的世界 2011/04/02 茜崎空
启动 2012/05/21 第貮日蚀计画预定 2017/05/01~07 LeMU崩坏 2019/04/01~07 某大学合宿
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.24.187