國立中央大學

#請益 #請益 請教複雜度問題

2021年8月7日 05:26
剛開始學演算法,想向大家請教這段程式的複雜度,感恩! for(int i = 0; i < n; i++){ if(i + 1 == n){ int k = n; while(k >= 0){ k--; } } }
5
留言 14
文章資訊
Logo
每天有 6 則貼文
共 14 則留言
原 PO - 國立中央大學
想了一陣子應該是O(n) 因為最糟情況是2n 有錯的話麻煩糾正 感恩!
長庚大學
O(n) 沒錯吧 不過說最糟情況有點怪? 這個程式不管怎麼跑次數只由 n 決定吧 哪裡來的最糟、最好跟平均?
逢甲大學
b2 時間複雜度不是討論時間花費的上界嗎?即最糟情況 所以應該是O(2n) ? (我也是新手 求解
長庚大學
B3 舉個例子 以排序法來說 可能會有最糟情況:5 4 3 2 1 可能會有最好情況:1 2 3 4 5 也可能會有平均情況:3 1 5 2 4 在以上三種情況中 雖然 n (陣列的長度) 都是一樣的 花費的時間卻有長有短 所以才會有最糟、最好跟平均的時間複雜度一說 但是 以原 po 這個例子來說 唯一的輸入就是 n 程式跑的時間就是跟 n 呈正比 一但 n 被確定了 每一行程式碼運行的次數也就決定了 那如果你說最糟是 O(n) 請問最好是?平均是? 以上個人理解 我本人也是大一小菜雞而已
國立中興大學
他沒有最糟啊,他是一個固定的複雜度,然後O不會帶係數,所以是O(n)
國立中興大學
如果覺得不清楚,自己根據不同的n trace一遍就知道了
逢甲大學
b4 懂了~ 感謝說明!
淡江大學
B4 大一懂這麼多,騙人的吧www
匿名
這則留言已被刪除
已經刪除的內容就像 Dcard 一樣,錯過是無法再相見的!
原 PO - 國立中央大學
學習了! 謝謝大家回覆
長庚大學
B8 哈哈哈哈哈 謝謝你的誇獎😃
國立交通大學 資訊工程學系
B3 時間複雜度並不一定只討論最糟情況,例如 quicksort 的平均複雜度是 O(nlogn),而最糟複雜度卻是O(n^2)(考慮到每次 pivot 都選到最小或是最大的情況,不過顯然這機率太低了,期望值算起來是 O(nlogn))。 以這一題而言,當 i 從 0 ~ n - 2 的時候都不會做事,總共執行 n - 1 次,也就是 O(n)。 然後當 i 是 n - 1 時,會再執行 n + 1 次(k 從 n 到 0),也就是 O(n)。 因此總共無論 n 是多少,固定執行 O(n) + O(n) 次,因此 best case、worst case 和平均複雜度都是 O(n)。
國立交通大學 資訊工程學系
一種幫助你估計的方式: ``` int cnt = 0; for(int i = 0; i < n; i++){ if(i + 1 == n){ int k = n; while(k >= 0){ k--; cnt ++; } } } printf("%d", cnt); ``` 然後你自己測試不同的 n 的時候,cnt 會是多少。
逢甲大學
b12 okok 懂了 謝謝你!