大O记法

C++的大O记法是算法的时间复杂度表达公式。简单的说大O记法可以告诉你一个算法耗费的时间长度同算法所处理的数据量大小的关系。大O记法只是一个概念性的或定性的记号，不能通过它来真正计算一个算法所耗费的精确时长。

O(1) 算法只花费一个单位时间长度的时间。同所处理的数据量大小没有关系（常量时间）。

       “一个单位时间长度”没有定义为1秒，1天，还是1微妙，完全随意指定。大约同处理一个数据项的时长相同。

       考虑一个数组，按照数组下标的到一个元素的引用

       int arr[100];

       int x = arr[88]; //这个算法就是O(1)的

       O(1)是最爽的，哪怕有1亿条数据还是1条数据，算法所费时间是常量。

 

O(N) 算法只花费N个单位时间长度的时间。数据量大小同算法所花费时长成正比例

       考虑一个list链表

       list.remove( 88 ); //把第88个元素删除。这个算法就是O(N)的

       O(N)是最不爽的，假设有1亿条数据，算法就要花费1亿个时间单位的时长。

 

O(logN) 算法只花费logN个单位时间长度的时间。

         logN是取对数，可以简单的理解为取以2为底数，N的对数。例如log65536=16 (因为2^16=65536)

         对数是把一个天文数字般的整数映射成一个小小的整数的数学工具。

         考虑一个已排序的数组，用“折半法”查找，算法的时间特性就是O(logN)的。

         O(log(一个亿))约等于19个单位时间的时长。

     O(logN)也不一定是以2为底的，也可能是以3为底的，这都无所谓。

 

算法在应用于局部小数据量时，可能因为内存的申请，释放，初始化等原因，观察者发现不符合大O记法表示的特性。

但是在长期的运行，经过大数据量的考验后，那些干扰因素逐渐沦为次要因素，观察者可以发现算法的却符合某种自己固有的时间特性。

 

后注：O记有组织罪案及三合会调查科，同大O记法没有关系

 

http://blog.sina.com.cn/s/blog_62b4e3ff0100v7aa.html