PTT職涯區 / Examination (國家考試)

[考題] 請問時間複雜度計算?

看板Examination (國家考試)作者 (pinky)時間13年前 (2013/01/15 23:45), 編輯推噓2(2推 0噓 5→)
留言7則, 2人參與, 最新討論串1/1
for(i=1;i<n;i++) { for(j=1;j<n;j=j+i) x=x+1; } 請問這題要怎麼計算時間複雜度?? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.39.143.160
推
01/16 00:20, , 1F
第一圈執行n次 第二圈執行n/2次 第三次n/3...
01/16 00:20, 1F
→
01/16 00:21, , 2F
n+n/2+n/3+...+ 1 = n*(1+1/2+1/3+...+1/n) =nlogn
01/16 00:21, 2F
→
01/16 00:21, , 3F
O(nlogn)
01/16 00:21, 3F
→
01/16 10:25, , 4F
請問那n^0.00001要如何以big -O或其它符號表示?
01/16 10:25, 4F
→
01/16 10:26, , 5F
n^0.00001=O(log n)是錯的,那請問正確要怎麼解?
01/16 10:26, 5F
推
01/16 11:08, , 6F
只能確定n^0.00001=Omega(logn)但不知如何用O notation
01/16 11:08, 6F
→
01/16 11:08, , 7F
表示tightest upper bound
01/16 11:08, 7F
‣ 更多 pinky94 的文章
文章代碼(AID): #1GzNclRZ (Examination)
Examination 近期熱門文章
更多 近期熱門文章 >>
PTT職涯區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 pinky94 的文章
文章代碼(AID): #1GzNclRZ (Examination)