PTT職涯區 / Soft_Job (軟體人)

Re: [討論] 技術總監有可能不懂BFS嗎??已刪文

看板Soft_Job (軟體人)作者 (新規格)時間1年前 (2023/04/24 23:29), 1年前編輯推噓0(2推 2噓 22→)
留言26則, 8人參與, 1年前最新討論串7/8 (看更多)
看到這個可以聊一下big O notation，很多人在面試的時候可能會回答/或聽到面試官說「big O notation是一個評估演算法效能的方式」 …..其實並不是的哦~ big O notation在數學上是用來描述一個函數的參數在趨近於特定值或無限時的行為表達方式。在computer science領域則是在看「當input size趨於無限時，函數行為為何」的「分類方式」，和效能沒有直接關係。 舉個例子，例如今天有解同一個問題的兩個演算法，一個分析出來其時間複雜度為10^100*x，另一個分析出來時間複雜度是10^(-100)*x^1.1。則前者的big O notation為O(x)，後者為O(x^1.1)，明顯前者更加，但在實務上，當然大家應該會選擇後者的演算法。因此big O notation基本上是一個在分析層面的工具更多一些，在效能評比上可以當作理論分析用，但不是全部，實際開發時還是要透過benchmark才能得到最正確的結論。 因此，不管你是面試官或面試者，只要你聽到有人說big O notation是能拿評估演算法效能的，勇敢嗆回去吧XDDDD ※ 引述《LinuxKernel (Linus Torvalds)》之銘言： : 剛看到這個 YT 影片，不喜勿點 : https://www.youtube.com/watch?v=BkszA-MvjXA
: 在地上滾的工程師 aka Nic aka 工程技術總監 : 合拍了一個 coding interview 影片 : 一開始還想說應該是反串吧 : 但看到最後怎麼好像又不是?? : 軟體業的工程技術總監有可能分不清楚 BFS vs. DFS 或是 stack vs. queue 嗎?? -- Sent from nPTT on my iPhone 11 Pro -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.208.9 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1682350158.A.4E3.html
推
04/24 23:36, 1年前 , 1F
n要夠大比級數才有意義，不然常數的影響也要考慮進去
04/24 23:36, 1F
推
04/24 23:43, 1年前 , 2F
不同的scale下效能不一定一樣，實際跑Benchmark較為穩當
04/24 23:43, 2F
→
04/25 00:06, 1年前 , 3F
嗆回去不知道會不會適得其反？
04/25 00:06, 3F
→
04/25 00:08, 1年前 , 4F
他是用來評估演算法用來解決大型問題的可能性，也可以用來
04/25 00:08, 4F
→
04/25 00:09, 1年前 , 5F
評估當今天計算資源改善時，能夠獲得多少價值的模型；用你
04/25 00:09, 5F
→
04/25 00:10, 1年前 , 6F
的說法嗆回去，對方會覺得你導果為因吧？就是因為今天一段
04/25 00:10, 6F
→
04/25 00:10, 1年前 , 7F
程式，面對不同規模的資料量，以及跑在不同機器上所需要的
04/25 00:10, 7F
→
04/25 00:11, 1年前 , 8F
處理時間不同，才需要用他來分析呀…
04/25 00:11, 8F
→
04/25 00:30, 1年前 , 9F
你沒看懂我說的吧，我沒說範例那邊有問題，除此之外還有更
04/25 00:30, 9F
→
04/25 00:30, 1年前 , 10F
多可以納入討論的東西，如常數項、被忽略掉的內循環，還有
04/25 00:30, 10F
→
04/25 00:31, 1年前 , 11F
04/25 00:31, 11F
→
04/25 00:32, 1年前 , 12F
資料本身狀態等；你可以說他不代表實際執行的狀況優劣，但
04/25 00:32, 12F
→
04/25 00:32, 1年前 , 13F
他的確是用來評估跟分析演算法性能的數學模型...
04/25 00:32, 13F
→
04/25 00:49, 1年前 , 14F
04/25 00:49, 14F
→
04/25 00:51, 1年前 , 15F
建議你勇敢寄信去嗆 Steven Skiena
04/25 00:51, 15F
→
04/25 00:58, 1年前 , 16F
它確實可以做基礎效能評估啊，太鑽牛角尖只會適得其反
04/25 00:58, 16F
噓
04/25 01:16, 1年前 , 17F
就一句 scale 的問題還能說這麼長一篇也不簡單就是了
04/25 01:16, 17F
※ 編輯: NewSpec (223.137.208.9 臺灣), 04/25/2023 01:17:50
→
04/25 01:25, 1年前 , 18F
唉 可以吧，我的錯，就拿big O去評估效能唄
04/25 01:25, 18F
→
04/25 01:30, 1年前 , 19F
我上面的敘述，第四第五則推文是 Robert Sedgewick 書裡寫
04/25 01:30, 19F
→
04/25 01:31, 1年前 , 20F
的，上面截圖是 The Alogrithm Design Manual 的內容，文章
04/25 01:31, 20F
→
04/25 01:31, 1年前 , 21F
內容部分沒錯呀，但你說要嗆面試官的那條敘述是對的吧
04/25 01:31, 21F
→
04/25 01:33, 1年前 , 22F
04/25 01:33, 22F
→
04/25 01:34, 1年前 , 23F
教科書中都有提到這件事，而 Anany Levitin 有說在多數狀況
04/25 01:34, 23F
→
04/25 01:35, 1年前 , 24F
下，被乘的常數影響沒有這麼顯著。
04/25 01:35, 24F
噓
04/25 01:52, 1年前 , 25F
硬要琢磨理論感覺有點像在強詞奪理 實務上也不太會有
04/25 01:52, 25F
→
04/25 01:52, 1年前 , 26F
常數項差這麼多的演算法吧
04/25 01:52, 26F
‣ 更多 NewSpec 的文章
文章代碼(AID): #1aHg1EJZ (Soft_Job)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 7 之 8 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共8篇)
Soft_Job 近期熱門文章
更多 近期熱門文章 >>
PTT職涯區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 NewSpec 的文章
文章代碼(AID): #1aHg1EJZ (Soft_Job)