算法设计与分析期末考试复习(二)

news/2024/3/29 20:38:52/文章来源:https://blog.csdn.net/Caramel_biscuit/article/details/129194718

分治法

将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。最好使子问题的规模大致相同。

  1. 分解(Divide):将一个难以直接解决的大问题,分割成一些规模较小的子问题,这些子问题互相独立,且与原问题相同。
  2. 递归求解子问题,若问题足够小则直接求解。
  3. 将各个子问题的解合并得到原问题的解。

求二叉树深度

int get_depth(BTPtr pbt){int dL,dR=0;if(pbt == NULL){return 0;}if((!ptb->lchild) && (!ptb->rchild)){return 1;}dL = get_depth(pbt->lchild);dR = get_depth(pbt->rchild);return 1 + ((dL>dR)?dL:dR);
}

分治法所能解决的问题一般具有四个特征:

  1. 该问题的规模缩小到一定的程序就可以容易地解决。
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
  3. 利用子问题的解可以合并得到原始问题的解。
  4. 各个子问题是相互独立的。

二分搜索技术,每执行一次算法while循环,待搜索数组的大小减少一半,因此最坏时间复杂度O(log n)

int BinarySearch(int a[],int x,int left,int right){while(left <= right){int mid = (left + right)/2;if(a[mid] == x){return mid;}else if(a[mid] < x){left = mid + 1;}else{right = mid - 1;}}return -1;
}

Master定理(递归复杂度判定定理)

在这里插入图片描述
大整数的乘法:将两个n位大整数相乘
传统逐位相乘、错位相加的传统方法:O(n2),效率太低。
分治法:将该问题分解为若干个规模较小的相同问题。
在这里插入图片描述
在这里插入图片描述
为了降低时间复杂度,必须减少乘法的次数。
在这里插入图片描述
在这里插入图片描述
两个XY复杂度都相同,但(a+b),(c+d)可能得到(n/2)+1位的结果,使问题的规模变大,故不选择第2种方案。

矩阵乘积的传统算法,时间复杂度O(n3)

void multi(int A[],int B[],int C[]){for(int i=1; i<=n ;i++){for(int j=1;j<=n;j++){C[i][j] = 0;for(int k=1 ;k<=n; k++){C[i][j] += A[i][k]*B[k][j];}}}
}

分治法:矩阵乘法
在这里插入图片描述
在这里插入图片描述
为了降低时间复杂度,必须减少乘法的次数。
在这里插入图片描述
棋盘覆盖问题:在一个2kx2k个方格组成的棋盘中,要求用图(b)所示的4种L形态骨牌覆盖给定的特殊棋盘,覆盖给定特殊棋盘上除特殊方格以外的所有方格,任何2个L型骨牌不得重叠覆盖。
在这里插入图片描述
分治策略技巧:使每个子棋盘均包含一个特殊的方格,从而将原问题分解为规模较小的棋盘覆盖问题。
在这里插入图片描述
棋盘覆盖问题中数据结构的设计:

  1. 棋盘:用二维数组board[size][size]表示一个棋盘,其中size=2k。为了在递归处理的过程中使用同一个棋盘,将数组board设为全局变量。
  2. 子棋盘:在棋盘数组board[size][size]中,用子棋盘左上角的tr、tc和棋盘边长s表示。
  3. 特殊方格:用board[dr][dc]表示,dr和dc是该特殊方格在棋盘数组board中的下标。
  4. L型骨牌:一个2k×2k的棋盘中有一个特殊方格,所以,用到L型骨牌的个数为(4k-1)/3,将所有L型骨牌从1开始连续编号,用一个全局变量t表示。
