当前位置: 首页 > news >正文

免费俄语网站制作/定制网站制作公司

免费俄语网站制作,定制网站制作公司,品牌网站设计公司哪家好,南阳卧龙区高端网站建设价格这里写自定义目录标题分治法概述特点大数相乘问题分治算法矩阵相乘分治算法残缺棋盘分治算法分治法概述 在分而治之的方法中,一个问题被划分为较小的问题,然后较小的问题被独立地解决,最后较小问题的解决方案被组合成一个大问题的解决。 通常…

这里写自定义目录标题

  • 分治法概述
  • 特点
    • 大数相乘问题
      • 分治算法
    • 矩阵相乘
      • 分治算法
    • 残缺棋盘
      • 分治算法

分治法概述

在分而治之的方法中,一个问题被划分为较小的问题,然后较小的问题被独立地解决,最后较小问题的解决方案被组合成一个大问题的解决。
通常,分治算法有三个部分:

  • 分解:将问题划分为若干子问题,这些子问题是同一问题的较小实例。
  • 解决:通过递归地解决子问题来征服它们。如果它们足够小,则将子问题作为基本情况解决。
  • 合并:将子问题的解决方案合并为原始问题的解决方法。

特点

分治方法支持并行性,因为子问题是独立的。因此,使用该技术设计的算法可以在多处理器系统上或在不同的机器上同时运行。在这种方法中,大多数算法都是使用递归设计的,因此内存管理非常高。对于递归函数堆栈,需要存储函数状态。

大数相乘问题

  • 输入:两个n位整数X和Y。

  • 输出:X和Y的乘积。

  • 示例:X=1980 Y=2315

  • 在这里插入图片描述

  • 这是你在小学学的算法。注意这需要O(n2) 时间

分治算法

  • 按如下方式分解XY,得到一个新的计算公式,但这个公式仍然要计算:ac、ad、bc、bd四个乘式在这里插入图片描述

  • 因此它的递归式为:在这里插入图片描述

  • 运用主方法可以求出,递归式的解为T(n)=O(n2)。与原始方法相比,该方法没有显著改进。为了减少时间复杂性,我们必须减少乘法次数

  • 修改计算公式如下:在这里插入图片描述

  • 最后两个XY乘法方案的复杂度为O(nlog3),但考虑到a+b,c+d可能得到n+1位的结果,这使得问题的规模更大,因此没有选择第三个方案。

  • 可以列出如下递归式:在这里插入图片描述

  • 解得T(n)=O(nlog3)=O(n1.59)

矩阵相乘

  • 让我们考虑两个矩阵A和B。我们想通过乘以A和B来计算得到的矩阵C。
  • 朴素方法是如果A=(aij)和B=(bij)是n×n的矩阵,那么在乘积C=A·B中,我们定义条目cij,对于i,j=1,2,。。。,n、 通过cij=∑k=1naik⋅bkjcij=\sum^n_{k=1}a_{ik}·b_{kj}cij=k=1naikbkj
  • 我们必须计算n2个矩阵条目,每个条目都是n个值的总和。
  • 我们假设整数运算需要O(1)时间。该算法中有三个for循环,一个嵌套在另一个循环中。因此,该算法需要O(n3)时间来执行在这里插入图片描述

分治算法

下面是两个方阵相乘的简单除法。

  • 将矩阵A和B分成4个子矩阵,大小为N/2×N/2,如下图所示。
  • 递归计算以下值在这里插入图片描述
  • 在上述方法中,我们对大小为N/2×N/2的矩阵进行了8次乘法运算和4次加法运算。两个矩阵相加需要O(n2) 时间。因此,时间复杂度为T(n)= 8T(n/2)+O(n2) 。根据主定理,上述方法的时间复杂度为 O(n3),不幸的是,这与上述朴素方法相同。简单的分治也会导致O(n3),有更好的方法吗?
  • 在上述分治的方法中,高时间复杂度的主要组成部分是8个递归调用。Strassens方法的思想是将递归调用的数量减少到7。Strassens方法与上述简单除法和征服法相似,因为该方法也将矩阵划分为大小为N/2×N/2的子矩阵,如上图所示,但在Strassens法中,使用以下公式计算结果的四个子矩阵。
  • Strassen算法定义了新的矩阵在这里插入图片描述
  • 仅使用7次乘法(对每个MkM_kMk)而不是8次。我们现在可以用Mk表示Ci:在这里插入图片描述
  • 两个矩阵的加法和减法需要O(n2)时间。因此,时间复杂性可以写成:在这里插入图片描述
  • 根据主定理,上述方法的时间复杂度为O(nlog7),近似于O(n2.8074)
  • Hopcroft和Kerr证明(1971)在两个2×2矩阵的乘法中需要7次乘法。因此,为了进一步提高矩阵乘法复杂度的时间,它不能再基于计算2×2矩阵的7倍乘法的方法。也许应该研究3×3或5×5矩阵的更好算法。目前,最佳计算时间上限为O(n 2.376)。

