PTT推薦

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

NewSpec 發表於 2023/4/24 下午11:29:16
看板Soft_Job標題Re: [討論] 技術總監有可能不懂BFS嗎??作者
NewSpec
 (新規格)時間推噓 推:2 噓:2 →:22

看到這個可以聊一下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 留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.208.9 (臺灣)
※ PTT 網址
推

qwe7030204/24 23:36n要夠大比級數才有意義，不然常數的影響也要考慮進去

推

MyNion04/24 23:43不同的scale下效能不一定一樣，實際跑Benchmark較為穩當

→

Hsins04/25 00:06嗆回去不知道會不會適得其反？

→

Hsins04/25 00:08他是用來評估演算法用來解決大型問題的可能性，也可以用來

→

Hsins04/25 00:09評估當今天計算資源改善時，能夠獲得多少價值的模型；用你

→

Hsins04/25 00:10的說法嗆回去，對方會覺得你導果為因吧？就是因為今天一段

→

Hsins04/25 00:10程式，面對不同規模的資料量，以及跑在不同機器上所需要的

→

Hsins04/25 00:11處理時間不同，才需要用他來分析呀…

→

Hsins04/25 00:30你沒看懂我說的吧，我沒說範例那邊有問題，除此之外還有更

→

Hsins04/25 00:30多可以納入討論的東西，如常數項、被忽略掉的內循環，還有

→

WashFreeID04/25 00:31https://i.imgur.com/nx3bNOQ.jpg
→

Hsins04/25 00:32資料本身狀態等；你可以說他不代表實際執行的狀況優劣，但

→

Hsins04/25 00:32他的確是用來評估跟分析演算法性能的數學模型...

→

Hsins04/25 00:49https://i.imgur.com/fd0Y5Hc.png

→

Hsins04/25 00:51建議你勇敢寄信去嗆 Steven Skiena

→

happy864904/25 00:58它確實可以做基礎效能評估啊，太鑽牛角尖只會適得其反

噓

j095832208004/25 01:16就一句 scale 的問題還能說這麼長一篇也不簡單就是了

※ 編輯: NewSpec (223.137.208.9 臺灣), 04/25/2023 01:17:50
→

NewSpec04/25 01:25唉 可以吧，我的錯，就拿big O去評估效能唄

→

Hsins04/25 01:30我上面的敘述，第四第五則推文是 Robert Sedgewick 書裡寫

→

Hsins04/25 01:31的，上面截圖是 The Alogrithm Design Manual 的內容，文章

→

Hsins04/25 01:31內容部分沒錯呀，但你說要嗆面試官的那條敘述是對的吧

→

Hsins04/25 01:33https://i.imgur.com/8P8Z8sS.png
→

Hsins04/25 01:34教科書中都有提到這件事，而 Anany Levitin 有說在多數狀況

→

Hsins04/25 01:35下，被乘的常數影響沒有這麼顯著。

噓

chchan111104/25 01:52硬要琢磨理論感覺有點像在強詞奪理 實務上也不太會有

→

chchan111104/25 01:52常數項差這麼多的演算法吧
同系列文章
[討論] 技術總監有可能不懂BFS嗎??
其他人也閱讀了
PTT 熱門相關