数据结构知识点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;
    }
}