作者pinky94 (pinky)
看板Examination
标题[考题] 请问时间复杂度计算?
时间Tue Jan 15 23:45:49 2013
for(i=1;i<n;i++)
{
for(j=1;j<n;j=j+i)
x=x+1;
}
请问这题要怎麽计算时间复杂度??
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.39.143.160
1F：推 carterdunk:第一圈执行n次 第二圈执行n/2次 第三次n/3... 01/16 00:20
2F：→ carterdunk:n+n/2+n/3+...+ 1 = n*(1+1/2+1/3+...+1/n) =nlogn 01/16 00:21
3F：→ carterdunk:O(nlogn) 01/16 00:21
4F：→ pinky94:请问那n^0.00001要如何以big -O或其它符号表示? 01/16 10:25
5F：→ pinky94:n^0.00001=O(log n)是错的,那请问正确要怎麽解? 01/16 10:26
6F：推 carterdunk:只能确定n^0.00001=Omega(logn)但不知如何用O notation 01/16 11:08
7F：→ carterdunk:表示tightest upper bound 01/16 11:08