目錄

1.時間和空間復雜度

1.1時間復雜度

1.2空間復雜度

2.包裝類

2.1基本數據類型和對應的包裝類

2.2裝箱和拆箱

//阿里巴巴面試題

3.泛型

3.1擦除機制?

3.2泛型的上界

---

1.時間和空間復雜度

1.1時間復雜度

定義：一個算法所花費的時間與其語句的執(zhí)行次數成正比，算法中的基本操作的執(zhí)行次數，為算法的時間復雜度。

public class Main {public static void main(String[] args) {int n = 10;int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {count++; //F(n)=n^2}}for (int k = 0; k < 2*n; k++) {count++; //F(n)=2n}for (int m = 0; m < 10; m++) {count++; //F(n)=10}}
}

所以此時F(n)=n^2+2n+10，?但實際情況下只需要計算大概執(zhí)行次數，即——大O漸進法:

大O漸進法：

1> 用常數1代替所有的加法常數；

2> 只保留最高階項；

3> 如果最高階項存在且不是1，則去除與這個項相乘的常數。

例：F(n) = 2n^2 + 5n + 100?= O(n^2)

注意：

二分查找 O(n) = log2N

遞歸 O(n) = 遞歸的次數*每次遞歸后執(zhí)行的次數

public class Main {long factorial(int n) { //階乘return n<2?n:factorial(n-1)*n; //O(n)=n}long fibonacci(int n) { //菲波那切數列return n<2?n:factorial(n-1)+factorial(n-2); //O(n)=2^n}
}

拓展：平均復雜度

定義：所有情況下代碼執(zhí)行的次數累加起來，再除以所有情況數量，即為平均復雜度。

例如下述代碼，判斷x在循環(huán)中出現(xiàn)的位置，有n+1種情況：1<=x<=n 和?n<x，

所以平均復雜度為=（(1+2+3+……+n) + n）/ n+1

 public int Function(int n, int x){int sum = 0;for (int i = 1; i <= n; ++i){if (i == x)break;sum += i;}return sum;
}

1.2空間復雜度

定義：空間復雜度是一個算法在運行時臨時占用存儲空間大小的量度，即計算的是變量的個數。

public class Test {//實例1：使用了常數個額外空間，空間復雜度為O(1)//冒泡排序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：動態(tài)開辟了N個空間，空間復雜度為O(N)//菲波那切數列l(wèi)ong[] 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：遞歸調用了N次，開辟了N個棧幀，每個棧幀使用了常數個空間，空間復雜度為O(N)//階乘遞歸long factorial(int N) {return N < 2 ? N : factorial(N-1)*N;}
}

2.包裝類

2.1基本數據類型和對應的包裝類

基本數據類型	包裝類
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character
boolean	Boolean

2.2裝箱和拆箱

裝箱：基本類型——>包裝類型

拆箱：包裝類型——>基本類型

public class Test {public static void main(String[] args) {int a = 10;Integer i = a;//自動裝箱Integer ii = new Integer(a);//顯示裝箱Integer iii = new Integer(a);//顯示裝箱int m = i.intValue();//顯示拆箱float ff = i.intValue();//拆成對應的類型int fff = a;//自動拆箱}
}

//阿里巴巴面試題

public class Test {public static void main(String[] args) {Integer a = 127;Integer b = 127;Integer c = 128;Integer d = 128;System.out.println(a==b);//trueSystem.out.println(c==d);//false}
}

原因：裝箱時底層調用了valueOf方法，本質是一個范圍在-128~127之間的數組。

3.泛型

先來看看一道編程題，編程要求：創(chuàng)建一個可以存放任何類型數據的數組。

解：所有類的父類默認為Object類，所以可以創(chuàng)建一個Object數組用來存放不同類型的元素：

class MyArray {public Object[] objects = new Object[10];//創(chuàng)建Object類數組public Object getPos(int pos) {//訪問數組return objects[pos];}public void setVal(int pos,Object val) {//賦值數組objects[pos] = val;}
}
public class Test {public static void main(String[] args) {MyArray myArray = new MyArray();//此時可以將不同類型的元素放入數組中myArray.setVal(0,"123");myArray.setVal(1,10);//由于父類是Object類型，訪問時必須強制類型轉換int val = (int)myArray.getPos(1);System.out.println(val);//10}
}

我們發(fā)現(xiàn)上述代碼有些繁瑣，但用泛型來解這道題就會簡單可讀很多：?

定義：通俗來講，就是適用于許多許多類型，從代碼上講，就是對類型實現(xiàn)了參數化（傳遞類型）。

意義：在編譯時幫我們進行類型的檢查和轉換，注意在運行時沒有泛型這一概念，即JVM中沒有泛型。

語法：class 泛型類名稱 <類型形參列表> { 代碼塊?}

常見類型形參列表：E - Element、K - Key、V - Value、N - Number、T - Type、S/U/V等 - 第二、第三、第四個類型。

注意：不能new泛型類型的數組。

class MyArray <T> { //T是一個占位符，表示當前類是一個泛型類public T[] objects = (T[]) new Object[10];//這種寫法不是很好，改良版見下public T getPos(int pos) {return objects[pos];}public void setVal(int pos,T val) {objects[pos] = val;}
}
public class Test1 {public static void main(String[] args) {MyArray<Integer> myArray1 = new MyArray<Integer>();//指定類型為Integer myArray1.setVal(0,1);                //這里的Integer可不寫myArray1.setVal(1,2);int val = myArray1.getPos(1);System.out.println(val);//2MyArray<String> myArray2 = new MyArray<String>();//指定類型為StringmyArray2.setVal(0,"hello");         //這里的String可不寫myArray2.setVal(1,"world");String ret = myArray2.getPos(1);System.out.println(ret);//world}
}

3.1擦除機制?

定義：在編譯過程中，將所有的T替換為Object，這種機制稱為擦除機制。

編譯器生成的字節(jié)碼在運行期間并不包含泛型的類型信息。

class MyArray <T> {public Object[] objects =new Object[10];public T getPos(int pos) {return (T)objects[pos];//強轉}public void setVal(int pos,Object val) {objects[pos] = val;}
}

3.2泛型的上界

?寫一個泛型類，其中有個方法，用來求數組中的最大值：

class Alg<T extends Comparable<T>> { //擦除為一個實現(xiàn)了Comparable接口的類型public T findMax(T[] array) {    //即限制了T的邊界(上界)，使其為Comparable的子類或Comparable本身T max = array[0];for (int i = 1; i < array.length; i++) {if(max.compareTo(array[i]) < 0) {max = array[i];}}return max;}
}
class Alg2 {public static<T extends Comparable<T>> T findMax(T[] array) { //靜態(tài)泛型方法T max = array[0];for (int i = 1; i < array.length; i++) {if(max.compareTo(array[i]) < 0) {max = array[i];}}return max;}
}
public class Test {public static void main(String[] args) {Alg<Integer> alg = new Alg<>();Integer[] array = {1,9,3,7,5,4};Integer max = alg.<Integer>findMax(array);//此處Integer可不寫System.out.println(max);}public static void main2(String[] args) {Integer[] array = {1,9,3,7,5,4};Integer max = Alg2.<Integer>findMax(array);//此處Integer可不寫System.out.println(max);  //靜態(tài)方法通過類名調用}
}

---

這一點點只是開胃菜，后面還有更多有趣的知識等著我們去學習！

痛并快樂著捏?~ ~?