What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics
5 days ago
- #asymptotic notation
- #Kolmogorov complexity
- #Big O
- 本文讨论了形如$f(x) \le g(x) + O(1)$的渐近不等式，重点研究柯尔莫哥洛夫复杂度的界。
- 定义了标准大O记号$f(x) = O(g(x))$，表示存在常数$C$和临界点$x_0$，使得$x>x_0$时$f(x)$有界于$C|g(x)|。
- 表达式$f(x) = g(x) + O(1)$解释为$f(x) - g(x) = O(1)$，意味着$f(x)$与$g(x)$的差有常数界。
- 文章阐释了$f(x) \le g(x) + O(1)$的形式定义，强调其仅提供单向上界，不同于标准大O的双向界。
- 明确指出$f(x) = g(x) + O(1)$蕴含$f(x) \le g(x) + O(1)$，但反之未必成立。