[問題] 時間複雜度

看板C_and_CPP作者 (一見鍾情)時間12年前 (2011/10/01 01:01), 編輯推噓4(4推 0噓 16→)
留言20則, 9人參與, 最新討論串1/1
根據big O的定義:存在c,n0>0使得當n>=n0時,f(n)<=cg(n) 今天老師教了一題95成大資工的考題 n平方+n*lgn+n/2=O(n八次方) True or False? 答案是True 那麼請問一下為甚麼2個for圈(for包for)的複雜度是O(n平方)而不寫成O(n八次方)? 演算法新手請教! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.173.22.221
→
10/01 01:12, , 1F
N*N 不就是平方嗎 N*N*N*N*N*N*N*N 這才是八次方吧
10/01 01:12, 1F
→
10/01 01:14, , 2F
上面的算式order也是n*n 但是也可以說O(n八次)
10/01 01:14, 2F
→
10/01 01:15, , 3F
所以我想說 for包for 也可以這樣說囉?
10/01 01:15, 3F
→
10/01 01:18, , 4F
而且好像也沒O(n八次方)這種時間複雜度
10/01 01:18, 4F
→
10/01 01:19, , 5F
不是就n平方 n3次方 2的n次方 再來就n!了 有n八次方?
10/01 01:19, 5F
→
10/01 01:20, , 6F
其實我也不了你的問題XD 希望真的有高手能替你解答
10/01 01:20, 6F
→
10/01 01:21, , 7F
因為考題是這樣寫的 其實我也沒印象有8次方
10/01 01:21, 7F
→
10/01 01:27, , 8F
有呀 你枚舉八皇后就八次方了呀(茶)
10/01 01:27, 8F
→
10/01 01:30, , 9F
想錯了@@
10/01 01:30, 9F
→
10/01 01:43, , 10F
回原po 因為那些要你算big O的題目 其實要的答案都是Θ
10/01 01:43, 10F
→
10/01 01:43, , 11F
此問題與程式語言無直接關聯, 請移駕Prob_Solve討論
10/01 01:43, 11F
→
10/01 02:19, , 12F
100公尺10秒跑完的短手選手　說他可以在1分鐘之內跑完
10/01 02:19, 12F
→
10/01 02:20, , 13F
100公尺，這樣也沒什麼不對，只是意義不大
10/01 02:20, 13F
推
10/01 02:55, , 14F
短跑選手 打錯字了 Orz
10/01 02:55, 14F
推
10/01 04:21, , 15F
BigO 符號定義可以再看一次.
10/01 04:21, 15F
→
10/01 05:52, , 16F
c要是定下來的喔，所以你正數隨便寫一個都對
10/01 05:52, 16F
→
10/01 05:53, , 17F
隨便寫意思是 你找一個應該都會對，保險點就寫大一點
10/01 05:53, 17F
推
10/01 16:27, , 18F
這類型題目要的都是最小的big-O, 不然任何題目你都寫
10/01 16:27, 18F
→
10/01 16:27, , 19F
O(N^N^N) 不就好了=)
10/01 16:27, 19F
推
10/01 17:58, , 20F
考試可以自改題目嗎?
10/01 17:58, 20F
‣ 更多 whatacatch 的文章
文章代碼(AID): #1EXVNomd (C_and_CPP)