void ChessBoard(int tr,int tc,int dr,int dc,int size){if(size == 1)	return; //棋盘只有一个方格,且是特殊方格。t++;//L型骨牌号,已经初始化为0。s = size/2;//划分棋盘if(dr<tr+s && dc<tc+s){ //特殊方格在棋盘左上角ChessBoard(tr,tc,dr,dc,s);}else{ //用t号L型骨牌覆盖右下角,再递归处理子棋盘board[tr+s-1][tc+s-1] = t;ChessBoard(tr,tc,tr+s-1,tc+s-1,s);}if(dr<tr+s && dc >= tc+s){ChessBoard(tr,tc+s,dr,dc,s);}else{board[tr+s-1][tc+s] = t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}if(dr>=tr+s && dc<tc+s){ChessBoard(tr+s,tc,dr,dc,s);}else{board[tr+s][tc+s-1] = t;ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}if(dr >= tr+s && dc >= tc+s){ChessBoard(tr+s,tc+s,dr,dc,s);}else{board[tr+s][tc+s] = t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}
}
  1. 当k>0时,将2的k次幂乘以2的k次幂分隔成为4个2的k-1次幂乘以2的k-1次幂子棋盘。
  2. 特殊方格必位于4个较小棋盘之一中,其余3个子棋盘中午特殊方格。
  3. 为了将这3个特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌将这3个较小棋盘的汇合处覆盖,这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将原问题转换成4个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为1*1棋盘。

在这里插入图片描述

快速排序:在数组中确定一个记录作为划分元,将数组中关键字小于划分元的记录移动到划分元之前,将数组中大于划分元的记录移动到划分元之后。

int Partition(int *arr,int L,int R){int left = L;int right = R;int pivot = arr[left];while(left < right){while(left<right && arr[right]>=pivot)right--;if(left < right){arr[left] = arr[right];}while(left<right && arr[left]<=pivot)left;if(left<right){arr[right] = arr[left];}if(left == right){arr[left] = pivot;return left;}}
}void QuickSort(int *arr,int L,int R){if(L < R){int position = Partition(arr,L,R);quickSort(arr,L,position-1);quickSort(arr,position+1,R)}
}

最好情况:T(n)=O(nlogn)(每次总是选到中间值作为划分元)
最坏情况:T(n)=O(n2)(每次总是选到最小或最大元素作为划分元)
算法性能与系列中关键字的排列顺序和划分元的选取有关

  1. 当初始序列按关键字有序(正序或逆序)时,快速排序蜕化为冒泡排序,此时算法性能最差,时间复杂度为O(n2)。
  2. 可以用“三者取中”法来选取划分元,设:数组首记录为r[s]、尾记录为r[t],取:r[s]、r[t]和r[(s+t)/2]三者的中间值为划分元。
  3. 也可采用随机选取划分元的方式

快速排序算法的性能取决于划分的对称性。通过修改算法partition,可以设计出采用随机选择策略的快速排序算法。在a[p:r]中随机选出一个元素作为划分基准,这样可以使划分基准的选择是随机的,从而可以期望划分是比较对称的。

int RandomizedPartition(int a[],int p,int r){int i = random(p,r);swap(a[i],a[p]);Partition(a,p,r)
}

线性时间选择:给定线性序集中n个元素和一个整数k,要求找出这n个元素中第k小的元素,问是否可以在O(n)时间内得到解决,可以采用分治法,模仿快排对输入数组进行递归划分,只对划分出的子数组之一进行递归处理,子数组的选择与划分元和k相关。

int RandSelect(int A[],int start,int end,int k){if(start == end){return A[start];}int i = RandomizedPartition(A,start,end);int n = i-start+1;//左子数组的个数if(k <= n){RandSelect(A,start,n,k);}else{RandSelect(A,i+1,end,k-n;)}
}

线性时间内找到合理划分基准的步骤(select函数)

  1. 将n个元素划分成n/5个组,每组5个元素,只有可能一个组不是5个元素。
  2. 用任意一种排序算法对每组中的元素排序。
  3. 取出每组中的中位数,共n/5个元素。
  4. 递归调用select函数,找出这n/5元素中的中位数。
  5. 如果n/5为偶数,就选择2个中位数中较大的一个,以这个选出的元素作为划分基准。

