1.概念

概念

Data structure：数据结构是用一种特殊的方式组织（排列）和存储数据的一种容器。
Algorithms: 算法是用一些特定的方法从input data中计算出你想要的output data。
抽象的来讲，数据结构就是一种数据容器，算法就是操作数据的过程。

常见的数据结构

Array 数组
Stack 栈
Queue 队列
Linked List 链表
Tree 树
Heap 堆
Graph 图
Hash table 哈希表

常见算法

Selection sort
Merge sort
Quick sort
Bubble sort
Bucket sort
Patient sort
Smooth sort
Cocktail sort
... ...

Algorithms complexity 算法复杂度

time complexity 时间复杂度
space complexity 空间复杂度

因为计算机硬件配置各不相同,同一段算法在各硬件上的执行时间也会不同，所以并不能单纯的使用精确的时间值或内存大小来表示算法的时空复杂度，so科学家们发明了一种对算法复杂度的衡量标准使用大O符号来标识衡量算法的性能。简单点说就是随着输入的数据规模的增长算法的运算次数的增长速率是以什么样数学模型在增长来表达算法的复杂度，而不需要去关心具体的细节。

eg.

void fun(){
  int[] arr = new [n]{1,2,3,4,5,6...};
  for(int i=0;i<arr.length;i++){
    System.out.println(arr[i]);
  }
}

先简单的理解，上面的for 循环System.out.println(arr[i]);执行了n次，当
arr.length=n时，时间复杂度就是O(n);
空间复杂度就是为了表示除了必须要用到的内存空间以外还需要用到的额外内存空间有多大，
以上例子除了必须用到的arr数组外并没有使用其他内存空间所以空间复杂度是O(1)，如果用了额外的内存空间如下，
void fun(){
  int[] arr = new [n]{1,2,3,4,5,6...};
  for(int i=0;i<arr.length;i++){
    System.out.println(arr[i]);
  }
  int[] arr1 = new [n];
  System.out.println(arr1.length);
}
那么空间复杂度就会变为O(n)。

为什么要进行算法复杂度分析？

预测算法所需的资源
- CPU消耗
- 内存空间
预测算法的运行时间
- 在给定输入规模时，所执行的基本操作数量。
比较算法之间的优劣
- 找出相同的问题的多种解决方案中的最优解

常见的算法复杂度

O(1)<O(log10(n))=O(log2(n))<sqrt(n)<n<nlogn<n^2<n3<2^n<10n<n!<n^n（省略O符号）

复杂度的比较

Limt n->inf f(n)/g(n)=k!=0,有两个复杂度f(n)和g(n) 当n趋向于无穷大的时候，如果f(n)/g(n)的结果恒等于一个不为0的常数，那么就认为f(n)与g(n)的复杂度是一样的；当n趋向于无穷大的时候，如果f(n)/g(n)的结果趋向于0，那么就认为g(n)的复杂度高于f(n);*当n趋向于无穷大的时候，如果f(n)/g(n)的结果趋向于无穷大，那么就认为f(n)的复杂度高于g(n)。

概念