残缺棋盘

  • 定义:有缺陷的棋盘是一块2k×2k的正方形棋盘,正好有一个有缺陷的正方形
  • 例子:在这里插入图片描述
  • 要求用一种化合物来平铺(覆盖)所有非残缺方格。
    • 化合物是一种L形物体,可以覆盖棋盘的三个方格。
    • 有四个方向:在这里插入图片描述

分治算法

  • 分成四个小棋盘。
  • 其中一个是有缺陷的棋盘。在这里插入图片描述
  • 通过在其他三个棋盘的共同角落放置一个三分之一,使其有缺陷。
  • 递归平铺四个有缺陷的棋盘在这里插入图片描述
  • 设n=2k,d是常数。 设t(k)是平铺2k×2k有缺陷棋盘所花费的时间。然后在这里插入图片描述
  • 这里,c是常数,表示为化合物找到合适位置和旋转化合物以获得所需形状所花费的时间。在这里插入图片描述
  • 由于每个网格必须花费θ(1)时间来放置每个化合物,因此不可能得到一个更快的算法来解决这个问题

相关文章:

算法导论【分治思想】—大数乘法、矩阵相乘、残缺棋盘

这里写自定义目录标题分治法概述特点大数相乘问题分治算法矩阵相乘分治算法残缺棋盘分治算法分治法概述 在分而治之的方法中,一个问题被划分为较小的问题,然后较小的问题被独立地解决,最后较小问题的解决方案被组合成一个大问题的解决。 通常…...

Java【七大排序】算法详细图解,一篇文章吃透

文章目录一、排序相关概念二、七大排序1,直接插入排序2,希尔排序3,选择排序4,堆排序5,冒泡排序5.1冒泡排序的优化6,快速排序6.1 快速排序的优化7,归并排序三、排序算法总体分析对比总结提示&…...

Autosar OS IOC

Inter-OS-Application Communicator 背景和基本原理General purposeIOC functionalityCommunicationNotificationIOC interface背景和基本原理 The IOC implementation shall be part of the Operating System IOC和操作系统紧密相关,是操作系统实现的一部分 The IO…...

记录一次Binder内存相关的问题导致APP被杀的BUG排查过程

事情的起因的QA压测过程发生进程号变更,怀疑APP被杀掉过,于是开始看日志 APP的压测平台会上报进程号变更时间点,发现是在临晨12:20分,先大概确定在哪个日志文件去找关键信息一开始怀疑是crash,然后就在日志…...

设计模式(十)----结构型模式之适配器模式

1、概述 如果去欧洲国家去旅游的话,他们的插座如下图最左边,是欧洲标准。而我们使用的插头如下图最右边的。因此我们的笔记本电脑,手机在当地不能直接充电。所以就需要一个插座转换器,转换器第1面插入当地的插座,第2面…...

【数据结构】——队列

文章目录前言一.什么是队列,队列的特点二、队列相关操作队列的相关操作声明队列的创建1.队列的初始化2.对队列进行销毁3.判断队列是否为空队列4.入队操作5.出队操作6.取出队头数据7. 取出队尾数据8.计算队伍的人数总结前言 本文章讲述的是数据结构的特殊线性表——…...

Android OTA升级常见问题的解决方法

