https://www.youtube.com/playlist?list=PLu0nzW8Es1x3TmpwQRLMQwCtulEd43ZY8
以上为 CS 61B Lecture 1 课程概述的详细总结。
对象是数据的组合,包含了数据(成员变量)和行为(成员方法)。类是对象的蓝图或型,描述了对象的结构和行为。
使用new关键字调用类的构造函数来创建对象,例如:
String s1 = new String();
这行代码做了以下事情:
变量使用引用(指针)来引用对象,而不是直接包含对象本身。
例如:
String s1 = new String();
这里s1变量中的值是一个引用,它指向新创建的String对象。
要调用对象的方法,需要使用“对象.方法()”的语法:
s1.toUpperCase();
这行代码做了以下事情:
String类有多个构造函数,它们的参数不同,实现不同功能:
构造函数名称必须与类名相同。
可以通过引用复制,让多个变量引用同一个对象:
String s1 = new String("a");
String s2 = s1;
这里s1和s2都引用同一个字符串对象。若其中一个变量值改变,会影响另一个。
此视频说明了对象、类和构造函数的概念,介绍了如何使用new关键字创建对象,使用变量引用对象,以及如何调用对象方法。
对象是数据的存储空间,存储在对象中的称为字段。字段可以是不同类型的值,如整数、字符串等。
方法则是定义在类中的功能,使用方法可以操作对象内部的数据。
使用class关键字来定义一个类,后面跟类的名称。
class 类名{
//字段和方法定义
}
字段使用数据类型来定义,如整数型int或字符串型String等。可以使用public访问修饰符,让别的类能访问这个字段。
public int 字段名;
使用方法名()语法来定义一个方法。可以添加参数参数类型 参数名,以及返回值返回类型。
返回类型 方法名(参数类型 参数名){
//方法体
}
以下是定义一个Person类的示例:
class Person{
public int age;
public String name;
public void introduce(){
System.out.println("I am " + name + ". I am " + age);
}
}
定义类后,可以使用new关键字来实例化对象,并为其字段赋值。
Person p = new Person();
p.age = 20;
p.name = "Zhangsan";
使用对象.方法()的方式来调用对象的方法。
p.introduce();
一个对象可以存储多个字段,每个字段独立存储,互不影响。
当调用对象的方法时,方法内可以使用this关键字来代表当前对象。确保操作的一致对象。
一个方法可以操作多个对象,通过参数来传入其他对象。
以上内容介绍了如何使用类、对象、字段和方法来封装数据并进行操作。利用类可以方便地描述实体关系并实现复用。
原始类型包括:
原始类型变量实际存储的值,引用类型变量存储指针。
数值字面量后加L定义long,加F定义float。
数值类型支持以下操作符:
整型/整型结果为整型,舍弃小数部分。浮点数除法结果根据类型保留对应位数。
if(条件){ //条件成立执行 }
return表达式;返回表达式值
boolean只有true、false两个值
Java提供了几种循环的方式进行迭代:
while循环:依据条件是否满足决定是否继续执行循环体。
for循环:使用更简洁的语法表达循环次数和变量的迭代,常用于简单的计数循环。
循环条件:决定是否继续执行循环体。
循环体:循环每次迭代都会执行的语句块。
更新语句:每次循环结束后执行,用于更新循环条件或变量。
Java在检查循环条件前不执行循环体,如果开始条件不满足,循环体一次都不会执行。
检查条件后执行循环体,然后再检查条件是否继续迭代。
循环边界设置错误是常见bug,如需要1-n范围应使用<=而不是<。
数组可以用来存储大量相似类型数据,避免重复声明大量变量。
使用类型名加[]声明数组引用变量,此时未分配存储空间。
使用new关键字加上元素类型和长度构造数组对象,分配内存空间。
数组对象初始化后,通过索引可以对每个元素单独操作。
可以通过下标访问数组每个元素,下标从0开始。
不同类型数组还可以通过for循环进行迭代操作每个元素。
数组长度可以随意指定但后续无法改变。
以上内容详细阐述了Java中的循环方式和数组定义与使用方法,提供了学习 Java 迭代和数组的基础知识。
Java可以自动为你构造一维和多维数组。
对于一维数组,直接声明数组类型和大小即可:
int[] arr = new int[5];
对于二维数组,在new关键字后面指定行和列的个数:
int[][] mat = new int[3][4];
java会自动为你创建数组引用,以及为每个子数组分配空间。
初始化数组时可以直接为数组元素赋值:
int[] arr = {1, 2, 3};
String[] strs = {"a", "b", "c"};
对多维数组也适用:
int[][] mat = {{1,2},{3,4,5}};
但仅限于初始化,一般赋值语句无法直接为数组指定内容。
数组声明可以采用:
int[] a;
int a[];
string[] a[];
需要根据环境辨认数组的维度。
Java程序的main方法有一个String[]类型的参数args,用于接收命令行传入的参数。
可以使用for循环遍历args数组,取出每一个参数进行处理。
do-while循环保证循环体至少执行1次。适用于需要在循环体执行前就执行某项操作的场景。
break语句可以中断循环或switch的执行,跳出当前的循环或者switch结构。
continue语句运行循环中的下一次迭代,跳过循环中当前迭代的剩余语句。
它们可以帮助解决循环体进入和退出的位置不一致的情况。
数组列表在插入或删除项目时会很慢,因为它需要移动所有后续项目以保持连续性。
它也不方便插入项目,因为数组有固定长度。如果需要添加项目但数组已满,就需要重新分配更大的数组。
链表由节点组成,每个节点存储一项数据和指向下一个节点的引用。最后一个节点的下一个引用为null。
定义链表节点类Node,包含item和next成员。
使用构造函数为节点设置item和next,或者只设置item并将next设为null。
通过赋值next引用,可以将节点链接成列表。
例如:设L1、L2、L3为三个节点,分别存储7、0、6,通过L1.next = L2; L2.next = L3;形成链表。
插入项目:找到插入位置的前一个节点,创建新节点,将其item和next设置,前一个节点的next指向新节点。时间复杂度O(1)。
无限增长:链表具有动态性,可以添加任意数量的节点,无需预先知道总数。
插入 middle 操作时间不随列表长度增加而增加
无需预设列表大小,可以无限增长
nodeType 需要额外空间存储 next 指针
插入/删除效率略低于数组,需要修改指针
不连续性影响访问速度
链表的数据结构可以实现对数据项的插入、删除和访问等操作。通过链表中的“next”指针,可以将每一个节点链接到下一个节点,形成一个线性链式结构。这种结构的优势在于:
可以动态添加和删除节点,无需重新分配内存。
链表中的节点可以位于内存的任意位置,不要求连续存储。
插入和删除操作的时间复杂度是O(1)。
但是相对数组,查找一个特定节点的时间复杂度是O(n)。
链表的接口定义了操作链表的公共方法以及方法的行为说明。
接口中包括公开的方法原型,例如类构造函数;以及这些方法的英语行为描述。接口的目的是用英语说明给其他程序员如何使用该类。
并不是所有类都需要设计成抽象数据类型(ADT)。有些类仅仅起到数据载体的作用,没有需要强加的不变量。这种情况下,可以不将内部设计成私有,直接公开所有属性和方法。
链表可以利用抽象数据类型来设计:
全封装链表结构,只通过链表类的公共方法访问链表。
设置两个不变量:大小字段总是正确记录节点数量;链表结构永远不circular。
只有链表类内部的方法才能修改链表的内部结构,外部无法直接访问节点。
这可以防止链表结构在未来修改时产生兼容性问题。
以上的设计可以很好实现链表的封装,并且保证其结构正确性。
Java程序使用两块内存区域来存储变量:
栈(stack):存储临时变量,如方法参数、局部变量等。方法结束时变量自动释放。
堆(heap):存储对象实例。对象由类构造器new出来,在堆上开辟空间,释放由垃圾回收器处理。
栈由方法调用导致的帧(frame)堆叠组成。方法调用时,在栈顶新增一个帧,帧中存储该方法局部变量。方法返回时,对应帧释放。
Java采用值传递方式。
基本类型参数:直接复制值,在调用方法内不影响外部变量。
引用类型参数:复制对象引用,可以修改对象内部变量值,但是不能修改引用本身。
例如,IntBox类中的数值域可以在setX()方法内修改,但setX()不能改变对象引用本身。
假设一个main()方法调用SList的insertEnd()方法插入元素:
main()方法帧:参数arr、变量list等
insertEnd()方法帧:参数this、obj等
SListNode构造器帧:参数obj
方法返回时,相应帧释放,但堆中的对象不释放。
通过thread dump stack()可以打印当前线程栈帧内容,调试调用路径。
参数详细说明栈、堆和栈帧的作用。给出参数传递的详细例子,帮助理解Java内存模型。
模块测试又称单元测试,是对每个方法和类进行单独测试。
模块测试主要有两种形式:
测试驱动程序:专门调用代码来检查返回结果是否正确。
存根:替代类的其他依赖项。用存根模拟外部系统的行为,从而测试类本身的逻辑。
集成测试是将多个 module 和类整合测试在一起。先确保每个模块单独可用,然后将它们组合起来进行测试。
结果验证测试代码的输出是否符合预期,比如计算结果是否正确,数据结构是否满足不变量等。
测试驱动程序通常使用main方法的方式进行调用。
例如测试链表类SList,可以直接在SList的main方法中写入测试代码。
测试内容包括:
每次测试通过后,应对链表进行还原操作,确保每次测试使用同样的初始状态。
对于需要其他程序调用的类,可以直接在主方法中编写测试代码。
但对于自己包含主方法的应用程序,可以考虑使用JUnit等测试框架来进行自动化测试。
继承是面向对象语言中的一个重要特性,它允许在一个类(子类)中继承另一个类(父类)的字段和方法。子类可以重写父类的方法来改变行为,也可以定义自己独有的新的字段和方法。
我们可以使用extends关键字来定义一个子类,让它继承另一个类的所有属性和方法。
例如:
public class TailList extends SList {
// TailList 继承了 SList 类
}
这里 TailList 是 SList 的子类。
子类相对于父类可以新增三类内容:
定义新的字段。例如 TailList 类可以定义一个新的尾指针字段 tail。
定义新的方法。TailList 类中的方法 SList 中可能没有。
覆写父类的方法。可以改变父类方法的行为,例如使用尾指针来优化插入效率。
当new一个子类对象时,Java会自动在子类构造函数开始时调用父类的空参数构造函数,进行父类的初始化。
如果要调用其它父类构造函数,可以使用super()关键字指定:
public TailList(int capacity) {
super(capacity);
// 设置tail等
...
}
super必须放在构造函数第一行。
如果一个类的子类也有子类,那么最下层子类会继承上面所有父类的字段和方法。
子类可以使用相同的签名覆写父类的方法,实现新行为。但方法参数或返回类型不同视为不同的方法,需要单独覆写。
此外构造函数不能被覆写。
tail list类是S list类的子类。S list类称为父类或超类。S list可以定义一个print()方法为抽象方法,强调子类tail list实现自己的打印逻辑。instanceof操作符判断一个对象的实际类型。instanceof操作符可以在运行时灵活处理对象的类型。Java 包是一组相关联的类,接口等。包可以包含子包。
包中的类和接口都来自同一个开发者,实现类似功能,通常会一起工作来完成一个单独的任务。例如List和List节点类实现单链表的抽象数据类型。
包的主要优点:
包可以包含隐藏的类,这些类被包内使用,但不可从包外访问。例如List不需要让用户知道其内部使用了ListNode。
类可以有只在包内可见的成员,即使这个类本身可以从包外访问。例如ListNode可以让外部使用,但其成员字段只能在包内访问。
Java 接口像抽象类,但不允许有实现方法体。接口可以声明抽象方法的签名。
类可以实现多个接口,使用implements关键字。但一个类只能继承一个父类。
接口也可以有子接口,使用extends关键字。
标准库中的Comparable接口负责为可排序对象提供排序功能。它定义了compareTo()方法返回对象的顺序。实现Comparable的类需要重写compareTo()方法比较两个对象。
Arrays类提供了对实现Comparable接口的对象数组进行排序的静态方法。
实现接口的类需要提供所有抽象方法的实现。
可以为接口变量定义静态类型,例如Comparable c=new MyClass(),但不能new接口。
类实现的接口,其他类可以使用其接口类型作为变量类型或参数类型。这提供了面向接口编程的功能。
昨天讲解的内容如果有任何不清楚或错误之处,请提出。我们可以一起讨论。
在 Java 中,当运行时错误发生时,Java 虚拟机会抛出一个异常。异常是一个对象,如果程序想要捕获异常防止程序中断,可以通过 try-catch 语句块来捕获异常对象。
try 代码块内的语句可能会抛出异常。当异常被抛出后,catch 代码块根据异常的类型来匹配恰当的异常处理程序。只有第一匹配的 catch 代码块会被执行。
常见的例子是打开一个不存在的文件可能会抛出 FileNotFoundException。我们可以写一个 catch 语句块来捕获这个异常:
try {
// 打开文件
} catch (FileNotFoundException e) {
// 处理异常
}
catch 代码块内可以声明一个变量来引用实际抛出的异常对象,从而检查异常的详细信息。
如果 try 代码块内有多种可能抛出异常的操作,可以使用多个 catch 语句块来分别处理不同类型的异常。catch 语句块也常用来关闭在 try 中打开的资源,例如文件。
程序员也可以定义自己的异常类来抛出自定义的异常。例如在编写词法分析器时,当文件意外结束而无法完成分析,可以抛出一个自定义的异常从而优雅地终止程序。异常可以帮助程序从递归调用堆栈中快速退出。
总之,通过Exceptions机制,程序可以在错误情况下优雅地终止,同时也可以选择性地捕获异常继续执行。这比直接终止程序更容易对错误进行处理和诊断。
finally 子句的语句会在 try 语句结束后无论是否发生异常都会执行。
如果 try 语句内发生异常,catch 子句会捕获该异常后执行,之后会执行 finally 子句。如果 try 语句内没有发生异常,直接执行finally 子句。
如果在finally 子句内再次抛出异常,会覆盖原来的异常,继续抛出。
可以使用 finally 子句完成资源释放工作,如关闭文件流。
异常类通常会定义至少两个构造器:
字符串参数可以提供异常的信息描述,通过异常对象的 getMessage() 方法获取。
当异常抛出时,JVM会记录当时的调用栈信息。可以通过异常对象的 printStackTrace() 方法打印出异常栈跟踪信息,有助于调试。
try-catch 子句可以嵌套定义在 catch 子句或 finally 子句内部。
如果内部再次抛出异常,会根据语义原则继续处理。
需要注意避免字段隐藏带来的错误。
接龙子是一种经典的棋类游戏。棋盘上有9个格子,两个玩家轮流在空白格子放置自己的标记,X号或O号。放置后若能连成三条直线,该玩家得一分,胜利者是第一个得分的一方。
游戏状态可以用游戏树来表示。每个节点代表一种棋盘状态,子节点代表在该状态下可能的下家走法。游戏树的叶子节点代表游戏结束的状态。
我们可以为每个节点分配一个分数,来表示计算机从该状态下获胜的可能性:
对于游戏还未结束的中间节点,需要使用Minimax算法来评估:
以此递归下去,从底向上给每个节点分配分数,最终得到根节点的分数,作为计算机该状态下的最优选择。
通过构建完整的游戏树,使用Minimax算法评估每个节点的分数,计算机就可以在任意一步决定最优的下棋策略,从而极大可能地赢得比赛。这就是游戏树搜索算法的基本思路。
本视频讨论了如何设计满足封装性的链表数据结构。
作业3的列表设计中,移除一个节点时只更新节点所在的列表的大小文件,但如果误输入了错误的节点,就会影响该节点实际不在的另一个列表的大小。
考虑将节点方法移除和插入后改放在节点类中,而不是列表类中。因为这些方法相关的操作对象是节点,而不是整个列表。
给每个节点添加一个“my list”字段,记录它所在的列表。那么在操作节点时,就可以通过这个字段取得正确的列表,更新它的大小。
将与节点相关的方法放在节点类中,如移除、插入后等。将与整个列表相关的方法如是否为空等放在列表类中。这样接口更加合理清晰。
如果移除一个节点后直接在它后插入新节点,由于原节点指针未清除,就会形成一个通过原节点的循环,破坏列表循环不变量。
以上总结了视频关于如何设计满足封装性的链表数据结构主要问题和解决思路。
渐进分析是研究算法随输入数据规模增长趋势的一种方法。它通过描述算法在数据规模非常大或趋近无限时的表现,来刻画算法效率。
O大O符号用来表示一个函数的上限。如果函数T(n)的增长速度被简化函数f(n)的增长速度限定,则可以说T(n)是O(f(n))的。
形式定义:对任意正常数C和基本数n0,若对任意n≥n0都有T(n)≤C×f(n),则称T(n)是O(f(n))的。
O(1):表示无论数据规模如何,该算法的运行时间都不随数据规模的增加而增加,为常量时间。
O(n):表示该算法随数据规模的增加而线性增加。
O(n^2):表示为该算法随数据规模的增加而呈平方增加,即为指数时间。
O(2^n):表示随数据规模的增加而呈指数增加,最慢。
如果一个算法完成读取磁盘上所有物品信息的初始化操作需要10000ms,然后每处理一笔交易需要10ms,假设一天有n笔交易。
则该算法的运行时间可以表示为:T(n)=10000+10n
它属于O(n)的线性时间复杂度。
忽略常数因子。O(n)和O(2n)在渐进意义上是等价的。
分析初期阶段而非渐进阶段。只关注输入数据规模趋于无限大时的表现。
错误理解为具体运行时间。O符号反映增长趋势并非实际时间。
以上即为本讲所要点总结。
栈是一种先进后出(LIFO,Last In First Out)的数据结构。新添加的元素会添加在栈的顶部,移除元素也是从栈顶移除。
栈常见的操作有:
栈常见应用有:
队列是一种先进先出(FIFO,First In First Out)的数据结构。新添加的元素会添加在队尾,移除元素也是从队首移除。
队列常见的操作有:
队列常见应用有:
树是一组节点和连线,节点之间通过连线连接形成一条路径。树之间任意两个节点只有唯一的一条路径。
树不存在环状路径。
如果在树中选择一个特定的节点作为根结点,那么除根结点外的其他节点都会获得一个父节点。
父节点是从该节点到根结点路径上的第一个节点。一个节点的子节点是从该节点开始向下延伸的节点。
只有根结点没有父节点。一个节点可以有任意多个子节点。
叶子节点:没有子节点的节点。
兄弟节点:具有相同父节点的节点。
祖先节点:从一个节点到根结点路径上的所有节点,包含该节点本身。
后代节点:与一个节点有路径相连的所有节点。
路径长度:路径中边的数量。
深度:一个节点到根结点的路径长度。
高度:一个节点的最底层后代深度。树的高度是根结点的高度。
子树:以一个节点为根的所包含的所有后代节点形成的树。
二叉树是每个节点最多有两个子节点的树。具体来说:
每个节点包含:存储的值、指向父节点的指针、指向子节点的指针。子节点使用链表或者顺序存储。
阿布莱(Avl)树使用一个指针指向第一个子节点,子节点通过next sibling指针链接。节省内存空间。
树类包含根节点和数量属性。
树结构可以采用前序、中序、后序等不同顺序进行访问节点。
优先队列是一个抽象数据类型,它可以用来处理具有优先级的事件。它支持三种主要操作:
插入项目。可以随时将任何项目插入优先队列中。
标识最小项目。可以获取并返回优先队列中具有最小键值的项目,但不会从队列中删除该项目。
删除最小项目。可以同时从优先队列中移除并返回具有最小键值的项目。
优先队列常用来模拟事件队列。每个项目都有一个键值,代表事件发生的时间,以及一个值,描述事件的内容。优先队列会保证按时间顺序依次处理事件。
二叉堆是实现优先队列的一种高效数据结构。它是一个完全二叉树,且满足堆顺序属性:每个节点的键值都大于或等于其子节点的键值。
二叉堆通常用数组来存储。根节点存储在数组的第一位,后续节点按层次遍历顺序依次存储。这样可以通过索引快速定位各节点和其子父节点。
具体操作include:
插入:将新项目添加到数组尾部,然后上浮调整 restored 符合堆顺序。
标识/删除最小项目:获取并删除根节点,将最后一个节点放到根位,然后下沉调整还原堆顺序。
中的最小项目:直接返回根节点即可。
二叉堆实现了常数时间复杂度的插入和对最小项目的操作,是一种高效的优先队列实现方式。
二叉树的表示使用一个类Binary Tree。类中记录树的规模size和根节点root。然后通过BinaryTreeNode类来表示每个节点。
不同于通常树使用左子节点和兄弟节点表示,二叉树使用左子节点和右子节点表示,因为每个节点只能有两个子节点。
示例表达式树用添加节点表示加法,减法节点表示减法。每个操作节点有两个子节点,表示两个子表达式。leaf节点如6和5没有子节点。所有的父子关系也都记录在内。
二叉搜索树实现有序字典的抽象数据类型。 ordered dictionary相比哈希表可以对键进行有序操作,比如找到最小或最大键。
二叉搜索树每个节点key满足:左子树所有节点key≤该节点key;右子树所有节点key≥该节点key。
通过中序遍历二叉搜索树,可以按顺序打印出所有节点key。中序遍历的步骤是:1. 若该节点有左子树,则中序遍历该左子树;2. 访问该节点;3. 若该节点有右子树,则中序遍历该右子树。
Find操作:从根节点开始,依次比较查找键,匹配则返回该节点,否则进入左子树或右子树继续查找。
Insert操作:查找到插入点后,将新节点作为该插入点的左子节点或右子节点。
Delete操作:找到需要删除的节点后,有三种情况处理其子树的连接。
Min/Max操作:找到最小键和最大键的节点。
Ceil/Floor操作:找到大于等于或小于等于给定键的最大或最小键。
Range操作:找到在两键之间的所有键。
用于实现ordered dictionary数据结构,可以高效实现查找、插入、删除等操作。
可以查找距离给定键最近的值,如匹配名字前缀进行自动补全。
用于排序大量数据,通过二叉搜索树的中序遍历实现线性时间排序。
用于索引和查询,如B树就是二叉搜索树的一种应用。
语法分析常用二叉搜索树表示语法树,通过搜索树结构实现递归下降分析。
二三四树是一种平衡搜索树,每个节点可以存储1-3个key,对应的子节点数为key数+1。
二三四树有以下特征:
二三四树支持find、insert、remove三种基本操作:
二三四树相比传统二叉搜索树, 每个节点可存储更多key,利用空间换取时间效率。但其保持平衡的规则也更复杂,需要在插入和删除时依次向上进行节点重构。
除二三四树外,还有许多其他平衡搜索树,如AVL树、红黑树等,它们采用不同的规则来保证树在插入删除时仍保持高度平衡,效率均为O(logn)。这些数据结构在数据库和文件系统中广泛应用。
图由两个集合组成:
用G(V,E)表示一个图,其中V表示节点集合,E表示边集合。
在有向图中,每个边都有一个方向,以有序对(u,v)表示从节点u指向节点v。
在无向图中,边没有方向,用无序对{u,v}表示节点u和v之间的边。
有向图用带有箭头的线绘制边的方向。
无向图只是简单地绘制边,没有箭头表示方向。
路径是一个节点序列,相邻节点间有边连接。
如果图中任意两个节点之间都存在路径,则该图是连通图。
常用的图存储结构有:
| 邻接矩阵:用 | V | × | V | 矩阵存储,元素定义是否存在边连接两个点。 |
在这节课中,讲师主要讲解了带权图算法。
带权图的意思是,图中的边都附带有一个“权重”值。例如在城市图中,各个城市之间的边可能代表交通线路,则边的权重可以代表这条线路的时间长短或费用高低等。
讲师首先介绍了最短路径问题。该问题是找出图中任意两个节点之间的最短路径,也就是路径权重和最小的那条路径。
然后讲师给出了具体的算法——迪杰斯特拉算法(Dijkstra’s algorithm)来解决这个问题。这个算法的思路是:
首先从源节点开始,将其距离设为0。
接着选择距离源节点最近的一个还未处理的节点,并将它标记为“已经处理”。
随后更新以该节点为中间节点的边,来 recalculate 其他未处理节点到源节点的距离。
重复第二、三步,直到所有节点都被处理。
算法结束后,就可以得到图中所有节点到源节点的最短距离了。
时间复杂度是O(ElogV),其中E为边数,V为节点数。这是因为每次需要从未处理节点中选择一个距离最小的,这需要logV的时间。总操作次数为E次(遍历每条边一次)。
除此之外,讲师还介绍了仅考虑非负权重图时,可以使用松弛(relax)操作来简化算法。并给出了Python代码实现该算法。
最后讲师回答了几个问题,特别强调了迪杰斯特拉算法的一个重要性质:它可以求得图中任意两节点之间的最短路径,而不仅仅是到源节点的最短路径。
插入排序是一种简单的排序算法,其运行时间是O(n^2)。
插入排序的基本思想是:先将第1个数据保存在有序序列中,然后与后续的数据进行比较,将当前数据插入到合适的位置。
插入排序可以对链表或数组进行排序。如果使用链表,每个插入操作的时间复杂度是O(n);如果使用数组,可以使用二分搜索找到插入位置,时间复杂度是O(logn),但是插入后需要移动元素,总时间复杂度仍然是O(n^2)。
插入排序采用原地排序,不需要额外的存储空间。每次只需要将当前元素与已排序区间中的元素进行比较,插入到合适位置即可。
如果输入数组基本有序,插入排序的性能会提升到O(n)。实际运行时间与数组中逆序对的数量成正比。
选择排序也是一种O(n^2)的简单排序算法。
选择排序的基本思路是:每次从未排序序列中找到最小(大)元素,存放到排序序列的末尾。
选择排序也可以原地进行,不需要额外空间。但其每次查找最小元素需要线性时间,因此总时间复杂度仍为O(n^2)。
选择排序的每次循环需要交换元素,也可以说实现起来更简单。但其性能没有插入排序详细。
快速排序属于分治法思想的一种排序算法。它的基本思想是:
选择数组中的一个元素作为基准值(pivot)。
将所有比基准值小的元素放在基准值前面,所有比基准值大的放在后面(这步叫做「划分」)。
递归地把划分后小于基准值的那部分数组和大于基准值的那部分进行快速排序。
重复执行上述步骤,直到所有的子数组元素数量少于等于1,则排序完成。
快速排序的平均时间复杂度是O(nlogn),如果利用随机化技术选择基准值,则其期望时间复杂度也为O(nlogn)。
但是,如果数组已经基本有序,或者每次选择基准值都不太理想,最坏情况下快速排序的时间复杂度可以达到O(n^2)。
给出一个待排序的数组,选择该数组第一个元素作为基准值。
然后将比基准值小的放在它左边,比基准值大的放在它右边。这步称为「划分」。
对划分后的左右两个子数组再进行同样的操作,即递归调用快速排序函数。
递归终止的条件是子数组只包含一个元素或没有元素时。
最后合并两个已经排好序的子数组,得到最终排序结果。
直接选择第一个元素作为基准值的策略,如果数组已经基本有序,将导致快速排序的最坏情况,时间复杂度为O(n^2)
一种较好的策略是随机选择基准值。这可以在概率上避免最坏情况,使平均时间复杂度优于O(n^2)。
另一个更好的策略是选择“三数中值”作为基准值。即随机选择数组的三个元素,将它们中的中位数作为基准值。这可以进一步提高排序效率。
如果数组元素数量很大,也可以采用此策略来选择基准值,以提高快速排序算法的性能。
快速排序适用于任意大小的数组排序。对顺序存储结构的数组尤其高效。
如果采用随机选择基准值或三数中值策略,快速排序也适用于顺序数据基本已排序的情况。
但对链表进行快速排序时,由于链表难以进行随机访问,效率会差些。这时可以考虑使用归并排序。
总的来说,快速排序是最常用且效率较高的一种排序算法,在实际应用中广泛使用。
无交集集合是一种数据结构,它用于表示一组没有交集的集合。即每个项目都只能属于一个集合内。
无交集集合支持快速地完成两种操作:
列表式无交集集合实现思路:
Find操作很快,直接返回项目所属集合。但Union操作比较慢,需要将另一个集合的所有项目添加到列表中,同时修改这些项目内部存储的集合信息。
树式无交集集合实现思路:
Tree-Union Find算法:
路径压缩的思想是:在Find的过程中,将节点直接指向根节点,这样后续Find路径就更短了。
具体做法是:在Find过程中,一次性将当前节点和其祖先节点都直接指向根节点。
路径压缩能有效降低树的高度,近乎将Find的时间复杂度降低到O(α(m,n)),其中α为阿克曼函数。
Kruskal算法在判断是否加入一条边时,需要判断两个结点是否已在同一集合中。
使用无交集集合来存储结点就可以快速判断:通过Find操作判断两个结点是否有同样的根节点。这比深度优先搜索更快效率。
选择排序是一种排序算法,它通过寻找数组中最小(大)的元素,然后和第一位元素交换位置,以此类推,可以把元素按照大小顺序排序。
选择排序的时间复杂度为O(n^2),每一次循环中都需要遍历整个数组来找到最小值,然后将它和第一位置交换,这样需要循环n次。
快速选择算法采用和快速排序相同的partition分割思路,将数组划分为两部分,但只递归查找其中一部分即可找到指定位置的元素。
具体步骤:
快速选择算法的时间复杂度为O(n),平均情况下只需要线性时间就可以找到指定位置的元素。
如果有n个不同的数字,每个数字只能使用一次,那么它们可以排列组合成的不同顺序数就是n的阶乘,记为n!。
n! 计算方式为:n! = 1 × 2 × 3 × … × (n-1) × n
可以证明:
这说明n个不同元素的排列组合数阶乘项增长得非常快。
如果只允许使用比较运算决定元素的相对大小进行排序,那么任何一种排序算法的时间下界都为Ω(nlogn)。
证明思路:
所以仅使用比较操作的排序算法,时间复杂度的理论下限就是Ω(nlogn)。
计数排序是一个常数时间 O(n+k) 的排序算法,其中 k 是可能键值的范围。它适用于键值在有限范围内的排序问题。
假设要排序的仅仅是一组数字,没有任何相关信息。
初始化一个长度为 k 的计数数组 count[],所有元素均初始化为0。
遍历输入数组,对于每个元素x,计数数组 count[x] 加1。
对计数数组进行前缀和扫描,这样 count[i] 就表示小于或等于i的元素数量。
根据计数数组输出有序数组。从count[0] 开始填入0, count[1]-count[0] 填入1,以此类推。
如果排序元素包含键值以外的其他信息,需要一个更复杂的算法:
同样初始化长度为k的计数数组count[]
扫描输入数组,统计各个键值的个数
对计数数组进行前缀和扫描,这个过程将计数数组转化为存放元素输出下标的数组
根据计数数组将元素输出到结果数组中。对每个元素,根据其键值在计数数组中取得输出下标,并将元素写入结果数组。同时更新计数数组避免重复计数。
这样就完成了元素的排序。
假设输入数组为[[6,a],[7,b],[3,c],[0,d],[1,e],[5,f],[0,g],[3,h],[7,i]],要按键值进行排序:
初始化长度为10的计数数组count[],全部元素为0
扫描输入数组,统计每个键值的个数,得到计数数组[2,2,2,2,1,1,0,0,0,0]
对计数数组进行前缀和扫描,得到[0,2,4,6,7,8,8,8,8,8]
遍历输入数组,根据每个元素的键值在计数数组中取得其输出下标,并将元素写入结果数组。同时将计数数组对应元素加1
结果数组为[[0,d],[0,g],[1,e],[3,c],[3,h],[5,f],[6,a],[7,b],[7,i]],完成排序
计数排序的时间复杂度为O(n+k),其中n是输入元素数,k是可能键值范围。它适用于k较小的情况,否则空间复杂度就很高了。
相比buckets排序,计数排序中不需要处理链表,效率会高一些。但buckets排序直接使用链表结构也更符合一些场景。
总体来说,如果键值范围很大,则应选择时间复杂度O(nlogn)的比较排序,如快速排序、归并排序等。如果键值范围有限,则计数排序或buckets排序更好选择。
摇树是一种平衡二叉搜索树,与红黑树和AVL树一样,通过旋转操作来实现树的平衡。与二叉搜索树不同的是,摇树在进行查找时,会将查找结点移动到根结点,进一步平衡整个树。
摇树操作和二叉搜索树相同,包括查找、插入、删除结点等。但摇树在执行这些操作后,会进行额外的“摇树”操作,通过结点的旋转来将操作结点移动到根部。
旋转是摇树平衡树的核心操作。通过结点的左旋转和右旋转,可以将某个结点移动到其父结点的位置,实现对树形结构的调整。
左旋转:将结点X作为新的根结点,X的右子树作为X的左子树,X原来的左子树作为X的右子树。
右旋转:与左旋转反,将结点X作为新的根结点,X的左子树作为X的右子树,X原来的右子树作为X的左子树。
平衡摇树时一般分三种情况进行旋转:
蛇形案例:结点是其父结点的左子结点或者右子结点的左子结点/右子结点。 通过两次旋转将结点上浮两层。
锯齿形案例:结点是其父结点的左子结点或者右子结点。但与蛇形案例不同,首先要旋转其grandparent结点,然后旋转parent结点。
其他情况直接对parent结点进行一次旋转。
每次操作后,都会将操作结点通过旋转移动到根部,从而实现树的动态平衡。整棵树的时间复杂度仍为O(logN)。
实现简单,只需左旋转和右旋转两种操作。
对经常访问的数据访问速度快,可以达到O(1)时间复杂度。
平均时间复杂度为O(logN),最差情况为O(N)但概率很低。
相比其他平衡树,摇树结构更紧凑。
因此,摇树广泛应用于系统缓存,数据库索引等需要快速访问特定数据的场合。
平均分析保证一系列操作的总时间复杂度,而不是单个操作。它可以应用于令单个操作时间变慢,但大量操作平均速度快的算法。
随机化分析考虑算法中使用随机性带来的期望运行时间。如快速排序、快速选择和哈希表的平均时间复杂度优于最坏情况。
假设哈希表只包含一个桶,插入操作时桶数翻倍。非恰充分扩容操作需2n时间。
插入I次:
无法处理删除操作,因为操作序列不确定。需使用更复杂方法进行平均分析。
本节介绍了平均分析和随机分析的区别。以哈希表为例进行了平均化分析,证明了插入操作的平均时间复杂度为O(1)。分析方法包括假设只有1个桶、桶数翻倍扩容等。介绍了分配账本法无法适用于删除操作。
随机算法根据随机数生成器生成的随机数来做决定。随机算法的平均运行时间可以用概率论来分析。
随机变量描述一个可能取多种值的量。一个随机调用X的运行时间可以是1秒或3秒,取决于掷硬币结果。它用一个随机变量X来表示。X有0.5的概率是1秒,0.5的概率是3秒。
期望表示如果重复实验无限次,随机变量的值的平均值。
期望(X) = 概率(X=x1) x1 + 概率(X=x2) x2 + …
例如X的期望即为0.5 1 + 0.5 3 = 2秒。
如果一个随机变量T是其他随机变量X,Y的和,那么:
期望(T) = 期望(X) + 期望(Y)
即随机变量的和的期望等于每个随机变量期望的和。这对于分析随机算法的总时间很有用。
假设Hash表使用链地址法解决冲突,且不允许重复键。
对一个键K的查找操作包括:
如果哈希函数很随机,每个键都均匀分布到每个桶中,那么期望查找长度就是整个表的平均链表长度。
此模型下,可以预测随机哈希表的平均性能。
在计算机科学中,表达式可以用以下几种形式表示:
中缀表达式(Infix Expression):就是我们平时在公式中看到的运算顺序。例如:3 + 4 * 7。这种形式更方便人类阅读。
后缀表达式(Postfix Expression):将操作符写在操作数后面。例如:3 4 7 * +。这种形式更适合计算机直接计算。
前缀表达式(Prefix Expression):将操作符写在操作数前面。例如:+ 3 * 4 7。Scheme语言就采用这种表达式表示法。
求值后缀表达式的通用算法是:
用一个栈来存储中间结果。
从左到右读取表达式的每个元素:
若为操作数,直接将其压入栈中;
若为运算符,则弹出栈顶的两个操作数,进行运算,结果再压入栈中。
表达式求值结束后,栈中剩下的一个元素即为最终结果。
例如表达式2 7 5 - * 8 5 - *的求值过程是:
2,压入栈中7,压入栈中5,压入栈中-,弹出7和5,计算7-5=2,结果压入栈中*,弹出2和2,计算2*2=4,结果压入栈中21中缀表达式解析最简单的方法是:先将它转换为后缀表达式,然后直接使用后缀表达式求值算法计算结果。
转换算法步骤:
使用链表作为操作符栈。
从左到右读取中缀表达式。
遇到操作数直接输出。
遇到运算符,根据优先级规则:
如果遇到的操作符优先级高于或者等于栈顶元素,则直接入栈。
如果低于栈顶元素,则弹出栈顶元素并输出,再入栈。
表达式遍历结束后,将栈内剩余元素依次弹出输出。
输出的结果就是后缀表达式。
例如中缀表达式3 + 4 * 7 :
3,输出3+,入栈+4,输出4*,*的优先级高于+,入栈*7,输出7*弹出并输出,再弹出+并输出3 4 7 * +给定一个后缀表达式字符串,要求计算其值。
主要步骤:
定义一个 operate() 方法,用于执行单个运算。
主函数读取后缀表达式每个字符:
若为操作数,压入操作数栈
若为运算符,则调用 operate() 方法进行运算,结果入栈
表达式遍历完,栈内剩余元素即为结果
例如输入后缀表达式字符串"7 3 * 2 +" ,计算过程:
7,入栈3,入栈*,调用operate('*', 3, 7)=21,结果入栈2,入栈+,调用operate('+', 21, 2)=23,结果入栈从而可以轻松实现后缀表达式的求值。
在Java中,对象占用内存空间。程序创建了很多对象后又遗忘,但这些对象是否仍然占用内存空间?Java可以重用这些空间为新对象服务吗?
在C/C++中,程序员需要手动释放内存。但Java可以自动回收程序不再使用的对象,这就是垃圾回收。
存活对象(Live Object):程序可能继续使用的对象。
垃圾对象(Garbage):程序再也无法引用的对象。
垃圾回收的目标是:不收集存活对象,只收集垃圾对象以释放其内存。
Java虚拟机使用隐藏的数据结构追踪所有对象的引用关系,构建一个引用图。
垃圾回收从根开始(本地变量、静态变量等直接可引用的对象),使用深度优先搜索算法寻找与根相连接的存活对象。
如果对象无法从根对象访问到,则该对象属于垃圾,可以被回收。每一个对象都有一个”已访问”标记。
计算机内存就是一个很大的字节数组。每个字节都有一个地址作为索引。
若32位系统,一次通常读取或者写入4个字节(一个int或者pointer)。因此可以把地址看作每4个地址作为一个单位。
在Java中,当定义局部变量时,给变量赋一个内存地址。但具体地址由JVM选择。本地变量就是根对象。
JVM会隐藏地追踪所有对象之间的引用关系,实现对象的回收。
垃圾收集器主要有三种:
标记清除收集器:标记所有可以访问的对象,然后清除未标记的对象。
复制收集器:内存拷贝活着的对象到一个新的地方,放弃旧区域。
代收集器:内存分为几个代,不同代对象的存活时间不同,采用不同的垃圾收集方式。
代收集器一般有老年代和幼年代:
老年代对象存活时间长,使用标记清除收集器。
幼年代内存分为食田区和幸存区。
食田区为新对象分配空间,当满了进行GC。
幸存区使用复制收集器实现。
当对象在幸存区成功复制若干次,即可入选老年代。
老年代对象可能指向幼年代对象,如果不跟踪,在幼年代GC时可能误删依赖对象。
因此需维护一个表,记录老年代到幼年代的引用。但由于老年代对象变化小,开销也较低。
代收集器通过划分代来实现不同对象有针对性的垃圾回收,提高了内存利用率和GC效率。关键是定位和处理老年代到幼年代的跨代引用问题。