目錄
1.時間和空間復(fù)雜度
1.1時間復(fù)雜度
1.2空間復(fù)雜度
2.包裝類
2.1基本數(shù)據(jù)類型和對應(yīng)的包裝類
2.2裝箱和拆箱
//阿里巴巴面試題
3.泛型
3.1擦除機制?
3.2泛型的上界
1.時間和空間復(fù)雜度
1.1時間復(fù)雜度
定義：一個算法所花費的時間與其語句的執(zhí)行次數(shù)成正比，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復(fù)雜度。
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í)行次數(shù)，即——大O漸進法:
大O漸進法：
1> 用常數(shù)1代替所有的加法常數(shù)；
2> 只保留最高階項；
3> 如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)。
例：F(n) = 2n^2 + 5n + 100?= O(n^2)
注意：
二分查找 O(n) = log2N
遞歸 O(n) = 遞歸的次數(shù)*每次遞歸后執(zhí)行的次數(shù)
public class Main {
long factorial(int n) { //階乘
return n<2?n:factorial(n-1)*n; //O(n)=n
}
long fibonacci(int n) { //菲波那切數(shù)列
return n<2?n:factorial(n-1)+factorial(n-2); //O(n)=2^n
}
}拓展：平均復(fù)雜度
定義：所有情況下代碼執(zhí)行的次數(shù)累加起來，再除以所有情況數(shù)量，即為平均復(fù)雜度。
例如下述代碼，判斷x在循環(huán)中出現(xiàn)的位置，有n+1種情況：1<=x<=n 和?n<x，
所以平均復(fù)雜度為=（(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空間復(fù)雜度
定義：空間復(fù)雜度是一個算法在運行時臨時占用存儲空間大小的量度，即計算的是變量的個數(shù)。
public class Test {
//實例1：使用了常數(shù)個額外空間，空間復(fù)雜度為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個空間，空間復(fù)雜度為O(N)
//菲波那切數(shù)列
long[] 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：遞歸調(diào)用了N次，開辟了N個棧幀，每個棧幀使用了常數(shù)個空間，空間復(fù)雜度為O(N)
//階乘遞歸
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}
}
2.包裝類
2.1基本數(shù)據(jù)類型和對應(yīng)的包裝類
| 基本數(shù)據(jù)類型 |
包裝類 |
|---|---|
| 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();//拆成對應(yīng)的類型
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);//true
System.out.println(c==d);//false
}
}原因：裝箱時底層調(diào)用了valueOf方法，本質(zhì)是一個范圍在-128~127之間的數(shù)組。
3.泛型
先來看看一道編程題，編程要求：創(chuàng)建一個可以存放任何類型數(shù)據(jù)的數(shù)組。
解：所有類的父類默認為Object類，所以可以創(chuàng)建一個Object數(shù)組用來存放不同類型的元素：
class MyArray {
public Object[] objects = new Object[10];//創(chuàng)建Object類數(shù)組
public Object getPos(int pos) {//訪問數(shù)組
return objects[pos];
}
public void setVal(int pos,Object val) {//賦值數(shù)組
objects[pos] = val;
}
}
public class Test {
public static void main(String[] args) {
MyArray myArray = new MyArray();
//此時可以將不同類型的元素放入數(shù)組中
myArray.setVal(0,"123");
myArray.setVal(1,10);
//由于父類是Object類型，訪問時必須強制類型轉(zhuǎn)換
int val = (int)myArray.getPos(1);
System.out.println(val);//10
}
}
我們發(fā)現(xiàn)上述代碼有些繁瑣，但用泛型來解這道題就會簡單可讀很多：?
定義：通俗來講，就是適用于許多許多類型，從代碼上講，就是對類型實現(xiàn)了參數(shù)化（傳遞類型）。
意義：在編譯時幫我們進行類型的檢查和轉(zhuǎn)換，注意在運行時沒有泛型這一概念，即JVM中沒有泛型。
語法：class 泛型類名稱 <類型形參列表> { 代碼塊?}
常見類型形參列表：E - Element、K - Key、V - Value、N - Number、T - Type、S/U/V等 - 第二、第三、第四個類型。
注意：不能new泛型類型的數(shù)組。
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);//2
MyArray<String> myArray2 = new MyArray<String>();//指定類型為String
myArray2.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];//強轉(zhuǎn)
}
public void setVal(int pos,Object val) {
objects[pos] = val;
}
}3.2泛型的上界
?寫一個泛型類，其中有個方法，用來求數(shù)組中的最大值：
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)方法通過類名調(diào)用
}
}這一點點只是開胃菜，后面還有更多有趣的知識等著我們?nèi)W(xué)習！文章來源：http://www.zghlxwxcb.cn/news/detail-436403.html
痛并快樂著捏?~ ~?文章來源地址http://www.zghlxwxcb.cn/news/detail-436403.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】復(fù)雜度&包裝&泛型的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
