時間復雜度

要求：只要高階項，不要低階項
常數操作：操作花費的時間和數據量無關，比如數組尋址，直接利用偏移量找到對應元素的位置；
非常數操作：比如list(鏈表)；查找元素需要遍歷鏈表，元素查找時間和元素對應的位置有關；時間復雜度為O(n)
常數時間操作：兩個數相加(+)? 相減(-) 左移(<<)? 右移(>>)?或運算(|) 與運算(&) 異或運算(^)?

例子? 選擇排序? 引出時間復雜度

package class01;import java.util.Arrays;public class Code01_SelectionSort {public static void selectionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < arr.length; j++) {minIndex = arr[j] < arr[minIndex] ? j : minIndex;}swap(arr, i, minIndex);}}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);selectionSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);selectionSort(arr);printArray(arr);}}

選擇排序：先從[0->N-1]范圍內找最小值，對于每個位置上元素的操作時間為c；再從[1->N-1]、[2->N-1]、[3->N-1]等，所以一共需要花費時間為((N)+(N-1)+(N-2)+? + (1))*c = (aN^2 + b*N + k)*c = acN^2 + bcN + kc 只要高階項，不要低階項，也不要高階項的系數,時間復雜度為N^2，即O(N^2)
一個操作如果和樣本數據量沒有關系，每次都是固定時間內完成的操作，叫做常數操作
表達式中，只要高階項，不要低階項，也不要高階項的系數，剩下的部分如果是f(N)，那么時間復雜度就是O(f(N))
評價一個算法的好壞，先看時間復雜度指標，然后分析不同數據樣本下的實際運行時間，也就是“常數項時間”?

冒泡排序

最差情況每個位置上元素都需要移動

package class01;import java.util.Arrays;public class Code02_BubbleSort {public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int e = arr.length - 1; e > 0; e--) {for (int i = 0; i < e; i++) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);}}}}public static void swap(int[] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);bubbleSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);bubbleSort(arr);printArray(arr);}}

插入排序

?時間復雜度按照最差情況計算
插入排序和數據情況有關，因此相較于冒泡排序和選擇排序會好

package class01;import java.util.Arrays;public class Code03_InsertionSort {public static void insertionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 1; i < arr.length; i++) {for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);}}}public static void swap(int[] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);insertionSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);insertionSort(arr);printArray(arr);}}

二分查找

每次都是找中點，比較數據，因此時間復雜度是? O(log2N)

在一個有序數組中，找某個數是否存在？二分查找

package com.example.algorithm.demo.class1;import java.util.Arrays;public class Code04_BSExist {public static boolean exist(int[] sortedArr,int num){if (sortedArr == null || sortedArr.length == 0){return false;}int L = 0;int R = sortedArr.length - 1;int mid = 0;while (L < R){mid = L +((R - L) >> 1);if (sortedArr[mid] == num){return true;} else if (sortedArr[mid] > num){R = mid - 1;} else {L = mid + 1;}}return sortedArr[L] == num;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static void printArray(int[] arr){for (int i = 0;i < arr.length;i++){System.out.print(arr[i] + " ");}}public static void main(String[] args) {int[] arr = {1,2,5,3,1,6,78,9,234,55,666,76};comparator(arr);printArray(arr);System.out.println();if (exist(arr,234)){System.out.println("存在數據！");} else {System.out.println("不存在數據！");}}
}

在一個有序數組中，找大于等于某個數最左側的位置？(進一步演化)

比如 1223334444555556666667777777

package com.example.algorithm.demo.class1;import java.util.Arrays;public class Code05_BSNearLeft {//在arr上 找到滿足>=value的最左位置public static int nearestIndex(int[] arr,int value){int L = 0;int R = arr.length - 1;int index = -1;while (L < R){int mid = L + ((R - L) >> 1);if (arr[mid] >= value){index = mid;R = mid - 1;} else {L = mid + 1;}}return index;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static void printArray(int[] arr){for (int i = 0;i < arr.length;i++){System.out.print(arr[i] + " ");}}public static void main(String[] args) {int[] arr = {1,23,4,5,5,5,6,7,7,8,8,8,8,2,1,2,4,5,3,1,6,78,9,234,55,666,76};comparator(arr);printArray(arr);System.out.println();System.out.println("元素7的位置索引是"+ (nearestIndex(arr,7)+1));}
}

額外空間復雜度

使用輔助數組，額外空間就不是O（1）

局部最小

要求：無序數組，相鄰不等，返回一個局部最小的位置，怎么整？
具體操作：1，先看0位置的元素，如果0位置小于1位置，那么直接返回1位置的元素；2，上一條件不滿足，即0位置元素大于1位置的元素，則看N-1位置的元素是否是局部最小，如果是直接返回。如果不是，則表明N-2位置的元素小于N-1位置的元素。表明0-1曲線下降，N-2? 到 N-1 曲線上升，表明在0->(N-1)絕對存在局部最小。數學知識
編碼：使用二分搜索，判斷局部最小；

原理

【0】<【1】，0是局部最小
【N-1】<【N-2】，N-1是局部最小
【i-1】<【i】<【i+1】，i是局部最小

方法

二分法，在0-N一定存在局部最小
二分不一定只能適用于有序數組，這個和題意有關。比如查找一個局部最小的數值

異或計算（無進位相加）

0異或N=N? N異或N=0
滿足交換律和結合律（具體操作和執行的次序無關）

完成數據的交換

引入第三方變量

int a = 1;
int b = 2;
int c = a;
a = b;
b = c;

單獨自身計算，不引入第三方變量

int a = 1;
int b = 2;
a = a + b; //a = 3
b = a - b; //b = 3 - 2 = 1
a = a - b; //a = 3 - 1 = 2

?使用異或（前提，值是一樣的，但是a和b所處的內存區域是不同的，如果相同會出錯）相同會導致數據抵消，二者都變成0

int a = 1;
int b = 2;
a = a 異或 b; //a = 1 異或 2，b = 2
b = a 異或 b; //a = 1 異或 2, b = 1
a = a 異或 b; //a = 1 異或 2 異或 1 = 2, b = 1即使a和b的元素都是2，也可以實現數據的交換，但是如果a和b指向相同的地址空間，會消除數據，a和b都變成0

錯誤使用?
i和j指向相同的位置，造成數據抹除

int[] arr = {4,5,3}
int i = 0;
int j = 0;arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];for(int c = 0; c < arr.length; c++){System.out.println(arr[c]);
}arr[0]=0;arr[1]=5;arr[2]=3;

