章節連結
從網路課程 程式必修課!離散數學與演算法 來淺嚐一下沒機會在課堂上所學的離散數學與演算法。或許對撰寫程式的效能提昇會有些幫助。
課程相關資訊
[連結]:https://hiskio.com/courses/1196/lectures/133792
本篇範圍:Chapter 8
請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。
內容
Pigeonhile Principle
假定有多餘 K 數量的物品,要放在 K 個洞內,那一定有其中一個必然有一個以上的物品
於電腦科學中的應用,其中一個會是 Hash Table。若你採用 Hash Table 的資料結構,當你的資料量增大時,所需時間並不會大幅增加