什么是算法的大O表示法 _大O表示法

做了这么多年的程序员，是不是一直靠着自己的聪明伶俐在编码，数据结构和算法是前辈们的心血和经验总结，不可错过。
数据结构是利用其存储结构和逻辑结构来有效地组织数据，比如线性的表、栈、队列，非线性的树、图等，而算法是描述运算的过程，良好的算法是建立在有效的数据结构之上的。
评价算法的指标评价一个算法的好坏，除了他正确性指标外，就是所消耗的时间和空间。
为了方便计算所消耗的时间，需要先作2个假设：

算法与计算机的软硬件无关（硬件好理解，软件比如编程语言、执行器、编译器等）；代码中的每个语句所消耗的时间都一样，记作一个时间单位；

举个例子

for (int i = 0; i < n; i++) { //①  for (int j = 0; j < n; j++) { //②    c[i][j] = 0; //③    for (int k = 0; k < n; k++) { //④      c[i][j] = a[i][k] + b[k][j] + c[i][j]; //⑤    }  }}

计算它所消耗时间的过程如下

语句①需要循环到i=n时才会完结，所以它耗费n+1个时间单位；
语句②同语句① ，自己的的循环中耗费n+1个时间单位，但它在①的n次循环体内，所以消耗n*(n+1)个时间单位；
语句③在语句①②循环体内，它们分别循环n次，所以语句③消耗n*n个时间单位；
语句④同③ ，但它本身执行n+1 ，所以语句④消耗n*n*(n+1)个时间单位；
语句⑤在语句①②④循环体内，它消耗n*n*n个时间单位；

所以总体消耗的时间为：n+1 + n*(n+1) + n*n+n*n*(n+1)+n*n*n=2n3+3n2+2n+1；
算法的时间复杂度上例最终消耗的时间可以用函数表示：T(n)=2n3+3n2+2n+1 ，但用这么长的算式评价算法的好坏过于繁冗。实际上它是变量n的函数，表示随着n的增大影响着T(n)的增长率变化，化繁为简可进一步抽象为n的量级函数：T(n)=O(f(n) 。T(n)=2n3+3n2+2n+1的最大量级是n3 ，因此可简化为T(n)=O(n3) ，这就大O表示法。
计算机科学经常用大O表示算法的复杂度或衡量性能，它主要用于描述在最坏的情况下所花费的时间和空间(内存或磁盘) 。
为了更形象，下面列举几个例子，根据计算消耗时间的方法很容易得出结果。
O(1)O(1)表示算法的执行总是消耗相同的时间，比如
boolean isFirstElementEmpty(List<String> elements){ return elements.get(0).isEmpty();}O(n)O(n)表示算法的复杂度是线性增长的，与数据集的大小成正比。

boolean ContainsValue(List<String> elements, String value) {  for (String element : elements) {    if (element.equals(value)) return true;  }  return false;}

如果不用foreach ，使用for会更直观些

boolean ContainsValue(List<String> elements, String value) {  int n = elements.size();  for (int i = 0; i < n; i++) {    if (elements.get(i).equals(value)) return true;  }  return false;}

它是消耗时间单位算式是1+n+1+n+1=2n+3 ，根据n的量级简化为大O表示即O(n) 。
O(n2)O(n2)表示算法的复杂度与数据集大小的平方成正比，一般的循环嵌套就是这种，随着嵌套的层级增加可能是O(n3)、O(n4)等。

boolean ContainsDuplicates(List<String> elements) {  for (int i = 0; i < elements.size(); i++) {    for (int j = 0; j < elements.size(); j++) {      if (i == j) continue;      if (elements.get(i).equals(elements.get(j))) return true;    }  }  retrn false;}

O(2n)O(2n)表示算法的复杂度与数据集大小成指数增长，比如递归