Re: [問題] 程式執行複雜度
※ 引述《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
討論串 (同標題文章)