[理工] [資結]big O

[bouwhat (微笑的故事)]

請教下面兩題bigO算法
1、
for(i=0;i<N;i++)
for(j=i+1;j<N;j++)
for(k=j+1；k<N;k++)
cout<<"count";

2.
for(i=1;i<n;i++)
for(j=1;j<n;j=j+i)
x=x+1;

第一題答案：O(N^3)
第二：O(n lgn)

--
posted from android bbs reader on my samsung GT-I9003

https://market.android.com/details?id=com.bbs.reader

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 27.241.14.7
推 ddczx:1.即0<=i<=j<=k<=N 整數解個數 -> x1+x2+..+xN=3 之正整數解
→ ddczx:C(N-1+3,3)=C(N+2,3)=(N+2)(N+1)(N)/6=O(N^3)
推 Murasaki0110:原來還可以照d大這樣想 多謝學到一招
→ ddczx:2.i從1~n,約作n/i次,n+n/2+n/3+....+n/n=O(nlogn)
→ ddczx:這是除了列式展開的另一種想法，上離散學到的XD
→ bouwhat:感謝d大！第一題解法真神奇
推 ghjklgv9:推D大解法