数据结构与算法
算法时间复杂度
度量一个程序(算法)执行时间的两种方法
事后的统计方法:
这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。
事前估算的方法：
通过分析某个算法的时间复杂度来判断哪个算法更优.
时间频度
基本介绍
时间频度：
一个算法花费的时间与算法中语句的执行次数成正比，那个算法中语句执行的次数多，它花费的时间就多，一个算法中的语句执行次数称为语句频度或者时间频度，记作T(n)。
举例说明-时间频度
比如计算1-100所有数字之和，我们设计两种算法：
int total = 0; int end = 100; for(int i;i<=end;i++){ total += i; } //这里这个语句就执行了100次 //T(n) = n+1; //直接计算 total = (1+end) * end/2 //T(n) = 1;
举例说明-忽略常数项
结论:
- 2n+20 和 2n 随着n 变大，执行曲线无限接近, 20可以忽略
- 3n+10 和 3n 随着n 变大，执行曲线无限接近, 10可以忽略
举例说明-忽略低次项
结论:
- 2n^2+3n+10 和 2n^2 随着n 变大, 执行曲线无限接近, 可以忽略 3n+10
- n^2+5n+20 和 n^2 随着n 变大,执行曲线无限接近, 可以忽略 5n+20
举例说明-忽略系数
结论:
- 随着n值变大，5n^2+7n 和 3n^2 + 2n ，执行曲线重合, 说明 这种情况下, 5和3可以忽略。
- 而n^3+5n 和 6n^3+4n ，执行曲线分离，说明多少次方式关键
时间复杂度的计算方式
时间复杂度的介绍
一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。
T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。
计算时间复杂度的方法：
用常数1代替运行时间中的所有加法常数 T(n)=3n²+2n+2 => T(n)=3n²+2n+1
修改后的运行次数函数中，只保留最高阶项 T(n)=3n²+2n+1 => T(n) = 3n²
去除最高阶项的系数 T(n) = 3n² => T(n) = n² => O(n²)
常见的时间复杂度
- 常数阶O(1)
- 对数阶O(log2n)
- 线性阶O(n)
- 线性对数阶O(nlog2n)
- 平方阶O(n^2)
- 立方阶O(n^3)
- k次方阶O(n^k)
- 指数阶O(2^n)
说明：
- 常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低
- 从图中可见，我们应该尽可能避免使用指数阶的算法
时间复杂度的举例说明（常见）
常数阶O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)
int i = 1; int j = 2; ++i; ++j; int m = i+j; //这里的代码不管i,j是多少他都执行一次所以这里的时间复杂度就为o
对数阶O(log2n)
int i = 1; while(i<n){ i = i * 2; } //在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(log2n) 。 O(log2n) 的这个2 时间上是根据代码变化的，i = i * 3 ，则是 O(log3n)
线性复杂度O(n)
int j = 0; for(i = 1; i<=n;++i){ j=i; j++; } //这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度
平方阶O(n²)
for(int m=1;m<n;m++){ i=1; while(i<n){ i = i*2; } } //线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)
线性阶对数阶(n log N)
for(int m=1;m<n;m++){ i=1; while(i<n){ i = i*2; } } //线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)
平均时间复杂度和最坏时间复杂度
- 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
- 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
- 平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如图:)。
空间复杂度
基本介绍
- 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
- 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况
- 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.
稀疏数组
基本介绍
当一个数组中大部分元素为0，或者为同一个值得数组时，可以用稀疏数组来进行压缩储存
处理方法
1)记录数组一共有几行几列，有多少个不同的值
2)把具有不同值得元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
实际应用（棋盘上的棋子作为案例）
二维数组转稀疏数组的思路
1.遍历二维数组中的所有的有效值并统计为一个sum
2.根据sum可以创建对应的稀疏数组的行
sparseArr int[sum+1][3]
3.根据二维数组中的有效数据存入到稀疏数组中,分别对应的是 实际的行减一就是下标不是从0开始区分数学上的行，所以上图的就是
【0】（一维数组的索引值） row（这个矩阵有多少行） col（列） val (有多少个有效值)（这一行可以说是一个总结，下面就是单独拎出来）
11 11 2
【1】 row（有效值的行位置） col(列) val（这个位置对应的有效值）
1 2 1
【2】 2 3 2
代码实现
//先创建一个二维数组,表示棋盘 //0：表示没有棋子，1表示黑子，2表示篮子 int[][] ChessArray = new int[11][11]; ChessArray[1][2] = 1; ChessArray[2][3] = 2; ChessArray[5][8] = 2; //原始的二维数组 System.out.println("原始二维数组"); for (int[] ints : ChessArray) { for (int anInt : ints) { System.out.print(anInt + " "); } System.out.println(" "); } //二维数组转化为稀疏数组 /** * 先遍历所有的值，去除大于零和相同的值 * 将有效值个数用sum来表示 * 稀疏数组的行数就为sum+1，列为3 */ int sum = 0; for (int i = 0; i < ChessArray.length; i++) { for (int j = 0; j < ChessArray[i].length; j++) { if (ChessArray[i][j] != 0) { sum++; } } } //创建对应的稀疏数组 int[][] Spares = new int[sum + 1][3]; //给稀疏数组赋值 Spares[0][0] = 11; Spares[0][1] = 11; Spares[0][2] = sum; //遍历二维数组将非0的数值放入稀疏数组中 int count = 0; for (int i = 0; i < ChessArray.length; i++) { for (int j = 0; j < ChessArray[i].length; j++) { if (ChessArray[i][j] != 0) { count++; Spares[count][0] = i; Spares[count][1] = j; Spares[count][2] = ChessArray[i][j]; } } } //输出稀疏数组 System.out.println(); System.out.println("得到的稀疏数组为"); for (int[] spare : Spares) { for (int i : spare) { System.out.print(i+"\t"); } System.out.println(); }
稀疏数组转二位数组思路
先将稀疏数组的第一行读出来，根据第一行的数据来创建二维数组比如上面的棋盘
int [][] ChrreyAarry = new int [11][11]
然后将稀疏数组后的每一行的数据放回到二维数组当中
charreyAarry[1][2] = 1; charreyAarry[2][3] = 2;
//将稀疏数组转化为二位数组 /** * 先将稀疏数组中的第一行的数据拿出来作为二维数组的行和列 * 然后将稀疏数组后的每一行的数据放回到二维数组当中 */ int row = Spares[0][0]; int col = Spares[0][1]; int[][] ChessArray1= new int[row][col]; for (int i = 1; i < Spares.length; i++) { int Crow = Spares[i][0]; int Ccol = Spares[i][1]; int Val =Spares[i][2]; ChessArray1[Crow][Ccol] = Val; } System.out.println(); System.out.println("恢复后的二维数组"); for (int[] ints : ChessArray1) { for (int anInt : ints) { System.out.print(anInt+" "); } System.out.println(); }
队列
队列介绍
- 队列是一个有序列表，可以用数组或者链表来实现
- 遵循先进先出的原则，即：先存入队列的数据，要先取出，后存入的数据要后取出
示意图：（使用数组模拟队列示意图）
数组模拟队列
- 队列本身是一个有序列表，若使用数组的结构来储存队列的数据，则队列数组的申明如下图，其中max Size是该队列的最大容量。
- 因为队列的输出，输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据的输出而改变，而rear则是随着数据输入而改变。
如图：
3.当我们将数据存入队列时被称为”addQueue“,addQueue的处理需要有两个步骤：
思路分析
1）将尾指针往后移：rear+1 当front == rear 数组为【空】
2）若尾指针rear小于队列的最大下标 maxSize-1,则将数据存入rear所指的数组元素中，否则无法存入数据，rear == maxSize - 1 [队列满]。front不包含队列头部的第一个数据，rear包含队列尾部最后的一个数据
代码实现
class ArrayQueue { private int MaxSize;//这个数组的最大容量 private int front;//这个数组的尾指针 private int rear;//这个数组的前指针 private int[] arr;//创建一个数组变量 //创建数组的队列数组的构造器 public ArrayQueue(int maxSize) { this.MaxSize = maxSize; arr = new int[maxSize]; front = -1;//不包含队列头的数据 rear = -1;//包含队列尾部的数据 } //判断队列是否为满 public boolean IsFull() { return rear == MaxSize - 1; } //判断队列是否为空 public boolean IsEmpty() { return rear == front; } //添加数据到队列 public void AddQueue(int n){ if (IsFull()){ System.out.println("队列满不能加入数据"); return; } rear++;//让他后移 arr[rear] = n; } //让数据出队列 public int getQueue(){ //判断是否为空 if (IsEmpty()){ throw new RuntimeException("队列为空无法取出数据"); } front++; return arr[front]; } //展示所有数据 public void showQueue(){ //遍历 if (IsEmpty()){ System.out.println("队列为空，拿不出来呀"); } for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } //显示头部数据,不是取出数据 public int showHead(){ if (IsEmpty()){ throw new RuntimeException("队列为空，拿不出来呀"); } return arr[front+1]; } }
完整代码展示
public class ArrayQueueDemo { public static void main(String[] args) { //创建一个队列 ArrayQueue arrayQueue = new ArrayQueue(3); String key = ""; Scanner scanner = new Scanner(System.in); boolean flag = true; while (flag){ System.out.println("s (show)显示队列"); System.out.println("e (exist)退出程序"); System.out.println("a (add) 添加数据"); System.out.println("g (get)从队列取出数据"); System.out.println("gd (showHead)得到数据"); key = scanner.next(); switch (key){ case "s": arrayQueue.showQueue(); break; case "a": System.out.println("请输入你要添加的数据"); int num = scanner.nextInt(); arrayQueue.AddQueue(num); break; case "g": try{ int a = arrayQueue.getQueue(); System.out.println("取出的数据是"+a); } catch (Exception e) { System.out.println(e.getMessage()); } break; case"gd": try{ int a = arrayQueue.showHead(); System.out.println("取出的数据是"+a); } catch (Exception e) { System.out.println(e.getMessage()); } break; case "e": flag = false; break; default: System.out.println("你的输入有误请重新输入"); break; }} } } //使用数组模拟队列 class ArrayQueue { private int MaxSize;//这个数组的最大容量 private int front;//这个数组的尾指针 private int rear;//这个数组的前指针 private int[] arr;//创建一个数组变量 //创建数组的队列数组的构造器 public ArrayQueue(int maxSize) { this.MaxSize = maxSize; arr = new int[maxSize]; front = -1;//不包含队列头的数据 rear = -1;//包含队列尾部的数据 } //判断队列是否为满 public boolean IsFull() { return rear == MaxSize - 1; } //判断队列是否为空 public boolean IsEmpty() { return rear == front; } //添加数据到队列 public void AddQueue(int n) { if (IsFull()) { System.out.println("队列满不能加入数据"); return; } rear++;//让他后移 arr[rear] = n; } //让数据出队列 public int getQueue() { //判断是否为空 if (IsEmpty()) { throw new RuntimeException("队列为空无法取出数据"); } front++; return arr[front]; } //展示所有数据 public void showQueue() { //遍历 if (IsEmpty()) { System.out.println("队列为空，拿不出来呀"); }else { for (int i = 0; i < arr.length; i++) { System.out.printf("arr[%d] = %d",i,arr[i]); System.out.println(); } } } //显示头部数据,不是取出数据 public int showHead() { if (IsEmpty()) { throw new RuntimeException("队列为空，拿不出来呀"); } return arr[front + 1]; } }
问题分析
但是这个数据队列有一个很大的缺陷，这个数组只能使用一次，会有假溢出，而不能重复使用，如果要重复使用就要用到环形队列。
而环形队列则是用取模来实现%
取模运算的步骤：
(1) - 求整数商
c = a / b
(2) - 求模
r = a - c * b
数组模拟环形队列
使用数组模拟环形队列的思路分析
思路如下：
- front的含义发生变化，现在的front由指向数组的第一个的前一个改变为指向数组的第一个
- front = 0（初始值）
- rear的含义发生变化，rear指向队列的后一个元素的后一个位置，流出一块空间作为约束
- rear = 0（初始值）
- 当队列满时，判断满的方法为（rear+1）% MaxSize = front【满】（此时的rear在元素最后的一个位置，rear+1预留出一个空间，这时 (rear+1) %MaxSize为0 == front 这时候就为满 ）
- 当队列空时，判断空的方法为 rear == front
- 判断数组中的有效数据，(rear + MaxSize - front) % MaxSize (加MaxSize是为了避免rear - front是负数，因为这是一个环形队列)
仔细分析
队列最大长度匹配数组容量导致一种错误的解决方案
这就会有一个问题，随着队列中元素的不断更迭，front和rear很快就会超过数组容量，造成数组索引越界
比如上图所示，front=2，也就是说已经有两个元素出列了，因此rear=5与rear=6对应的两个元素理应可以入列，但是我们发现数组maxsize=5，不存在索引位5和6，强行对这两个下标赋值会造成索引越界异常indexOutException 。但是我们发现此时数组中索引位0和1都空着，完全可以将这两个位置利用起来，因此我们可以想办法让实际的rear值转化为等效的rear值，也就是是让rear=5转化为rear=0，同理rear6转化为rear=1。怎么做到呢？无疑是通过取余！
每次新元素入队后， 执行rear=(rear)%maxSize操作，随后执行rear++操作右移rear指针,但是这种做法是有缺陷的。
像上图中的rear=rear%5乍一看好像没问题，但实际上这种取余方式是有问题的，出现这种取余方式的根源在于我们想让队列最大长度与数组容量保持一致，
我们怎么判断队列为空呢？
如果我们按照指针从左到右的方向移动，当front指针和rear指针重合时，front指针对应的索引位之前的索引位都已经出列完毕，而rear指针对应的索引位以及之后的所有索引位还未有元素入列。
所以队列是否为空的判别：front==rear
rear=rear%maxSize解决方案的问题
下图展示了maxSize=5的数组中，front=0保持不变，元素依次入列直到满载，rear指针的移动情况：
可以看到，如果我们认为队列容量与数组容量应该持平，那么当第五个元素50入列后，本来rear=4执行了rear++的操作后，rear=5，随后rear将会通过取余算法rear=rear%maxSize重置为0。
但关键点就在这里，我们发现空载时front=rear=0，满载时依然有front=rear=0！这样子我们就无法判断front=rear时，队列是空还是满，因此rear=rear%maxSize这种解决方案是不被允许的。
新的解决方案：置空位的引入
每次新元素入队后， 执行rear=(rear+1)%maxSize操作，该操作包含rear++操作，如果这里不在括号内加1，那么最后一个位置就不会置空并且会由元素入列。
并且我们人为规定，数组中必须留有一个索引位不得放置元素，必须置空！！！如何实现我们的人为规定呢？那就要先探索当数组满载后front和rear指针之间有啥关系。
入队图示
下图展示了maxSize=5的数组中，front=0保持不变，元素依次入列直到满载，rear指针的移动情况：
人为的让最后一位置空，所以当元素40入列后，数组已经满载
满载后数据之间的关系：
- front=0
- rear=(rear+1)%maxSize=(3+1)%5=4 (注： 执行完arr[rear]=40，再执行 rear=(rear+1)%maxSize)
- (rear+1)%maxSize=(4+1)%5=0==front
当我们认为的满载发生后，最后一位置空，发现此时rear和front之间的关系为(rear+1)%maxSize=(4+1)%5=0==front，因此这个关系可以作为满载的条件
因为处于满载状态，我们无法再往队列添加元素，只能从队列取出元素，也就是进行出列的操作，而一旦我们执行了出列的操作，比如将索引位i=0上的元素10出列后，则front右移，即执行front=(front+1)%maxSize操作，最终front=1。
若随后又添加元素入列，即在索引位i=4上添加元素50，随后又会执行rear=(rear+1)%maxSize操作，最终rear=0。
rear=0≠front=1，此时就不会出现之前那种错误方案中 rear=front=0导致歧义的情况，而一旦 rear=front=0，必然表示队列为空，因此这种解决方案是行得通的
队列为满的判别
当我们认为的满载发生后，最后一位置空，发现此时rear和front之间的关系为(rear+1)%maxSize=(4+1)%5=0==front，因此这个关系可以作为满载的条件：（rear + 1）%maxSize = front
队列中元素的个数
numValid=(rear+maxSize-front)%maxSize，大家可以带入数据验证一下
实际上：
- 当rear在front之后(这里指的是数组中索引位的前后，并非逻辑上的前后)，有效数据个数=rear-front=(rear+maxSize-front)%maxSize
- 当rear在front之前(这里指的是数组中索引位的前后，并非逻辑上的前后)，有效数据个数=(rear+maxSize-front)%maxSize
- 这里主要防止rear - front为负数，取模的话也是负数。
小细节
置空位虽然是人为引入的，但这不意味这置空位的位置是随意的，实际上，只有队列满后才会将剩下的位置作为置空位，一旦置空位出现，rear和front永远不可能指向同一个索引位，因为你会惊奇的发现置空位恰号将rear和front隔开了.
置空位就像一把锁，一旦上锁就只能通过出队列操作解锁
继续执行获取元素操作出队列（解锁）：
上图中60入列后满载，可以看到置空位再次出现，但30➡40➡50➡60➡置空位 形成了逻辑上的闭环。
完整代码
public class CircleArrayQueueDemo { public static void main(String[] args) { //创建一个队列 CircleArray circleArray = new CircleArray(5); String key = ""; Scanner scanner = new Scanner(System.in); boolean flag = true; while (flag) { System.out.println("s (show)显示队列"); System.out.println("e (exist)退出程序"); System.out.println("a (add) 添加数据"); System.out.println("g (get)从队列取出数据"); System.out.println("gd (showHead)得到数据"); key = scanner.next(); switch (key) { case "s": circleArray.showQueue(); break; case "a": System.out.println("请输入你要添加的数据"); int num = scanner.nextInt(); circleArray.AddQueue(num); break; case "g": try { int a = circleArray.getQueue(); System.out.println("取出的数据是" + a); } catch (Exception e) { System.out.println(e.getMessage()); } break; case "gd": try { int a = circleArray.showHead(); System.out.println("取出的数据是" + a); } catch (Exception e) { System.out.println(e.getMessage()); } break; case "e": flag = false; break; default: System.out.println("你的输入有误请重新输入"); break; } } } } class CircleArray { private int MaxSize;//这个数组的最大容量 private int front;//这个从0开始 private int rear;//这个从0开始，到数组最后一个的前一个，留出一个置空位，判断是否满载 private int[] arr;//创建一个数组变量 public CircleArray(int maxSize) { MaxSize = maxSize; arr = new int[maxSize]; } //判断队列是否为满 public boolean IsFull() { return (rear + 1) % MaxSize == front; } //判断队列是否为空 public boolean IsEmpty() { return rear == front; } //添加数据 public void AddQueue(int n) { if (IsFull()) { System.out.println("队列满不能加入数据"); return; } arr[rear] = n; //通过取模防止下标越界 rear = (rear + 1) % MaxSize; } public int getQueue() { //判断是否为空 if (IsEmpty()) { throw new RuntimeException("队列为空无法取出数据"); } //这里要做一个做一个变量去保留拿出来的值 int val = arr[front]; //同rear一样防止索引溢出 front = (front + 1) % MaxSize; return val; } //展示所有数据 public void showQueue() { //遍历 if (IsEmpty()) { System.out.println("队列为空，拿不出来呀"); } else { //加上front的原因就是因为只有加上了front后才能将整个有效的数据遍历完 for (int i = front; i <= (rear + MaxSize - front) % MaxSize + front ; i++) { System.out.printf("arr[%d] = %d", i % MaxSize, arr[i % MaxSize]); System.out.println(); } } } public int showHead() { if (IsEmpty()) { throw new RuntimeException("队列为空，拿不出来呀"); } return arr[front]; } }
