数据结构知识点1

目录

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

1.1时间复杂度：

1.2空间复杂度：

二、装箱和拆箱

三、泛型

3.1泛型类的使用：

3.2泛型的上界：

3.3泛型方法：

---

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

1.1时间复杂度：

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

我们看以下代码：

      void func1(int N){int count = 0;for (int i = 0; i < N ; i++) {    //执行了N次for (int j = 0; j < N ; j++) {   //执行N次count++;}}for (int k = 0; k < 2 * N ; k++) {   //执行2*N次count++;}int M = 10;while ((M--) > 0) {   //执行了10次count++;}System.out.println(count);  //一共执行了N^2+2*N+10次，采用大O渐进表示时间复杂度为O（N*N）}

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

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

推导大O阶方法：

1 、用常数 1 取代运行时间中的所有加法常数。

2 、在修改后的运行次数函数中，只保留最高阶项。

3 、如果最高阶项存在且不是 1 ，则去除与这个项目相乘的常数。得到的结果就是大 O 阶。

1.2空间复杂度：

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

    // 计算bubbleSort的空间复杂度？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;}}}//由于没有开辟新内存，所以空间复杂度为O（1）// 计算fibonacci的空间复杂度？int[] fibonacci(int n) {long[] fibArray = new long[n + 1];//代码在这里创建了大小为n+1的数组，故空间复杂度为O（n）fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; i++) {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray;}

二、装箱和拆箱

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

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

三、泛型

3.1泛型类的使用：

语法：

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

注意：泛型只能接受类，所有的基本数据类型都要使用包装类 

泛型类的使用例子如下：

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

3.2泛型的上界：

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

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

语法：

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

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

3.3泛型方法：

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

//定义一个泛型类 ，找到数组当中的最大值
class Alg<T extends Comparable<T>> {public T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {//if(array[i] > max) {if(array[i].compareTo(max) > 0) {max = array[i];}}return max;}
}
//定义一个泛型方法，找到数组当中最大值
class Alg2 {public <T extends Comparable<T>> T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {//if(array[i] > max) {if(array[i].compareTo(max) > 0) {max = array[i];}}return max;}
}
//定义一个静态泛型方法，找到数组当中最大值
class Alg3 {public static <T extends Comparable<T>> T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {//if(array[i] > max) {if(array[i].compareTo(max) > 0) {max = array[i];}}return max;}
}