程序员经验分享-hwhale

计算数组中向量之间的最大距离

2024-04-22

假设我们有一个包含 n 个向量的数组。我们想要计算这些向量之间的最大欧氏距离。 最简单（天真的？）的方法是迭代数组，并为每个向量计算其与所有后续向量的距离，然后找到最大值。 然而，这个算法会增长 (n-1)！相对于数组的大小。

对于这个问题还有其他更有效的方法吗？

Thanks.


你对朴素算法复杂性的计算是靠不住的，它应该是O(n(n-1)/2)，这减少到O(n^2)。计算两个向量之间的距离是O(k) where k是向量中元素的数量；这仍然给出了远低于O(n!).

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

complexitytheory

计算数组中向量之间的最大距离 的相关文章

  • 检索受“rowspan”影响的行的列索引的最有效方法是什么？

    考虑下表 table thead tr th th th A th th B th th C th tr thead tbody tr th 1 th td Apples td td Oranges td td Pears td tr tb

  • 删除队列中的最后一个元素

    我需要删除队列的最后一个元素 我唯一可以使用的操作是 Peek 获取第一个元素而不删除它 Enqueue element 向队列末尾插入一个元素 Dequeue 删除第一个元素 IsEmpty true 或 false 队列是否为空 而且我

  • 我需要一个支持高效随机访问和 O(k) 插入和删除的容器

    我再次尝试问同样的问题question https stackoverflow com questions 3808708 delete parts of a dynamic array and grow other 但我最终提出了一个不同

  • 在 C++ 中通过引用传递 std 算法谓词

    我正在尝试从 a 中删除元素std list并保留已删除元素的一些统计信息 为此 我使用列表中的remove if 函数 并且我有一个谓词 我想使用这个谓词来收集统计数据 这是谓词的代码 class TestPredicate privat

  • 数组中连续元素的最大乘积

    我在现场面试的时候被问到了这个算法问题 由于没有要求我签署保密协议 我将其发布在这里寻求答案 给定一个数组REAL不包含 0 的数字 找到产生最大乘积的连续元素 该算法应在线性时间内运行 我考虑过以下方法 使用两个数组 第一个是利用DP思想

  • 关于在字典中查找所有有效单词的算法问题

    给定一个字典 只是一个字符串列表 您收到来自外部来源的未知数量的信件 给定字母串 您将如何列出您可以通过这些字母的任意组合组成的所有有效单词 来自字典 因此 如果您收到 applead 你应该找到apple bad pad lead等 我知

  • 在常数空间中创建 1..N 的随机排列

    我正在寻找枚举固定空间中数字 1 N 的随机排列 这意味着我无法将所有数字存储在列表中 原因是 N 可能非常大 超过可用内存 我仍然希望能够一次遍历这样一个数字的排列 只访问每个数字一次 我知道对于某些 N 可以这样做 许多随机数生成器随机

  • 数学组合的完美最小哈希

    首先定义两个整数N and K where N gt K 两者都在编译时已知 例如 N 8 and K 3 接下来 定义一组整数 0 N or 1 N 如果这使答案更简单 并调用它S 例如 0 1 2 3 4 5 6 7 的子集数量S wi

  • 如何检查是否存在可能的路径？

    我正在开发一个基于 javascript 的实验性游戏 玩家必须在二维平铺地图上移动才能退出 请随意检查这个小提琴并演奏 http jsfiddle net moonlife 74vLd 我只是随机放置障碍物 但有时障碍物会挡住玩家和出口之

  • 给定一个具有多个重复条目的数组，找到一个重复条目 O(N) 时间和常数空间

    我们得到了一个大小为 N 的数组 其中包含 0 到 N 2 范围内的整数 包括 0 和 N 2 该数组可以有多个重复的条目 我们需要在 O N 时间和常量空间中找到重复条目之一 我正在考虑取数组中所有条目的乘积和总和 以及 0 到 N 2

  • 具有 2 个属性的背包算法。如何在 3d 数组中实现它？

    当有超过 1 个属性时 我无法理解背包问题 当有 1 个属性时 我必须编写一个使用具有 2 个属性的背包算法的程序 老师告诉我们 它必须在 3d 数组中完成 错误的实现将导致 O 2 n 处理时间 我无法想象这样的数组会是什么样子 假设这是

  • Florian 的 Grisu2 算法如何工作？

    我遇到了一个关于将 double 转换为 ascii 的问题 经过搜索 我得到了 Florian 的论文 使用整数快速准确地打印浮点数 http www cs tufts edu nr cs257 archive florian loits

  • 两组点之间的最佳匹配

    I ve got two lists of points let s call them L1 P1 x1 y1 Pn xn yn and L2 P 1 x 1 y 1 P n x n y n 我的任务是找到它们点之间的最佳匹配 以最小化它

  • Java递归方法求阶乘返回负输出[重复]

    这个问题在这里已经有答案了 我知道这是溢出 但问题是 20 是相对较小的数字 这不应该发生 对吧 有没有更好的方法来查找大数 例如 1000 的阶乘 而不会得到这种奇怪的结果 public class RecursiveFunctionsE

  • 在java中使用BUBBLE SORT对二维字符串数组进行排序

    类似的问题已经被问过 但从来没有关于二维字符串数组 因此在尝试了很长时间之后我找不到我想要的 我正在尝试使用 BubbleSort 对 java 中的 2D 字符串数组进行排序 作为输入 我收到一个二维字符串数组 一个表 以及您应该排序的

  • n 或 nlog(n) 比常数时间或对数时间更好吗？

    在 Coursera 上的普林斯顿教程中 讲师解释了遇到的常见增长顺序函数 他说 线性和线性算术运行时间是 我们努力的目标 他的推理是 随着输入大小的增加 运行时间也会增加 我认为这是他犯了错误的地方 因为我之前听过他提到线性增长顺序对于高

  • 照片马赛克算法。如何在给定基本图像和瓷砖列表的情况下创建马赛克照片？

    Hy 我要做的是创建一个程序 使用 C 或 C 它将 24 位 像素位图和图像集合作为输入 我必须创建一个马赛克图像 类似于使用库的输入图像给定的图像 创建与输入类似的马赛克照片 到目前为止 我可以访问输入的图像像素及其颜色 但我有点卡住了

  • 需要解释搜索最小大和的算法

    我正在解决 Codility 问题作为练习 但无法回答其中一个问题 我在互联网上找到了答案 但我不明白这个算法是如何工作的 有人可以引导我逐步完成它吗 这是问题 You are given integers K M and a non em

  • 动态规划 (DP) 中的重叠子问题是什么？

    为了使动态规划适用 问题必须具有两个关键属性 最优子结构 and 重叠子问题 1 https en wikipedia org wiki Dynamic programming 对于这个问题 我们只关注后一个属性 有各种不同的定义重叠子问题

  • 归并排序中的递归：两次递归调用

    private void mergesort int low int high line 1 if low lt high line 2 int middle low high 2 line 3 mergesort low middle l

