【Java数据结构】时间和空间复杂度

       本章开始将进入数据结构的知识，时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，。

时间复杂度

算法中执行的次数决定了时间复杂度。

在计算执行次数时，只需要计算大概的次数，即称为大O的渐进表示法，以下是大O的渐进表示法计算执行次数时要注意的点： 

1. 用常数1取代运行时间中所有加法常数；例：5 -》O(1)
2. 运行次数是一个函数时，只保留最高阶项；例：n^2+2n+1 -》 O(n^2)
3. 如果最高阶项存在且不是1，就去除项的常数；例：2n -》O(n)

举几个例子更能了解时间复杂度：

第一个例子：

	public static void func1(int n) {int count = 0;for(int i = 0; i < 2*n; i++) {count++;}int m = 10;while(m-->0) {count++;}System.out.println(count);}

上面这个例子的时间复杂度是O(n)；为什么呢？我现在就来说说：

       首先执行第一个循环for循环，它的时间复杂度是2n；然后就是进入第二个循环whlie循环，它的复杂度是10；然后这个程序就走完了，总的复杂度是2n+10。那为什么是n呢？ 就是因为大O的渐进表示法，常数次数为1，所以就是2n+1，但是1与2n相比没有什么区别，那就是2n，表示法中表明系数可去除，所以综合下来就为n啦！！！

第二个例子：冒泡排序法 

	public static void bubbleSort(int[] array) {for(int i = 0; i < array.length; i++) {for(int j = 0; j < array.length - 1; j++) {if(array[j] > array[j+1]) {int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}}}

       在冒泡排序中，有最好的情况也有最坏的情况，最好是这个排序以及符合排序，那只需要走一遍就可以即复杂度是O(N)；最坏情况就是内外层循环都要执行以次，那就是n*(n-1)次，根据大O渐进表示法复杂度为O(N^2)。

第三个例子：二分查找

	public static int binarySearch(int[]array, int search) {int begin = 0;int end = array.length;while(begin < end) {int mid = begin +(end -begin)/2;if (array[mid] < search)begin = mid + 1;else if (array[mid] > search)end = mid - 1;else return mid;}return -1;}

二分查找的时间复杂度是O(log N)；怎么计算的呢 ？

       假设该数组有N个元素，第一次查找元素个数减去一半（N/2），第二次又减去一半（N/2^2），第k次时就只剩一个元素了那么就有N/2^k = 1，就得到log N（2不写，默认为2）。

第四个例子：阶乘递归

	public long factorial(int N) {return N < 2 ? N : factorial(N - 1) * N;}

       递归的复杂度 = 递归的次数 * 每次递归执行的次数，大概意思就是递归一次套一次套了多少次那就是递归得次数，套一次中里面执行的次数就是每次地柜执行的次数。所以上面例子的复杂度是N*1次，即O(2^N)。

        斐波那契数列的复杂度是O(2^N)，它是一个一分二，二分四，四分八等等将其累加起来就是2^N次。

常见的复杂度：O(1) < O (log N) < O(N * log N) < O (N^2)

空间复杂度

       空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。开辟了几个空间复杂度就是几，为常数时复杂度是O(1)。

例如冒泡排序，它创建了3个变量（i， j , temp）所以复杂度是O(1)；阶乘递归，它每次调用一次方法也需要开辟一次空间，所以它的空间复杂度是O(N)；