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