算法系列_基础01_O（nlogn）的理解

	前两天心血来潮买了两本书，打算补一下数据结构的基础，今天开张，就从O（xxx）的理解开始。

	讨论算法的时候会用到时间复杂度这个概念来衡量该算法，之前一直对O（n^2）、O（n）、O（nlogn）等写法一知半解，今天在《数据结构与算法分析-c语言描述》这本书中得到了答案，以后再看到，大写的O，就不会再有陌生感了。

1. 定义： 如果存在正常数c和n0使得当N>=n0时T（N）<=cf（N），则记为T（N）= O（f（N））；
反过来，记为T（N）= Ω（f（N））；如果不考虑等于的情况，即T（N）<cf（N），则记为T（N）= o（f（N））；

2.举例： T（N）= 100N；f（N）= N^2 ，n0=100且c=1，或者我们也可以让n0=10且c=10。因此，我们可以说100N= O（N^2），或者是T（N）= O（N^2）。

3.理解： 这个大O 的定义比较晦涩，通俗来讲，就是比较了两个函数的上升速度，只考虑N>0 ，然后一直变大，看N趋向无穷大时，T（N）大还是f（N）大，如果f（N）大（比如上面的例子，明显N>10000之后，N^2会大于100N ），则可以记为T（N）= O（N^2），表示f（N）是T（N）的上界。

4.类比： 说到比较两个函数的上升速度，那就回到了高数中的第一题，求极限。我们总能够通过计算极限 limT（N）/f（N）来确定这两个函数的相对增长率（洛必达法则又可以派上用场了）。
	极限是0，意味着T（N）= o（f（N））；极限是无穷大，意味着f（N）= o（T（N））；极限是常数c！=0，意味着他们的相对增长率一致。

5.加深理解： 应该注意到的是，不要说成T（N）<= O（f（N）），因为定义已经隐含有不等式了，写成T（N）<= O（f（N））是错误的，它没有意义。

	所以对于一个算法，说他的时间复杂度是O（N），表示的是f（N）= N ，且这个算法真正的时间复杂度T（N）=O（f（N）），即在N 趋向无穷大时，T（N）是以f（N）= N 为上界的，这个估算可能很粗略，但是以N为上界是肯定的。通过f（N）的描述，让我们知道了这个算法的T（N）大概的样子。