從網路課程 程式必修課!離散數學與演算法 來淺嚐一下沒機會在課堂上所學的離散數學與演算法。或許對撰寫程式的效能提昇會有些幫助。
課程相關資訊
[連結]:https://hiskio.com/courses/1196/lectures/133835
本篇範圍:Chapter 9
請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。
內容
給定集合 S 是定義域(Domain),有 m 個元素。集合 T 是對應域(Codomain),有 n 個元素。
函數:將每個 S 中的元素對應到 T 中的某個元素。
Onto 函數數量
條件:若 𝑚 >= 𝑛 才有可能存在 onto Function。
用 整體 扣除「不是滿射的函數」來計算。不是滿射的函數是指:存在至少一個 t∈T 沒有被 S 中任何元素對應。
算法:n^m – C(n,1) * ( n – 1 ) ^m + C(n,2)(n-2)^m – …… + (-1) ^ (n+1) C(n,n)(n-n)^m