認識時間復雜度
常數(shù)時間的操作：一個操作如果和數(shù)據(jù)量沒有關(guān)系矮烹，每次都是固定時間內(nèi)完成的操作罐呼，這叫常數(shù)操作捣染，如加減乘數(shù)，數(shù)組的尋址操作
時間復雜度作為一個算法流程中斟薇，常數(shù)操作數(shù)量的指標师坎。常用O（讀作big O）來表示。具體來說堪滨，在常數(shù)操作數(shù)量的表達式中胯陋，只要高階項，不要低階項椿猎，也不要高階項的系數(shù)惶岭，剩下的部分如果記為f(N),那么時間復雜度為O(f(N))。
評價一個算法流程的好壞犯眠，先看時間復雜度的指標，然后再分析不同數(shù)據(jù)樣本下的實際運行時間症革，也就是常數(shù)項時間筐咧。
額外復雜空間O(1)
完成一個算法時，如無序數(shù)組的排序噪矛，除了給出的數(shù)組本身的內(nèi)存空間量蕊，完成這個數(shù)組排序如需要新建一個數(shù)組輔助完成本次排序，新建的數(shù)組所占的內(nèi)存空間稱為額外復雜空間艇挨，如新建的數(shù)組長度為n残炮，則額外復雜空間為O(n),以此類推。
對數(shù)器
當我們設(shè)計一個算法時缩滨，并不能準確的驗證該算法的正確性势就，此時，我們可以借助對數(shù)器這個方法脉漏，可以很大效率的幫助我們驗證自己算法的準確度苞冯。這無疑對我們是一個很大的幫助。什么是對數(shù)器呢侧巨？
對數(shù)器的概念和使用
0舅锄、有一個你想要測的方法a。
1司忱、實現(xiàn)一個絕對正確但是復雜度不好的方法b皇忿。
2、實現(xiàn)一個隨機樣本產(chǎn)生器坦仍。
3鳍烁、實現(xiàn)對比的方法。
4桨踪、把方法a和方法b對比很多次來驗證方法a是否正確老翘。
5、如果有一個樣本使得對比出錯，打印樣本分析是哪個方法出錯铺峭。
6墓怀、當樣本數(shù)量很多時對測試依然正確，可以確定方法a已經(jīng)正確卫键。
常見的排序方法
- 冒泡排序
public class Code_BubbleSort {
public static void bubbleSort(int [] arr) {
for(int i=0;i<arr.length;i++) {
if(arr == null || arr.length<2) {
return ;
}
for(int j=1;j<arr.length-i;j++) { //每次遍歷都將最大的元素排到最后
if(arr[j-1]>arr[j]) {
swap(arr,j-1,j);
}
}
}
}
public static void swap(int []arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
分析：冒泡算法是常見的排序算法之一傀履，排序簡單，時間復雜度為O(n*n),對于大量的數(shù)據(jù)集不建議采用冒泡排序算法
- 選擇排序
選擇排序是將相鄰的兩個元素進行比較莉炉，找到元素最小的下標钓账，進行數(shù)據(jù)交換。
public class Code_SelectSort {
public static void selectSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
for(int i=0;i<arr.length;i++) {
int minIndex = i;
for(int j = i+1;j<arr.length;j++) {
if(arr[j]<arr[minIndex]) {
minIndex = j;
}
if(minIndex != i) {
swap(arr, i, minIndex);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
分析：時間復雜度為O(n * n),在現(xiàn)在的大部分架構(gòu)設(shè)計或者是業(yè)務邏輯中很少用到選擇排序算法了
- 插入排序
插入排序也是一種常見的排序方法絮宁，相對于冒泡排序和選擇排序梆暮，插入排序在排序過程中，依次選擇待排序元素與排序好的元素進行對比绍昂，如果小于當前元素及前面的元素啦粹，則將該元素插入到指定的位置。是一種比較抽象的排序方法
public class Code_InsertSort {
public static void insertSort(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) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
分析:時間復雜度為O(n * n),雖然比較抽象唠椭，但是插入排序還是會被經(jīng)常運用于實現(xiàn)于數(shù)據(jù)排序的業(yè)務邏輯中
使用對數(shù)器來驗證插入排序的正確性
public class TestInsertSort {
//正確方法
public static void rightMethod(int [] arr) {
Arrays.sort(arr);
}
// 產(chǎn)生隨機的數(shù)組
public static int [] generateRandomArray(int size, int value) {
int [] arr = new int[(int)((size + 1) * Math.random())];
for(int i=0; i<arr.length; i++) {
arr[i] = (int) ((value + 1) * Math.random() - (int)(value * Math.random()));
}
return arr;
}
// 復制數(shù)組
public static int[] copyArray(int [] arr) {
if(arr == null) {
return null;
}
int [] array = new int[arr.length];
for(int I=0;i<arr.length;i++) {
array[I] = arr[i];
}
}
//插入排序
public static void insertSort(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) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 判斷兩個數(shù)組是否相等
public static boolean isEquals(int []arr1, int []arr2) {
if( (arr1 == null && arr2 !=null) || (arr1 != null && arr2 == null)) {
return false;
}
}
if(arr1 == null && arr2 == null) {
return false;
}
if(arr1.length != arr2.length) {
return false;
}
for(int i=0;i<arr1.length;i++) {
if(arr1[i] == arr2[I]) {
return true;
}
}
return false;
}
public static void display(int [] arr) {
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+ " ");
}
System.out.println("");
}
public static void main(String []args) {
int testTime = 50000;
int size = 10;
int value = 100;
boolean succeed = true;
for(int i=0; i<testTime;i++) {
int [] arr1 = generateRandomArray(size,value);
int [] arr2 = copyArray(arr1);
int [] arr3 = copyArray(arr1);
insertSort(arr1);
rightMethod(arr2);
if(!isEquals(arr1,arr2)) {
succeed = false;
display(arr3);
break;
}
}
System.out.printLn(succeed ? "Nice": "What the Fuck");
}
}
