一、复杂度经典例子分析

1、计算时间复杂度分析

时间复杂度规则：

• 用1取代常数
• 只保留最高阶项
• 去掉最高阶项的系数

题1：O(N+M)，循环

// 计算func3的时间复杂度
void func3(int N, int M) {int count = 0;for (int k = 0; k < M; k++) {count++;}for (int k = 0; k < N ; k++) {count++;}System.out.println(count);
}

题2：O(N^2)，冒泡排序

// 计算bubbleSort的时间复杂度
void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}
}

分析：

题3：O(logN)，二分查找

// 计算binarySearch的时间复杂度
int binarySearch(int[] array, int value) {int begin = 0;int end = array.length - 1;while (begin <= end) {int mid = begin + ((end-begin) / 2);if (array[mid] < value)begin = mid + 1;else if (array[mid] > value)end = mid - 1;elsereturn mid;}return -1;
}

分析：

题4：O(N)，阶乘递归

注意：递归算法的时间复杂度 = 递归次数

// 计算阶乘递归factorial的时间复杂度
long factorial(int N) {return N < 2 ? N : factorial(N-1) * N;
}

题5：O(2^N)，斐波那契递归(满二叉树)

// 计算斐波那契递归fibonacci的时间复杂度
int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

2、空间复杂度分析

空间复杂度规则：计算变量的个数，而不是占用内存大小

题1：O(1)，冒泡排序

解释: 使用了常数个额外空间，所以空间复杂度为 O(1)

// 计算bubbleSort的空间复杂度
void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}
}

题2：O(N)，斐波那契循环

解释: 动态开辟了N个空间，空间复杂度为 O(N)

// 计算fibonacci的空间复杂度
int[] fibonacci(int n) {long[] fibArray = new long[n + 1];fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; i++) {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray;
}

题3：O(N)，阶乘递归，斐波那契递归

解释：从开始调用递归到最远距离的这一路径递归了N次。
阶乘递归：很好理解，它调用了n次
斐波那契递归：开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)
斐波那契递归空间复杂度： 斐波那契递归归的时候，销毁了这一层函数的栈帧，回到上一层，因此只算从开始到最远的距离，而不像时间复杂度那样累加。

阶乘递归：

// 计算阶乘递归factorial的空间复杂度
long factorial(int N) {return N < 2 ? N : factorial(N-1) * N;
}

斐波那契递归：

//计算斐波那契递归fibonacci的空间复杂度
int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

二、复杂度习题

题1：消失的数字

链接：
LeetCode 面试题 17.04.消失的数字

法一：求和

class Solution {public int missingNumber(int[] nums) {//法一：求和int nsum = 0;int numsum = 0;for(int i=0; i<= nums.length; i++) {nsum += i;}for(int i=0; i<nums.length; i++) {numsum += nums[i];}return nsum - numsum;}}

法二：异或

class Solution {public int missingNumber(int[] nums) {//法二：异或int t = 0;for(int i=0; i<nums.length; i++) {t ^= nums[i];}for(int i=0; i <= nums.length; i++) {t ^= i;}return t;}
}

法三：空间换时间

class Solution {public int missingNumber(int[] nums) {//法三：以空间换时间。int[] ret = new int[nums.length+1];Arrays.fill(ret,-1);for(int i=0; i<nums.length; i++) {ret[nums[i]] = nums[i];}for(int i=0; i <= nums.length; i++) {if(ret[i] == -1) {return i;}}return -1;}
}

题2：轮转数组

链接：
LeetCode189.轮转数组

法一：空间换时间

class Solution {public void rotate(int[] nums, int k) {//法二：开辟新空间，以空间换时间int cnt=0;k %= nums.length;int[] newnums = new int[nums.length];//注意1：将原数组的数据按照移动后的顺序放入新数组for(int i=nums.length-k; i<nums.length; i++) {newnums[cnt++] = nums[i];}for(int i=0; i<nums.length-k; i++) {newnums[cnt++] = nums[i];}//注意2：把新开辟的数组里的值拷贝回原来数组for(int i=0; i<nums.length; i++) {nums[i] = newnums[i];}}
}

法二：逆置三次

逆置分析:

旋转数组代码:

class Solution {public void rotate(int[] nums, int k) {//法三：利用逆置解决。两次小逆置，一次大逆置k %= nums.length;reverse(nums, 0 , nums.length-k-1);reverse(nums, nums.length-k, nums.length-1);reverse(nums, 0, nums.length-1);}public static void reverse(int[] nums, int left, int right) {while(left<=right){int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;left++;right--;}}
}

法三：循环换位(不可取)

class Solution {public void rotate(int[] nums, int k) {//法一：循环换位,世界复杂度为O(n*k)=>O(n^2),超过时间限制，不可取。k %= nums.length;while(k>0) {int i = 0;int tmp = nums[nums.length-1];for(i=nums.length-1; i > 0; i--) {nums[i] = nums[i-1];}nums[i] = tmp;k--;}}
}