随机推荐

  • 为什么pivot_wider要么将单个值读取为重复项，要么创建一个宽而长的小标题（不合并行）？

    我浏览了此处发布的大部分相关问题 但似乎没有一个问题与我面临的问题相同 根据我的阅读 此处已经发布的问题与长格式数据中的重复值 缺乏唯一标识符 有关 这会导致带有列表列的宽格式数据 这通常可以通过创建虚拟变量列来解决这是一串唯一的数字 我已

  • JTable JComboBox 第一项名称错误

    我添加了一个摇摆JComboBox to a JTable 但我的第一个项目的标签始终是javax swing JComboBox 我究竟做错了什么 更新 这是我的代码 import java awt Color import java a

  • 如何让 Pool.map 采用 lambda 函数

    我有以下功能 def copy file source file target dir pass 现在我想用multiprocessing立即执行此函数 p Pool 12 p map lambda x copy file x target

  • 核心音频指导/入门

    我一直在阅读 ios 4 的核心音频 目的是构建一个小测试应用程序 目前我对所有 api 的研究感到非常困惑 理想情况下 我想知道如何从两个 mp3 中提取多个样本到数组中 然后在回调循环中 我想将这些样本混合在一起并将它们发送到扬声器 苹

  • Delphi - MySQL 最好使用的数据感知组件

    我需要我的应用程序连接到我的 Web 服务器的 MySQL 数据库 最好的选择是什么 首选数据感知组件 我尝试了 zeos 7 但不断收到错误 SQL 错误 客户端不支持服务器请求的身份验证协议 考虑升级MySQL客户端 但未能修复 Tha

  • 在比较分支时，有没有办法在 GitHub 中“隐藏”合并提交？ [关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 help reopen questions 我的 10

  • 如何使用 Junit 对 cordova 插件进行单元测试？

    我已经完成了一些 Cordova 插件 我想对其编写单元测试 这个想法是 例如 在我运行 cordova build android 后 测试文件将被移动到 Android 上的正确文件夹 我可以使用 Java 运行测试 那可能吗 我见过一

  • 如何根据单元格值使用颜色设置 Asp.net GridView 单元格的样式

    我有一个Gridview 它有一个名为student Class 网格视图上大约有 80 个类 我已使用 GroupBy 查询对此类进行分组 现在我想用不同的颜色来设计这个不同的类 这怎么可能 把所有的类都写在上面并不容易RowDataBo

  • Android webView 的 iframe 的 shouldOverrideUrlLoading

    我有一个由 Javascript 控制的本地网站 并将其加载到 WebView 中 该网站实际上是一个带有 iframe 的主页 其内容根据用户输入而变化 主页上有一个 下一步 按钮 它运行一些 javascript 函数并决定在 ifra

  • 两个数组的乘积之和（点积）

    首先 我知道我的标题可以更好地表述 但我的数学课已经结束了 我已经记不起正确的单词了 我需要做这样的事情 伪c int digits1 new int 10 0 1 2 3 4 5 6 7 8 9 int digits2 new int 1

  • Material Design lite 所需的复选框验证未显示错误消息

    我正在使用 Material Design Lite 来制作表单 我面临的问题是 当在复选框上设置所需的验证时 它似乎在渲染后立即隐藏错误消息 请注意 实际验证正在按预期进行 只是未显示错误消息 这是一个解决这个问题的代码笔 http co

  • Android Gradle：找不到符号变量

    我在使用 gradle 构建时遇到错误 如下所示 error cannot find symbol variable image name 我在用着ContextCompat getDrawable getActivity R drawab

  • 在Python中将字符串截断为特定字节数

    如何将字符串截断为不超过 50 个字节 a asdfzx awelkjawletjawetr dlgawklejtwgasdgsdfgd sdfasdfsdafa rewgargasregawergedrhsedhesrdhrthdrfjy

  • Selenium WebDriver 和下拉框

    如果我想选择下拉框的一个选项 有多种方法可以实现 我一直用 driver findElement By id selection sendKeys Germany 但这并不是每次都有效 有时会选择另一个选项 所以我用谷歌搜索了一下 发现这段

  • 如何使用 awk 将一组重复的行转置为列

    我有一个文本文件 其中包含 7 列数据 格式如下 18030 AAJ51 FTO rs9939609 C 30090620 10 A T 18030 AAJ51 CAT rs1001179 C 11468118 10 C C 18030 A

  • 有没有比“手表制造”更明智的替代方案？

    我遇到了这个有用的提示 如果您经常处理文件并且希望它们自动构建 则可以运行 手表品牌 每隔几秒钟它就会重新运行一次 一切都会构建完成 然而 它似乎一直在吞噬所有的输出 我认为它可能更聪明 也许显示输出流 但抑制 全部 不做任何事情 这样如果

  • Like子句和sql注入

    我对这种情况存有疑问 我在存储过程中有这样的查询 SELECT column1 column2 FROM table1 WHERE column1 like column1 我的问题是 这容易受到 SQL 注入攻击吗 我需要将其更改为这样的

  • 如何在PDF文档之前显示加载屏幕

    在我们的应用程序中 我们有动态生成的 PDF 文档的链接 链接看起来像这样主机 22 5 file 3136 pdf所以对于浏览器来说它就像一个静态的 pdf 文档 单击链接时 它会打开一个新窗口 该窗口仅接收 PDF 文档 无 HTML

  • 仅使用本机库的 C# 简单游戏

    我可以找到一组java 2D 游戏教程 http zetcode com tutorials javagamestutorial and 安卓游戏教程 http obviam net index php table of contents

  • 计算数组中向量之间的最大距离

    假设我们有一个包含 n 个向量的数组 我们想要计算这些向量之间的最大欧氏距离 最简单 天真的 的方法是迭代数组 并为每个向量计算其与所有后续向量的距离 然后找到最大值 然而 这个算法会增长 n 1 相对于数组的大小 对于这个问题还有其他更有

热门标签