1，一個數組中有一種數出現了奇數次，其他數都出現了偶數次，怎么找到這一個數?

public static void printOddTimesNum1(int[] arr){int eor = 0;for (int cur : arr){eor ^= cur;}System.out.println(eor);
}

只有一個是奇數項，將所有元素都異或，相同元素就會消失，只剩下奇數的元素，利用到了異或的交換律和結合律

2，一個數組中有兩種數出現了奇數次，其他數都出現了偶數次，怎么找到這兩個數例子

【1011，0110，0110，1011，1000，0001】
1，讓所有元素異或運算，得到eor變量，這個利用相同位置上1的個數，如果是奇數個，則為1，同理，偶數個1為0
2，第一步得到的eor=1001，因為eor的末尾元素為1，則將所有末尾為1的元素進行第二次異或，得到eor’，具體是【1011，1011，0001】，則eor'=0001，eor'也為第一個奇數個元素
3，將eor和eor'進行異或，eor=1001，eor'=0001，則二者計算得到1000為第二個奇數個的元素

引出新的問題?

上面例子中的eor=1001，我們提取最后面位置上的元素 1,是如何實現的呢？
例子（方法1）

01101000如何操作變成00001000呢？提取到指定位數的1，其余位數全部清零
假設 a = 01101000
1，計算 a-1,目的是打散最末尾的數字1，a-1 = 01100111
2，計算 a同或a-1 = 01100000，目的是清楚原始最右側的1
3，計算 a異或（a同或a-1）= 00001000

例子（方法2）

a & (~a +1)
a = 01101000, a取反得到10010111，再 +1 得到10011111
a & (~a +1) = 01101000 & 10011111 = 00001000
獲取最右邊的 1

步驟

?先將所有的元素進行異或，使用eor 得到奇數 a 和 b 的異或，即 eor = a ^ b;
將eor轉化為二進制，其中位置為1 的用于區別a 和 b；假設x位置上元素為1，將數組中元素x位置為1的全部進行異或得到eor‘；eor’ = a或者b
再將 eor和 eor‘ 異或得到另外一個元素

代碼

public static void printOddTimesNum2(int[] arr){int eor = 0;for (int i=0;i<arr.length;i++){eor ^= arr[i];//eor = a ^ b//err != 0//err必然有一個位置上是1int rightOne = eor & (~eor + 1);//提取出最右側的1int onlyOne = 0;//eor'for (int cur : arr){if((cur & rightOne) == 0){onlyOne ^= cur;}}}System.out.println(onlyOne + " " + (eor ^ onlyOne));
}

package class01;public class Code07_EvenTimesOddTimes {public static void printOddTimesNum1(int[] arr) {int eO = 0;for (int cur : arr) {eO ^= cur;}System.out.println(eO);}public static void printOddTimesNum2(int[] arr) {int eO = 0, eOhasOne = 0;for (int curNum : arr) {eO ^= curNum;}int rightOne = eO & (~eO + 1);for (int cur : arr) {if ((cur & rightOne) != 0) {eOhasOne ^= cur;}}System.out.println(eOhasOne + " " + (eO ^ eOhasOne));}public static void main(String[] args) {int a = 5;int b = 7;a = a ^ b;b = a ^ b;a = a ^ b;System.out.println(a);System.out.println(b);int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };printOddTimesNum1(arr1);int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };printOddTimesNum2(arr2);}}