### 概述
* O(1)
* O(n)
* O(lgn)
* O(nlogn)
* O(n^2)
简单(不是严格的意义)大O描述的是算法的运行时间和输入数据之间的关系. 大O翻译成中文应该叫做**渐进时间复杂度**.渐进表现在"描述n趋近于无穷的情况"
### O(n)的时间复杂度
底下这个例子的时间复杂度是O(n)的,为什么说它是O(n)的呢?n是nums中的元素个数. 这个算法运行的时间大小是和nums中元素呈线性关系的. 这个线性关系就表现在这个n是一次方,它不是O(n方),O(n立方)的.
为什么要用大O,叫做O(n)? 因为它忽略了很多常数 . 实际时间**T = c1*n + c2**
~~~
public static int sum(int[] nums)
{
int sum = 0;
for(int num : nums) sum += num;
return sum;
}
~~~
* T = 2*n + 2 //O(n)
* T = 2000*n + 10000 //O(n) 不要看这个数值很大,它也是O(n)的
* T = 1*n*n+0 //O(n^2) 描述n趋近于无穷的情况
* T = 2*n*n + 300n + 10 //O(n^2) 300n低阶项被忽略掉,因为当n趋近于无穷的时候,这个低阶项起到的作用太小了
### 分析动态数组的时间复杂度
#### 添加操作
通常在分析的时候要考虑最坏的情况来进行分析
* addLast(e) //O(1)
* addFirst(e) //O(n)
* add(index e) //O(n/2) = O(n) 严格计算需要一些概率论知识
#### 删除操作
* removeLast(e) //O(1)
* removeFirst(e) //O(n)
* remove(index,e) //O(n/2) = O(n)
* resize() //O(n)
#### 修改操作
* set(index,e) //O(1)
#### 查询操作
* get(index) //O(1)
* contains(e) //O(n)
* find(e) //O(n)
### 分析动态数组操作
* 增 : O(n)
* 删 : O(n)
* 改 : 已知索引O(1);未知索引O(n)
* 查 : 已知索引O(1);未知索引O(n)
