界函式(bounding function)一種特殊函式。是時間或空間複雜性的限定函式。
基本介紹
- 中文名：界函式
- 外文名：bounding function
- 類型：特殊函式
- 釋義：時間或空間複雜性的限定函式
設M為一個算法，中為其一個複雜性測度.f為一元數論函式，若對任何字W，都有中(W)毛f(lW)，則稱f為M關於中的一個界函式.特別地，當中分別為時間和空間複雜性測度時，相應地稱f為M的時間界函式和空間界函式.
界函式的另一個含義是關於複雜性類的.設中某個複雜性測度，f為一元數論函式.若中(f)表示全體以f為中界函式的算法所接受的(計算的)語言(函式)類，則稱f為複雜性類中(f)的界函式，亦稱f為中(f)之名(參見“語言複雜類”、“函式複雜性類”).
