大O记号和小o记号这两天我一直在纠结于一个问题，就是o(f(x))和O(f(x))到底代表什么？究竟是一个函数的**，还是别的什么东西。经过漫长的GOOGLE和思考，我有了一点关于这两个记号的想法。o(f(x))，和O(f(x))虽然只是数学记号，但这些记号究竟是什么意思，我们还是要想清楚。按我的理解，o(f(x))是一个函数，只不过我们只知道关于他的一个信息:o(f(x))/f(x)=0 (x->a)这样很多事情就可以说清楚了。因为o(f(x))是一个函数，所以含有它的代数式进行加减乘除之类的运算都没有问题。这样我们可以解释这个问题：x=o(x^2), 2x=o(x^2) ->x=2x这是不对的，因为两个等式里的o(x^2)，并不见得是同一个函数，o(x^2)有很多个，比如x+1,x+2...，他们并不见得相等。所以上面x=2x的推理是不正确的。最后再谈谈计算机界中的大O记号，它通常用来进行算法复杂度的估计。比如说快速排序的平均时间复杂度是O(nlogn)（计算机界logn默认是以2为底的对数），即输入规模是n（也就是输入n个数），计算次数会是knlogn，多半k是1，否则如果k很大，那么这个估计就没有多大意义。因为我们通常是通过算法的时间复杂度来获知算法效率，在O(n)的算法和O(n!)的算法之间，我们肯定选O(n)，不过如果O(n)的算法的准确复杂度是100000！*n，我们肯定不用它——虽然他也是线性的算法。所以说计算机界的大O在实际意义上与数学中的大O还是有区别的，在《离散数学及其应用》中计算机界的大O被指被普遍的误用，但这不影响我们读懂使用大O记号的人的意思。