医学类的网站做Google,定制开发app方案,常州市金坛区网站建设,摄影网站首页设计❣博主主页: 33的博客❣ ▶文章专栏分类: Java从入门到精通◀ #x1f69a;我的代码仓库: 33的代码仓库#x1f69a; #x1faf5;#x1faf5;#x1faf5;关注我带你学更多数据结构知识 目录 1.前言2.集合架构3.时间和空间复杂度3.1算法效率3.2时间复杂度3.2.1大O的渐进… ❣博主主页: 33的博客❣ ▶文章专栏分类: Java从入门到精通◀ 我的代码仓库: 33的代码仓库 关注我带你学更多数据结构知识 目录 1.前言2.集合架构3.时间和空间复杂度3.1算法效率3.2时间复杂度3.2.1大O的渐进表示3.2.2常见时间复杂度举例 3.3空间复杂度 4.包装类4.1基本数据和对应的包装类4.2装箱和拆箱 5.泛型5.1引出范型5.2语法5.3泛型类的使用5.4泛型是如何编译5.5泛型的上界5.6泛型方法 6.总结 1.前言 数据结构是计算机存储组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合从这篇文章开始我们将一起进入数据结构的学习那么该如何学好数据结构呢博主的建议是多写代码多思考多画图 本章重点 掌握数据结构基本知识主要包括集合框架时间和空间复杂度算法效率大O渐进表示包装类泛型相关知识。 2.集合架构
Java 集合框架Java Collection Framework 又被称为容器和其实现类classes 。 类和接口总览 3.时间和空间复杂度
遇到一个算法我们怎么衡量一个算法的好坏呢
3.1算法效率
算法效率分析分为两种第一种是时间效率第二种是空间效率。时间效率被称为时间复杂度而空间效率被称作空间复杂度。
3.2时间复杂度
时间复杂度的定义在计算机科学中算法的时间复杂度是一个数学函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。
有些算法的时间复杂度存在最好、平均和最坏情况: 最坏情况任意输入规模的最大运行次数(上界)当说时间复杂度一般值最坏情况下 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界 3.2.1大O的渐进表示
在计算时间复杂度时我们不需要计算精确的执行次数只需要大概的次数那么我们就剋用大O渐进表示法去掉那些对结果影响不大的项简明表示执行的次数。 规则 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 3.2.2常见时间复杂度举例
例1.
void func2(int N) {int count 0;for (int k 0; k 2 * N ; k) {count; //时间复杂度2N}int M 10;while ((M--) 0) {count; //时间复杂度10}System.out.println(count);}时间复杂度2N10 为ON 例2.
void func3(int N, int M) {int count 0;for (int k 0; k M; k) {count; //时间复杂度M}for (int k 0; k N ; k) {count; //时间复杂度N}System.out.println(count);}时间复杂度MN为OMN 例3.
// 计算func4的时间复杂度
void func4(int N) {int count 0;for (int k 0; k 100; k) {count; //时间复杂度100}System.out.println(count);}时间复杂度100为O1 例4.
// 计算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;}}}假设array.lengthN,那么第一次循环执行N-1次第二次循坏执行N-2次第三次循环执行N-3…最后一次为1那么总次数就是N-1)(N-2)(N-3)…1,等差数列求和结果为NN-N/2那么时间复杂度为ONN。 例5.
int binarySearch(int[] array, int value) {int begin 0;int end array.length - 1;while (begin end) {int mid begin ((end-begin) / 2);if (array[mid] value)begin mid 1;else if (array[mid] value)end mid - 1;elsereturn mid;}return -1;}那么剩下1个数就需要时间复杂度Olog2^N。 例6.
// 计算阶乘递归factorial的时间复杂度
long factorial(int N) {return N 2 ? N : factorial(N-1) * N;}递归复杂度递归次数*每次递归后执行的次数 时间复杂度N-1*1O(N) 例7.
int fibonacci(int N) {return N 2 ? N : fibonacci(N-1)fibonacci(N-2);}//2^n3.3空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似也使用大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;}}}//输出O1例2.
int[] 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;}//ON4.包装类
在Java中由于基本类型不是继承自Object为了在泛型代码中可以支持基本类型Java给每个基本类型都对应了一个包装类型。
4.1基本数据和对应的包装类
基本数据类型包装类byteByteshortShortintIntegerlongLongfloatFloatdoubleDoublecharCharacterbooleanBoolean 4.2装箱和拆箱
Integer a 10;//装箱
int b 20;
Integer cb;//基本类型转变为包装类型Integer a 10;
int c a;//拆箱包装类型转换为基本类型例
public static void main(String[] args) {Integer a 127;Integer b 127;Integer c 128;Integer d 128;System.out.println(a b);//trueSystem.out.println(c d);//false}为什么输出结果一个是T一个是F呢我们来看看源码 通过源码我们知道如果范围在【-128127】那么就返回数组中的值否则就new一个对象。127在范围内那么直接返回cache[255]的值128不在范围内久new一个 对象。 5.泛型
泛型就是适用于许多许多类型。从代码上讲就是对类型实现了参数化。
5.1引出范型
实现一个类类中包含一个数组成员使得数组中可以存放任何类型的数据也可以根据成员方法返回数组中某个下标的值
class MyArray {public Object[] array new Object[10];public Object getPos(int pos) {return this.array[pos];}public void setVal(int pos,Object val) {this.array[pos] val;} }public class TestDemo {public static void main(String[] args) {MyArray myArray new MyArray();myArray.setVal(0,10);myArray.setVal(1,hello);//字符串也可以存放String ret myArray.getPos(1);//编译报错//强行转化String ret (String)myArray.getPos(1);System.out.println(ret);}}但是我们发现虽然任何类型的数据都可以存放但是获得的时候报错必须强制转换。但是当代码很多的变量的时候我们就不知道该变量是什么类型的每次都要返回定义的时候去查看是什么类型就比较繁琐。更多情况下我们还是希望他只能够持有一种数据类型。而不是同时持有这么多类型。所以泛型的主要目的就是指定当前的容器要持有什么类型的对象。让编译器去做检查。此时就需要把类型作为参数传递。需要什么类型就传入什么类型。 5.2语法
class MyArrayT {//添加 表示这个类是泛型public T[] array (T[])new Object[10];//这句代码是错误的这样写只是为了不让编译器报错public T getPos(int pos) {return this.array[pos];}public void setVal(int pos,T val) {this.array[pos] val;}}public class TestDemo {public static void main(String[] args) {MyArrayInteger myArray new MyArray();//传入Integer后每次存储数据时会检查存入的数据是不是我传入的类型获取数据的时候也不需要强制转化。myArray.setVal(0,10);myArray.setVal(1,12);int ret myArray.getPos(1);System.out.println(ret);myArray.setVal(2,bit);}}5.3泛型类的使用
语法 泛型类参数类型 变量名; //定义一个泛型类引用
MyArrayInteger a;
new 泛型类类型实参(构造方法实参); // 示例化一个泛型类对象
MyArrayInteger myArray new MyArray();5.4泛型是如何编译
在编译过程中将所有的T替换为object这种机制称为擦除机制在运行的时候并没有泛型的概念。 通过命令javap -c 查看字节码文件所有的T都是Object: 在编译的过程当中将所有的T替换为Object这种机制我们称为擦除机制。 Java的泛型机制是在编译级别实现的。
实例化的时候不能实例化一个泛型数组。
T[] anew T[5];//这样定义泛型是错误的这个时候我们不知道到底定义的什么类型的数组
//以我们现在的知识一般定义数组的时候我们采取以下方式
object[] anew obje[5];5.5泛型的上界
在定义泛型类时有时需要对传入的类型变量做一定的约束可以通过类型边界来约束。 语法
class 泛型类名称类型形参 extends 类型边界 {...}
MyArrayInteger l1; // 正常因为 Integer 是 Number 的子类型
MyArrayString l2; // 编译错误因为 String 不是 Number 的子类型5.6泛型方法
定义语法
方法限定符 类型形参列表 返回值类型 方法名称(形参列表) { ... }示例
public class Util {//静态的泛型方法 需要在static后用声明泛型类型参数public static E void swap(E[] array, int i, int j) {E t array[i];array[i] array[j];array[j] t;}}//使用Integer[] a { ... };Util.swap(a, 0, 9);//使用类型推导Util.Integerswap(a, 0, 9);//不使用类型推导6.总结 本篇介绍数据结构基本知识主要包括集合框架时间和空间复杂度算法效率大O渐进表示包装类泛型相关知识其中关于用泛型定义数组的内容博主比并没有深入讲解感兴趣的同学可以查看其他博主的内容。 下期预告顺序表
