美文网首页
最小向量积

最小向量积

作者: M_lear | 来源:发表于2018-11-08 15:30 被阅读0次

调整数组元素的位置使得两数组向量积最小

问题描述：

有长度为n的数组a，b，问如何调整数组内元素的位置使得 a\cdot b 最小？

解的通俗描述：

对应小的乘大的，大的乘小的，得到的向量积最小。

证明：

  1. 重定义a的逆序
    依据数组b来定义数组a的逆序，假设有a，b对应位置上的两对数a_{i},a_{j}和b_{i},b_{j}，如果有b_{i}<b_{j}时a_{i}>a_{j}，或者b_{i}>b_{j}时a_{i}<a_{j}，则称a_{i},a_{j}为一对逆序，否则不为逆序。
  2. 证明单调
    假设现在有 b_{i}<b_{j}，a_{i}<a_{j}，i=0,1,\cdots,n-1，j=0,1,\cdots,n-1，i\ne j
    则向量积S_{1}=\sum_{k=0,k\ne i,k\ne j}^{n-1}a_{k}\cdot b_{k}+a_{i}\cdot b_{i}+a_{j}\cdot b_{j}
    若现在交换a_{i},a_{j}的位置，即数组a增加了一对逆序。
    向量积变为S_{2}=\sum_{k=0,k\ne i,k\ne j}^{n-1}a_{k}\cdot b_{k}+a_{i}\cdot b_{j}+a_{j}\cdot b_{i}
    可以证得a_{i}\cdot b_{i}+a_{j}\cdot b_{j}>a_{i}\cdot b_{j}+a_{j}\cdot b_{i}（这个简单证明放在第3点）
    即S_{1}>S_{2}
    所以结论是：保持b不变，a每增加一对逆序，a，b的向量积就一定会变小，两者呈反比。

所以当a是相对于b的全逆序时，a，b的向量积最小。相反的，当a是相对于b的全顺序时，a，b的向量积最大。

  1. 下面证明a_{i}\cdot b_{i}+a_{j}\cdot b_{j}>a_{i}\cdot b_{j}+a_{j}\cdot b_{i}：
    因为b_{i}<b_{j}，a_{i}<a_{j}，所以b_{i}-b_{j}<0，a_{i}-a_{j}<0
    即(a_{i}-a_{j})\cdot(b_{i}-b_{j})>0
    对上式展开移项即可得到要证明的结论。

相关文章

  • 最小向量积

    调整数组元素的位置使得两数组向量积最小 问题描述： 有长度为n的数组a，b，问如何调整数组内元素的位置使得 最小...

  • OpenGL - 获取法向量

    计算一个法向量 计算矢量积向量 用这个矢量积向量的长度/矢量积的每个分量 获取两个点形成的的向量 返回一个单位法向量

  • 线性代数-向量

    什么是向量所谓向量，就是「既有大小，又有方向的量」。向量有加、减、数乘、数量积、向量积运算，但唯独没有除法（这里指...

  • Chapter3——向量

    1. 向量的数量积（内积） 定义： 性质： 坐标表达式： 2. 向量的向量积（外积） 定义： 性质： 坐标表达式：...

  • 向量外积的高中数学运用

    向量积，数学中又称外积、叉积，物理中称矢积、叉乘，是一种在向量空间中向量的二元运算。与点积不同，它的运算结果是一个...

  • 【MATLAB】向量运算

    数量积（点乘） 向量积（叉乘） 夹角 模

  • 线性代数的本质（笔记3）（完）

    1. 叉积与点积 点乘，也叫数量积。结果是一个向量在另一个向量方向上投影的长度，是一个标量。 叉乘，也叫向量积。结...

  • 【数学】统计基础

    点积（dot product/scalar product）：即两个向量相乘的数量积，运算结果是标量。 例：向量 ...

  • 向量代数和空间解析几何

    个人重点1.数量积，向量积，混合积2.平面方程，直线方程，平面与直线的位置关系（关键：♦♦平面的法线向量，直线的方...

  • 数量级与向量积——笔记

    数量级与向量积 一、两向量的数量级 1、定义： 为与的夹角 2、数量积的性质： 等价于 3、数量积的运...

网友评论

      本文标题：最小向量积

      本文链接：https://www.haomeiwen.com/subject/girwxqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|最小向量积|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！