按递增序列,找出下面29个元素的第18个元素:
8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29.

  1. 把前面29个元素分为6组(ceil(29/5));(8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7),(23,22,46,29).
  2. 提取每一组中的中值元素,构成集合{33,49,13,25,16,29}
  3. 递归地使用该算法求得集合中的中值,得到m=29.
  4. 根据m=29,把29个元素划分为3个子数组P={8,17,4,11, 3,13,6,19, 25,16,5,7,23,22},Q={29},R={31,60,33,51,57,49,35,43,37,52,32,54,41,46}
  5. P中有14个元素,Q中有1个元素,所以18-15=3,对R递归地执行本算法。
  6. 将R划分成3组(ceil(14/5)):{31,60,33,51,57},{49,35,43,37,52},{32,54,41,46}
  7. 求取这3组元素的中值元素分别为{51,43,46},这个集合的中值是43.
  8. 根据43将R划分成3组{31, 33, 35,37,32, 41},{43},{60, 51,57, 49, 52,54, 46}
  9. 因为k=3,第一个子数组的元素个数大于k,所以放弃后面两个子数组,以k=3对第一个子数组递归调用本算法;
  10. 将这个子数组分为5个元素为一组: {31,33,35,37,32}、{41},取中值为33。
  11. 根据33,把第一个子数组划分成{31,32},{33},{35,37};
  12. 因为k=3,而第一、第二个子数组的元素个数为3,所以33即为所求取的第18个小元素。
