数据结构知识点1

目次

一、时间复杂度和空间复杂度
1.1时间复杂度：
1.2空间复杂度：
二、装箱和拆箱
三、泛型
3.1泛型类的使用：
3.2泛型的上界：
3.3泛型方法：

---

一、时间复杂度和空间复杂度

1.1时间复杂度：

时间复杂度是一个程序中算法执行的次数，我们用大O渐进表示法计算
我们看以下代码：

1.       void func1(int N){
2.         int count = 0;
3.         for (int i = 0; i < N ; i++) {    //执行了N次
4.             for (int j = 0; j < N ; j++) {   //执行N次
5.                 count++;
6.             }
7.         }
8.         for (int k = 0; k < 2 * N ; k++) {   //执行2*N次
9.             count++;
10.         }
11.         int M = 10;
12.         while ((M--) > 0) {   //执行了10次
13.             count++;
14.         }
15.         System.out.println(count);  //一共执行了N^2+2*N+10次，采用大O渐进表示时间复杂度为O（N*N）
16.     }

复制代码

假如要计算递归的时间复杂度，公式就是：递归次数*每次递归代码执行次数

1. // 计算阶乘递归factorial的时间复杂度？
2. long factorial(int N) {
3.     //递归了N次，每次递归的代码时间复杂度是O（1），所以总时间复杂度是O（N*1）=O（N）
4.     return N < 2 ? N : factorial(N-1) * N;
5. }

复制代码

  推导大O阶方法：
     1   、用常数   1   取代运行时间中的全部加法常数。        2   、在修改后的运行次数函数中，只保存最高阶项。        3   、假如最高阶项存在且不是   1   ，则去除与这个项目相乘的常数。得到的结果就是大   O   阶。   
1.2空间复杂度：

空间复杂度是计算临时占用存储空间巨细的量度

1.     // 计算bubbleSort的空间复杂度？
2.     void bubbleSort(int[] array) {
3.         for (int end = array.length; end > 0; end--) {
4.             boolean sorted = true;
5.             for (int i = 1; i < end; i++) {
6.                 if (array[i - 1] > array[i]) {
7.                     Swap(array, i - 1, i);
8.                     sorted = false;
9.                 }
10.             }
11.             if (sorted == true) {
12.                 break;
13.             }
14.         }
15.     }
16.     //由于没有开辟新内存，所以空间复杂度为O（1）
19.     // 计算fibonacci的空间复杂度？
20.     int[] fibonacci(int n) {
21.         long[] fibArray = new long[n + 1];//代码在这里创建了大小为n+1的数组，故空间复杂度为O（n）
22.         fibArray[0] = 0;
23.         fibArray[1] = 1;
24.         for (int i = 2; i <= n ; i++) {
25.             fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
26.         }
27.         return fibArray;
28.     }

复制代码

二、装箱和拆箱

装箱就是把根本数据类型转成包装类类型，拆箱就是把包装类类型转成根本数据类型，装箱和拆箱都有主动和手动：

1.         int i=10;
3.         Integer ii=i;//自动装箱
4.         Integer ij=Integer.valueOf(i);//手动装箱
6.         int j=ii;//自动拆箱
7.         int ji=ii.intValue();//手动拆箱

复制代码

三、泛型

3.1泛型类的使用：

语法：
  

1. //泛型类<类型实参> 变量名; // 定义一个泛型类引用
2. //new 泛型类<类型实参>(构造方法实参); // 实例化一个泛型类对象
3. MyArray<Integer> list = new MyArray<Integer>();

复制代码

   注意：泛型只能接受类，全部的根本数据类型都要使用包装类 
泛型类的使用例子如下：

1. //定义一个数组泛型类
2. class MyArray <T>{
3.     public Object[] array = new Object[10];//以后创建泛型数组最好使用这样的格式
4.     public T getPos(int pos) {
5.         return (T)array[pos];//返回任意类型的值
6.     }
7.     public void setVal(int pos,T val) {
8.         this.array[pos] = val;//传入T类型值
9.     }
10. }
11. public class Main {
12.     public static void main(String[] args) {
13.         MyArray<Integer> myArray = new MyArray<>();
14.         myArray.setVal(0,10);
15.         MyArray<String> myArray1=new MyArray<>();//由于myArray是Integer，这里要传入的是String类型，所以要重新实例化一个变量
16.         myArray1.setVal(1,"hello");//字符串也可以存放
17.         String ret = myArray1.getPos(1);
18.         System.out.println(ret);//hello
19.     }
20. }

复制代码

3.2泛型的上界：

假如没有指定泛型的上届，那么默认是extends Object：

1. class MyArray <T>{        //这里没有指定泛型上界，默认是<T extends Object>
2.     public Object[] array = new Object[10];
3.     public T getPos(int pos) {
4.         return (T)array[pos];
5.     }
6.     public void setVal(int pos,T val) {
7.         this.array[pos] = val;
8.     }
9. }

复制代码

语法：

1. class 泛型类名称<类型形参 extends 类型边界> {
2. ...
3. }

复制代码

1. class MyArray <E extends Number>{
2.    
3. }
4. public class Main {
5.     public static void main(String[] args) {
6.         MyArray<Integer> myArray = new MyArray<>();
7.         MyArray<String> myArray1=new MyArray<>();//编译错误，因为String不是Number的子类型
8.     }
9. }

复制代码

3.3泛型方法：

语法：方法限定符 <类型形参列表> 返回值类型 方法名称(形参列表) { ... }

1. //定义一个泛型类 ，找到数组当中的最大值
2. class Alg<T extends Comparable<T>> {
3.     public T findMax(T[] array) {
4.         T max = array[0];
5.         for (int i = 1; i < array.length; i++) {
6.             //if(array[i] > max) {
7.             if(array[i].compareTo(max) > 0) {
8.                 max = array[i];
9.             }
10.         }
11.         return max;
12.     }
13. }
14. //定义一个泛型方法，找到数组当中最大值
15. class Alg2 {
16.     public <T extends Comparable<T>> T findMax(T[] array) {
17.         T max = array[0];
18.         for (int i = 1; i < array.length; i++) {
19.             //if(array[i] > max) {
20.             if(array[i].compareTo(max) > 0) {
21.                 max = array[i];
22.             }
23.         }
24.         return max;
25.     }
26. }
27. //定义一个静态泛型方法，找到数组当中最大值
28. class Alg3 {
29.     public static <T extends Comparable<T>> T findMax(T[] array) {
30.         T max = array[0];
31.         for (int i = 1; i < array.length; i++) {
32.             //if(array[i] > max) {
33.             if(array[i].compareTo(max) > 0) {
34.                 max = array[i];
35.             }
36.         }
37.         return max;
38.     }
39. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。