1.1 多服务器编译 OTA 报错 Android7 以后引入了 jack-server 功能,也导致在公共服务器上 编译 Android7 以上的版本时,会出现 j ack-server 报错问题。 在多用户服务器上 编译 dist 时 会出现编译过程中 会将 port_service 和 port_admin 改为 默认的 …...

说说Hibernate

当你在实战项目中需要用到SSH时, 如果你之前只用过Mybatis那自然是不能解决问题的, 因为在很多银行类金融类项目中你可能会使用到Hibernate, 那么关于Hibernate你应该要了解什么呢, 本篇文章就以学习Hibernate框架为目的, 巩固在工作中可能需要用到的这种ORM技术, 同时也欢迎家…...

目标检测论文阅读:DETR算法笔记

标题:End-to-End Object Detection with Transformers 会议:ECCV2020 论文地址:https://link.springer.com/10.1007/978-3-030-58452-8_13 官方代码:https://github.com/facebookresearch/detr 作者单位:巴黎第九大学、…...

Golang sync.Once 源码浅析

本文分析了Golang sync.Once 源码,并由此引申,简单讨论了单例模式的实现、 atomic 包的作用和 Java volatile 的使用。 sync.Once 使用例子 sync.Once 用于保证一个函数只被调用一次。它可以用于实现单例模式。 有如下类型: type instanc…...

C++面向对象(上)

文章目录前言1.面向过程和面向对象初步认识2.引入类的概念1.概念与用法2.类的访问限定符及封装3.类的作用域和实例化4.类的大小计算5.this指针3.总结前言 本文将对C面向对象进行初步介绍,引入类和对象的概念。围绕类和对象介绍一些基础知识,为以后深入学…...

经常用但是不知道什么是BFC?

BFC学习 block formatting context 块级格式上下文 简单理解: 一个独立容器,内部布局不会受到外面的影响 形成条件: 1.浮动元素:float除none之外的值 2.绝对定位:position:absolute,fixed 3.display:inline-blo…...

GO的临时对象池sync.Pool

GO的临时对象池sync.Pool 文章目录GO的临时对象池sync.Pool一、临时对象池:sync.Pool1.1 临时对象的特点1.2 临时对象池的用途1.3 sync.Pool 的用法二、临时对象池中的值会被及时清理掉2.1 池清理函数2.2 池汇总列表2.3 临时对象池存储值所用的数据结构2.4 临时对象…...

高精度算法一

目录 1. 基础知识 2. 大整数 大整数 3. 大整数 - 大整数 1. 基础知识 利用计算机进行数值计算,有时会遇到这样的问题:有些计算要求精度高,希望计算的数的位数可达几十位甚至几百位,虽然计算机的计算精度也算较高了&#xff0c…...

2023年全国最新食品安全管理员精选真题及答案1

百分百题库提供食品安全管理员考试试题、食品安全员考试预测题、食品安全管理员考试真题、食品安全员证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 11.预包装食品的标签内容应使用规范的汉字,但可以同时使用&a…...

C++入门:引用

目录 一. 什么是引用 1.1 引用的概念 1.2 引用的定义 二. 引用的性质和用途 2.1 引用的三大主要性质 2.2 引用的主要应用 三. 引用的效率测试 3.1 传值调用和传引用调用的效率对比 3.2 值返回和引用返回的效率对比 四. 常引用 4.1 权限放大和权限缩小问题 4.2 跨…...

SpringSecurity的权限校验详解说明(附完整代码)