int Select(int a[],int start,int end,int k){if(end-start<75){//用某个简单的算法对数组a[start:end]排序return a[start+k-1];}for(int i=0; i<=(end-start-4)/5; i++){//将a[start+5*i]与a[start+4+5*i]的第3小元素与a[start+i]交换位置}//找出中位数中的中位数int x = Select(a,start,start+(end-start-4)/5,(end-start-4)/10);int i = Partition(a,start,end,x); //划分元位置int n = i-start+1; //左数组长度if(k <= n)	return Select(a,start,i,k);else{return Select(a,i+1,end,k-n);}
}

在这里插入图片描述

最接近点对:给定平面上的n个点,找出其中的一对点,使得在n个点组成的所有点对中,该点对的距离最小。

直观解法:将每一个点与其他n-1个点的距离算出,找出最小距离,时间复杂度:T(n)=n(n-1)=O(n2)
分治法

  1. 分解:将n个点的集合分成大小近似相等的两个子集。
  2. 求解:递归求解两个子集内部的最接近点对。
  3. 合并:从子空间内部最接近点对,和两个子空间之间的最接近点对中,选择最接近点对。
    在这里插入图片描述

分治法

  1. 假设我们用x轴上某个点m将S划分为2个子集S1和S2,基于平衡子问题的思想,用S中各点坐标的中位数来作分割点。
  2. 递归地在S1和S2找出其最接近点对{p1,p2}和{q1,q2}。
  3. 设d=min{|p1-p2|,|q1-q2|},则S中的最接近点对可能是{p1,p2},或者是{q1,q2},或者是某个{p3,q3},其中p3∈S1且q3∈S2。
  4. 如果最接近点对是{p3,q3},即|p3-q3|<d:即p3和q3两者之间的基于不超过d,p3∈(m-d, m],q3∈(m, m+d]。
bool Cpair1(S,d){n = |S|;if(n < 2){d =;return false; }m = S中各点坐标的中位数。构造S1和S2 //构造S1={x  S|x<=m}, S2={x  S|x>m}Cpair(S1,d1);Cpair1(S2,d2);p = max(S1);q = min(S2);d = min(d1,d2,q-p);return true;
}

考虑二维的情况
在这里插入图片描述

  1. 选取二维平面的一条垂直线L:x=m作为分割线,其中m为S中各点x坐标的中位数,由此将S分割成S1和S2。
  2. 递归地在S1和S2上找出其中最小距离d1,d2。
  3. 设d=min{d1,d2},S中的最接近点对间的距离或者是d,或者是某个点对{p,q}之间的距离,其中p∈S1且q∈S2。如果用符号P1和P2分别表示直线 L 的左右两边宽为d的区域,则必有p∈P1且q∈P2

在这里插入图片描述
考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者,则必由distance(p,q)<d,P2中满足条件的点一定落在矩形R中,矩阵R的大小为dx2d。
由d的定义可知:P2中任何2个点(qi∈S)的距离都不小于d,由此可以推出矩形R中最多只有6个S中的点。
在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_73663.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【拿好了!Linux 运维必备的 13 款实用工具!】

​本文介绍几款 Linux 运维比较实用的工具&#xff0c;希望对 Linux 运维人员有所帮助。 查看进程占用带宽情况 – Nethogs Nethogs 是一个终端下的网络流量监控工具可以直观的显示每个进程占用的带宽。 下载&#xff1a; http://sourceforge.net/projects/nethogs/files/ne…

ZYNQ双核处理器独立运行AMP

一、简介多核处理器从多核的结构上是否一致&#xff0c;分为两种基本架构&#xff1a;同构多核架构和异构多核架构。同构多核处理器是指系统中的处理器在结构上是相同的&#xff1b;而异构处理器是指系统中的处理器在结构上是不同的&#xff0c;这些处理器可以是通用处理器&…

pyqt5通过CANoe COM Server来操作CANoe仿真工程

文章目录前言一、COM接口技术二、UI界面设计三、功能实现四、工程运行测试前言 继续学习《CANoe开发从入门到精通》。 今天在《CANoe仿真工程开发》的基础上&#xff0c;开发实现pyqt5应用程序来操控CANoe工程。 一、COM接口技术 COM&#xff08;Component Object Model&…

vue-cli引入wangEditor、Element,封装可上传附件的富文本编辑器组件(附源代码直接应用,菜单可调整)

关于Element安装引入&#xff0c;请参考我的另一篇文章&#xff1a;vue-cli引入Element Plus&#xff08;element-ui&#xff09;&#xff0c;修改主题变量&#xff0c;定义全局样式_shawxlee的博客-CSDN博客_chalk variables 1、安装wangeditor npm i wangeditor --savewangE…

【OpenFOAM】-olaFlow-算例10-wavemakerTank

算例路径&#xff1a; olaFlow\tutorials\wavemakerTank 算例描述&#xff1a; 采用 Flap和Piston两种方式的动网格进行造波 学习目标&#xff1a; 了解 olaDyMFlow 的使用&#xff1b;理解动网格使用和参数设置&#xff0c;理解 dynamicMotionSolverFvMesh 参数设置&#xff1…

【华为OD机试模拟题】用 C++ 实现 - 环中最长子串(2023.Q1)

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

【Linux修炼】14.磁盘结构/文件系统/软硬链接/动静态库

每一个不曾起舞的日子&#xff0c;都是对生命的辜负。 磁盘结构/文件系统/软硬链接/动静态库前言一.磁盘结构1.1 磁盘的物理结构1.2 磁盘的存储结构1.3 磁盘的逻辑结构二.理解文件系统2.1 对IO单位的优化2.2 磁盘分区与分组2.3 分组的管理方法2.4 文件操作三.软硬链接3.1理解硬…

vue手写日历

<template><div class"page">输入月份数字<input v-model"inputVal" type"text"><button click"change">点击</button><ul class"calendar"><li class"header">{{new …

记忆总掉线?这些行为太伤脑!

人体老化过程中&#xff0c;记忆力的衰退不可避免&#xff0c;这种属于“良性”的记忆衰退。但非“良性”的记忆衰退可要重视&#xff0c;很可能是痴呆症的早期征兆。由于各种原因&#xff0c;我们各种熬夜。作息的不规律扰乱大脑神经系统的调节。这种长期慢性损害大脑&#xf…

WebDAV之π-Disk派盘+Cloud Player

Cloud Player 支持WebDAV方式连接π-Disk派盘。 推荐一款云媒体播放器是存储在常见云平台中的内容的通用播放器。 Cloud Player云媒体播放器是存储在常见云平台中的内容的通用播放器,无需将其下载到设备。支持以下云平台:Google Drive、DropBox、One Drive、WebDav等。此外,…

超纯水制备,MB-106UP抛光树脂的技术解析

超纯水&#xff08;Ultrapure water&#xff09;又称UP水&#xff0c;是指电阻率达到18 MΩ*cm&#xff08;25℃&#xff09;的水。这种水中除了水分子外&#xff0c;几乎没有什么杂质&#xff0c;更没有细菌、病毒、含氯二噁英等有机物&#xff0c;当然也没有人体所需的矿物质…

【ArcGIS Pro二次开发】(7):地图(Map)的基本操作

地图是ArcGIS Pro中的基础起点&#xff0c;也是大多数工程的基础。主要用于显示表示空间数据的图层。 一、地图(Map)的基本操作示例 1、获取当前地图 var map MapView.Active.Map; 2、获取一级图层 var lys map.Layers; 用于获取地图中的单一图层&#xff0c;以及图层组…

深入了解Java线程锁(一)

在上一篇《如何保证线程的原子性》中&#xff0c;我们谈到了锁&#xff08;Synchronized&#xff09;&#xff0c; 这次我们就来深入探讨一下Java多线程中的锁。 互斥锁的本质是共享资源。 如上图所示&#xff0c; Thread1访问受保护资源&#xff0c;对其加锁&#xff0c;将…

【GO】k8s 管理系统项目16[前端部分–前端布局]

【GO】k8s 管理系统项目[前端部分–前端布局] 1. 前端布局 2. Layout 2.1 layout src/layout/Layout.vue <template><div class"common-layout"><el-container><el-side width"200">Aside</el-side><el-container>…

CAN总线开发一本全(3) - 微控制器集成的FlexCAN外设

CAN总线开发一本全&#xff08;3&#xff09; - 微控制器集成的FlexCAN外设 苏勇&#xff0c;2023年2月 文章目录CAN总线开发一本全&#xff08;3&#xff09; - 微控制器集成的FlexCAN外设引言硬件外设模块系统概要总线接口单元 - 寄存器清单数据结构 - 消息缓冲区MB初始化过…

React(一):初识React、类组件、jsx的基础语法

React&#xff08;一&#xff09;一、初识React1.简单介绍2.React的三个依赖3.Hello React案例二、类组件1.定义类组件并渲染2.绑定事件函数&#xff08;奇怪的this问题&#xff09;3.数组形式数据的展示&#xff08;电影案例&#xff09;4.计数器案例三、jsx语法详解1.jsx的书…

利用InceptionV3实现图像分类

最近在做一个机审的项目&#xff0c;初步希望实现图像的四分类&#xff0c;即&#xff1a;正常&#xff08;neutral&#xff09;、涉政&#xff08;political&#xff09;、涉黄&#xff08;porn&#xff09;、涉恐&#xff08;terrorism&#xff09;。有朋友给推荐了个github上…

机器学习笔记之近似推断(一)从深度学习角度认识推断

机器学习笔记之近似推断——从深度学习角度认识推断引言推断——基本介绍精确推断难的原因虽然能够表示&#xff0c;但计算代价太大无法直接表示引言 本节是一篇关于推断总结的博客&#xff0c;侧重点在于深度学习模型中的推断任务。 推断——基本介绍 推断(Inference\text{…

Python中实现将内容进行base64编码与解码

一、需求说明需要使用Python实现将内容转为base64编码&#xff0c;解码&#xff0c;方便后续的数据操作。二、base64简介Base64是一种二进制到文本的编码方式【是一种基于 64 个可打印字符来表示二进制数据的表示方法&#xff08;由于 2^664&#xff0c;所以每 6 个比特为一个单…

国产音质好的蓝牙耳机有哪些?国产音质最好的耳机排行

随着时间的推移&#xff0c;真无线蓝牙耳机逐渐占据耳机市场的份额&#xff0c;成为人们日常生活中必备的数码产品之一。蓝牙耳机品牌也多得数不胜数&#xff0c;哪些国产蓝牙耳机音质好&#xff1f;下面&#xff0c;我们从音质出来&#xff0c;来给大家介绍几款国产蓝牙耳机&a…