可忽略方程(negligible function)

Definition: We call a function μ: N⟶R negligible if for every positive polynomial p() there exists an N such that for all n > N, we have n(n) < 1/p(n).

e.g. functions 2^{-n^{1/2}} and n^{-log_2 n} are negligible.

Theorem: For any negligible function μ and any polynomial p, the function μ'(n)≝p(n)・μ(n) is also negligible

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容