[理工] [資結]-時間複雜度

看板Grad-ProbAsk作者時間16年前 (2009/12/03 23:08), 編輯推噓2(2推 0噓 2→)
留言4則, 3人參與, 最新討論串16/38 (看更多)
Let T(n) be the running time of Foo(n). Find the order of T. Foo(int n){ for i from 1 to n x = n while x > 0 do x = x - i } 為什麼是O(nlgn)? 不是O(n)嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.116.218.120
推
12/03 23:22, , 1F
nlgn 沒錯~~你n代5去跑跑看就知道了~
12/03 23:22, 1F
→
12/04 18:44, , 2F
for loop 跑n次 => x=n while 跑一次 break
12/04 18:44, 2F
→
12/04 18:45, , 3F
這樣不是O(n)??
12/04 18:45, 3F
推
12/05 01:31, , 4F
這題目本來就有一點問題XD
12/05 01:31, 4F
‣ 更多 NOtWorThy 的文章
文章代碼(AID): #1B5zHZLx (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 16 之 38 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共38篇)
‣ 更多 NOtWorThy 的文章
文章代碼(AID): #1B5zHZLx (Grad-ProbAsk)