说明 SpringSecurity的权限校是基于SpringSecurity的安全认证的详解说明(附完整代码) (https://blog.csdn.net/qq_51076413/article/details/129102660)的讲解,如果不了解SpringSecurity是怎么认证,请先看下【SpringSecurity的安…...

Java-集合(5)

Map接口 JDK8 Map接口实现子类的特点 Map和Collection是并列关系,Map用于保存具有映射关系的数据:Key-ValueMap中的key和value可以是任何引用类型的数据,会封装到HashMap$Node对象中Map中的key不允许重复,原因和HashSet一样Map…...

研制过程评审活动(四)设计定型阶段

1、设计定型阶段主要任务 设计定型的主要任务是对武器装备性能和使用要求进行全面考核,以确认产品是否达到《研制任务书》和《研制合同》的要求。   设计定型阶段应最终确定《产品规范》、《工艺规范》和《材料规范》的正式版本,并形成正式的全套生产图样、有关技术文件及目…...

【Linux】进程替换

文章目录进程程序替换替换原理替换函数函数返回值函数命名理解在makefile文件中一次生成两个可执行文件总结:程序替换时运行其它语言程序进程程序替换 程序要运行要先加载到内存当中 , 如何做到? 加载器加载进来,然后程序替换 为什么? ->冯诺依曼 因为CPU读取数据的时候只…...

LeetCode171-Excel表列序号(进制转换问题)

LeetCode171-Excel表列序号1、问题描述2、解题思路:进制转换3、代码实现1、问题描述 给你一个字符串columnTitle,表示Excel表格中得列名称。返回该列名称对应得列序号。 例如: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 …...

React SSR

ReactDOMServer 参考链接:https://zh-hans.reactjs.org/docs/react-dom-server.html ReactDOMServer 对象允许你将组件渲染成静态标记。通常,它被使用在 Node 服务端上 // ES modules import * as ReactDOMServer from react-dom/server; // CommonJS v…...

如何系统地优化页面性能

页面优化,其实就是要让页面更快地显示和响应。由于一个页面在它不同的阶段,所侧重的关注点是不一样的,所以如果要讨论页面优化,就要分析一个页面生存周期的不同阶段。 通常一个页面有三个阶段:加载阶段、交互阶段和关…...

Vulnhub 渗透练习(八)—— THE ETHER: EVILSCIENCE

环境搭建 环境下载 靶机和攻击机网络适配都选 NAT 即可。 信息收集 主机扫描 两个端口,22 和 80,且 apache httpd 2.4.0~2.4.29 存在换行解析漏洞。 Apache HTTPD是一款HTTP服务器,它可以通过mod_php来运行PHP网页。其2.4.0~2.4.29版本中…...

华为OD机试题 - 水仙花数 2(JavaScript)| 代码+思路+重要知识点

最近更新的博客 华为OD机试题 - 字符串加密(JavaScript) 华为OD机试题 - 字母消消乐(JavaScript) 华为OD机试题 - 字母计数(JavaScript) 华为OD机试题 - 整数分解(JavaScript) 华为OD机试题 - 单词反转(JavaScript) 使用说明 参加华为od机试,一定要注意不要完全背…...

字符设备驱动基础(二)

目录 一、五种IO模型------读写外设数据的方式 二、阻塞与非阻塞 三、多路复用 3.1 应用层:三套接口select、poll、epoll 3.2 驱动层:实现poll函数 四、信号驱动 4.1 应用层:信号注册fcntl 4.2 驱动层:实现fasync函数 一、…...

看见统计——第三章 概率分布

看见统计——第三章 概率分布 参考 https://github.com/seeingtheory/Seeing-Theory中心极限定理 概率分布描述了随机变量取值的规律。 随机变量Random Variables 🔥 定义:将样本空间中的结果映射到实数的函数 XXX 称为随机变量(random variable)&a…...

【基于众包标注的语文教材句子难易度评估研究 论文精读】

基于众包标注的语文教材句子难易度评估研究 论文精读信息摘 要0 引言1 相关研究2 众包标注方法3 语料库构建3.1 数据收集3.1 基于五点量表的专家标注3.3 基于成对比较的众包标注4 特征及模型4.1 特征抽取4.2 模型与实验设计4.2.1 任务一:单句绝对难度评估4.2.2 任务二:句对相对…...

实例五:MATLAB APP design-APP登录界面的设计

一、APP 界面设计展示 注:在账号和密码提示框输入相应的账号和密码后,点击登录按钮,即可跳转到程序中设计的工作界面。 二、APP设计界面运行结果展示...

作用域和闭包:

1、LHS和RHS查询编译一段代码,需要js引擎和编译器(js引擎负责整个程序运行时所需的各种资源的调度,编译器只是js引擎的一部分,负责将JavaScript源码编译成机器能识别的机器指令,然后交给引擎运行)编译的过程…...