沈阳网站建设信息,珠海市香洲区建设局网站,西安大公司,软件制作公司排名目录
1.时间和空间复杂度
1.1时间复杂度
1.2空间复杂度
2.包装类
2.1基本数据类型和对应的包装类
2.2装箱和拆箱
//阿里巴巴面试题
3.泛型
3.1擦除机制
3.2泛型的上界 1.时间和空间复杂度
1.1时间复杂度 定义#xff1a;一个算法所花费的时间与其语句的执行次数成…目录
1.时间和空间复杂度
1.1时间复杂度
1.2空间复杂度
2.包装类
2.1基本数据类型和对应的包装类
2.2装箱和拆箱
//阿里巴巴面试题
3.泛型
3.1擦除机制
3.2泛型的上界 1.时间和空间复杂度
1.1时间复杂度 定义一个算法所花费的时间与其语句的执行次数成正比算法中的基本操作的执行次数为算法的时间复杂度。 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^22n10 但实际情况下只需要计算大概执行次数即——大O渐进法: 大O渐进法 1 用常数1代替所有的加法常数 2 只保留最高阶项 3 如果最高阶项存在且不是1则去除与这个项相乘的常数。 例F(n) 2n^2 5n 100 O(n^2) 注意 二分查找 O(n) log2N 递归 O(n) 递归的次数*每次递归后执行的次数 public class Main {long factorial(int n) { //阶乘return n2?n:factorial(n-1)*n; //O(n)n}long fibonacci(int n) { //菲波那切数列return n2?n:factorial(n-1)factorial(n-2); //O(n)2^n}
} 拓展平均复杂度 定义所有情况下代码执行的次数累加起来再除以所有情况数量即为平均复杂度。 例如下述代码判断x在循环中出现的位置有n1种情况1xn 和 nx 所以平均复杂度为(123……n) n/ n1 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空间复杂度 定义空间复杂度是一个算法在运行时临时占用存储空间大小的量度即计算的是变量的个数。 public class Test {//实例1使用了常数个额外空间空间复杂度为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动态开辟了N个空间空间复杂度为O(N)//菲波那切数列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递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间空间复杂度为O(N)//阶乘递归long factorial(int N) {return N 2 ? N : factorial(N-1)*N;}
}2.包装类
2.1基本数据类型和对应的包装类 基本数据类型 包装类byteByteshortShortintIntegerlongLongfloat Float double DoublecharCharacterbooleanBoolean
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();//拆成对应的类型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(ab);//trueSystem.out.println(cd);//false}
} 原因装箱时底层调用了valueOf方法本质是一个范围在-128~127之间的数组。 3.泛型
先来看看一道编程题编程要求创建一个可以存放任何类型数据的数组。
解所有类的父类默认为Object类所以可以创建一个Object数组用来存放不同类型的元素
class MyArray {public Object[] objects new Object[10];//创建Object类数组public Object getPos(int pos) {//访问数组return objects[pos];}public void setVal(int pos,Object val) {//赋值数组objects[pos] val;}
}
public class Test {public static void main(String[] args) {MyArray myArray new MyArray();//此时可以将不同类型的元素放入数组中myArray.setVal(0,123);myArray.setVal(1,10);//由于父类是Object类型访问时必须强制类型转换int val (int)myArray.getPos(1);System.out.println(val);//10}
}我们发现上述代码有些繁琐但用泛型来解这道题就会简单可读很多 定义通俗来讲就是适用于许多许多类型从代码上讲就是对类型实现了参数化传递类型。 意义在编译时帮我们进行类型的检查和转换注意在运行时没有泛型这一概念即JVM中没有泛型。 语法class 泛型类名称 类型形参列表 { 代码块 } 常见类型形参列表E - Element、K - Key、V - Value、N - Number、T - Type、S/U/V等 - 第二、第三、第四个类型。 注意不能new泛型类型的数组。 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) {MyArrayInteger myArray1 new MyArrayInteger();//指定类型为Integer myArray1.setVal(0,1); //这里的Integer可不写myArray1.setVal(1,2);int val myArray1.getPos(1);System.out.println(val);//2MyArrayString myArray2 new MyArrayString();//指定类型为StringmyArray2.setVal(0,hello); //这里的String可不写myArray2.setVal(1,world);String ret myArray2.getPos(1);System.out.println(ret);//world}
}
3.1擦除机制 定义在编译过程中将所有的T替换为Object这种机制称为擦除机制。 编译器生成的字节码在运行期间并不包含泛型的类型信息。 class MyArray T {public Object[] objects new Object[10];public T getPos(int pos) {return (T)objects[pos];//强转}public void setVal(int pos,Object val) {objects[pos] val;}
}
3.2泛型的上界 写一个泛型类其中有个方法用来求数组中的最大值
class AlgT extends ComparableT { //擦除为一个实现了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 staticT extends ComparableT T findMax(T[] array) { //静态泛型方法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) {AlgInteger alg new Alg();Integer[] array {1,9,3,7,5,4};Integer max alg.IntegerfindMax(array);//此处Integer可不写System.out.println(max);}public static void main2(String[] args) {Integer[] array {1,9,3,7,5,4};Integer max Alg2.IntegerfindMax(array);//此处Integer可不写System.out.println(max); //静态方法通过类名调用}
} 这一点点只是开胃菜后面还有更多有趣的知识等着我们去学习
痛并快乐着捏 ~ ~
