推 yesa315:感謝 推 12/29 09:58
推 chenbojyh:推薦這篇文章 12/29 12:27
※ 引述《yesa315 (XD)》之銘言：
: ※ 引述《FRAXIS (喔喔)》之銘言：
: : N-1 i*i-1 j-1 N-1 i*i-1 N-1 i-1 N-1
: : Σ Σ [j%i==0] Σ 1 = Σ Σ [j%i==0] * j = Σ i Σ j = Σ i * (i+1)*i/2
: : i=1 j=1 z=0 i=1 j=1 i=1 j=1 i=1
: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
: 轉換不太懂
: 感覺的出來是 O(N^4) 但我是把Σ拆開來想才有感覺的
: 可以請F大講清楚一點嗎
: : = O(N^4)
: 謝謝
我只是用正式的數學方法來寫證明而已，[]是一個一元運算子
[P] : P為一邏輯判斷式，如果P為真則[P]為1，如果P為假則[P]為0
這樣才有辦法在summation中處理邏輯判斷。
直覺上可以這樣來理解
k=0
for(i=1;i<N;i++)
for(j=1;j<i*i;j++)
if(j%i==0)
for(z=0;z<j;z++)
k++;
j % i == 0 成立的情況下, 只有j = i, 2i, 3i, ..., (i-1)i 所以就變成了
N-1 i-1
Σ i * Σ j
i=0 j=1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50