请教一个算法
假如A={a1,a2,…,an}
定义f(A,x) = min{ (x-ai)^2 | ai属于A }
假如X={x1,x2,…,xm}是已知样本,要求出一个元素个数已知的A使得
f(A,x1)+f(A,x2)+…+f(A,xm)
最小
请教算法
[解决办法]
ls:
向量A的维数不一定等于向量X的维数。
[解决办法]
不失一般性，设x1<=x2<=x3……<=xm，a1<=a2<=a3……<=an。
当n>=m时，只要，ai=xi（i为1到m）和ai=x1（m<i<n）即可。所以假设m>n。
下面以m=9、n=4为例：
我们把m表示为n个正整数的和叫做m的n剖分。在剖分中数字可以重复，且次序有效，即不同的次序是不同的剖分。
对于某一个剖分，例如对于9=4+2+1+2，我们称a1=mean(x1,x2,x3,x4)、a2=mean(x5,x6)、a3=mean(x7)、a4=mean(x8,x9)为一组预备解（其中mean表示算数平均值）。对于这组解，如果满足x4<=mean(a1,a2)<=x5、x6<=mean(a2,a3)<=x7、x7<=mean(a3,a4)<=x8（我们简称这个条件为边界条件吧），那么，这组解在局部使函数f呈现极小值，我们称之为一组局部解。求出所有的局部解，其中最小的那个就是问题的解了。
按照上面的思路，可以采取下面的步骤：
1、排序x；
2、穷举所有的m的n剖分；
3、对于每一组剖分，求出其预备解，验证所谓边界条件，判断是否为局部解；
4、求出所有局部解对应的函数f的值，其中的最小值为问题的解。
[解决办法]
当n>=m的时候，取X的元素就行了；
当n<m的时候，必定有某个A中的元素（假设为ak）对应有多个X中的元素（假设为Xi,Xj,xi<xj）使得:
f(A,xi)=(xi-ak)^2; f(A,xj)=(xj-ak)^2;
假设有xi<xi'<xj;容易证明f(A,xi')=(xi'-ak)^2;
因为如果存在ak'<>ak,f(A,xi')=(xi'-ak')^2,
如果ak'<ak,那么(xi-ak)^2>(xi-ak')^2,矛盾;
如果ak'>ak,那么(xj-ak)^2>(xj-ak')^2,矛盾;
所以题目相当于对排序后的X分成m组，然后对每组（xi...xj）求一个数，使得sum((xi'-a)^2),i<i'<j最小；
此过程可以用动态规划法来求解；
现在的难点就在于每组（xi...xj）求一个数的解法（相当与X==该小组，A的元素个数为1的原问题）；
由方程式min((xi-a)^2+..+(xi'-a)^2+..+(xj-a)^2)
是否有lz说的“如果n等于1那么很容易知道a1等于X的平均值”就不太清楚了；
[解决办法]
5楼效率低下的原因是因为第2步要求穷举所以的剖分。
其实，如果m较大，n较小，那么是不必要的。
最佳解对应的剖分总是使每一个a所对应的区域长度（而非x的个数）大致相等。
因此，第2步中，可以按照这个标准来将x分段，然后在一定范围内调节，就可以了。
最后，调节的范围要看具体的x的分布。
比如说有4个x，按照如下分布：
-x1-x2-----------------------x3--x4-->
而要有剖分为3个段（有3个a），那么a1->{x1},a2->{x2},a3->{x3,x4}和a1->{x1,x2},a2->{x3},a3->{x4}这两组分组方式都对应局部的极值，所以就都要算出比较了。
[解决办法]
可以在o(n^2)求出全部的局部解；
用数组dp1[m][m]来保存全部的局部解；
如果dp1[i+i][j]已知，那么dp1[i][j]=(dp1[i+i][j]*(j-i)+x[i])/(j-i+1)
对所有的局部解搜索最优解：
用数组dp2[8][m][m]来保存中间结果，dp2[8][1][m]是最终的解,那么可以在o(n^3)求出；
dp2[i][j][k]=min(dp1[j][j']+dp2[i-1][j'+1][k]),j<j'<k
还没找到小于N^3的搜索最优解的方法；
不过o(n^3)对10^5的数量级应该也可行的吧
[解决办法]
当n<m时：对X元素进行排序后为：X1，X2，X3，....，Xm
1）先证明I个元素的集合，使得F=(x-a1)^2+（x-a2)^2+...+(x-aI)^2最小值的数X是I所有元素的平均值
F=x^2-2xa1+a1^2+....
=I*x^2-2x(a1+a2+a3...+aI)+a1^2+a2^2+...aI^2
可以得出F最小值的解，x=(a1+a2+a3...+aI)/I;
2)将集合X从小到大划分成s组集合，其中1<=s<=n;这时可以看出跟矩阵连乘的问题一样，可以用动态规划法来解；
3）其实可以证明s==n时得到的是最优的（证明略），所以当用动态规划求解时只要计算到（m-n）个元素，不用计算到n;
[解决办法]
搜索最优解用dp2[n][m]来保存最优解,dp2[i][j]表示从xj-xm分成i组的最优解，那么最后最优解就是dp2[n][1]；
dp2[i][j]=min(dp1[j][j']+dp2[i-1][j'+1]) j<j'<m
这样复杂度就降低成了o(m*n);
[解决办法]
to:IT_worker
复杂度不是这么计算的：
动态规划的推导公式是：
dp2[i][j]=min(dp1[j][j ']+dp2[i-1][j '+1]) j <j ' <m
计算dp2[n][m]的单个元素的复杂度为O(m);
元素总个数为n*m个；
所以总的复杂度为O(n*m^2);
又因为"n的值大约是8"，可以忽略掉n；
[解决办法]
如果不是必须求最优值，可以考虑使用模式识别中的聚类分析。将m个数据先聚类成n类。
然后每类求个平均值，基本上就差不多了。
[解决办法]
参考这个:
http://topic.csdn.net/u/20071016/16/6734119d-27dd-4efd-91ea-a9290d6545c0.html
终于搞清楚了C#二进制的一些关键操作了,解决了微软面试题，求数组中两两之差绝对值最小的值O(N)最少内存限制的问题!
研究了好几天,写出来一个看起来象O(n)的算法,O(nlog)就不用写了.
思路是桶排序O(N)复杂度,为了节省空间,采用了Byte[]数组,1个byte代表8个数字的有无.
回头整理公布一下C#二进制运算的一些重要操作.
- C# code
using System;namespace MinABS{ class Program { static void Main(string[] args) { int n = 100; int[] a = new int[n]; Random rand = new Random(); int min = int.MaxValue; int max = int.MinValue; Console.WriteLine("产生了" + n + "个数据的实验数组,"); Console.WriteLine("本程序适用于int.MinValue到int.MaxValue范围，请自行修改输入的量和范围"); for (int i = 0; i < n; i++) { //赋值并且取到最大最小值 //a[i] = rand.Next(int.MinValue, int.MaxValue); a[i] = rand.Next(-100, 100); if (a[i] < min) { min = a[i]; } if (a[i] > max) { max = a[i]; } Console.Write(a[i] + " "); } Console.WriteLine(); Console.WriteLine("在O(n)内得到最大最小分别是："); Console.WriteLine(max + "和" + min); long offset = (long)max + Math.Abs((long)min); //规划数组的长度。每个byte有8位长 int len = (int)(offset >> 3) +1 ; Byte[] B = new Byte[len]; int kkkk = 0; bool IsSame = false;//是否有重合点标记 //O(n)的时间内分配到了Byte[]中。 for (int i = 0; i < n; i++) { offset = (long)a[i] - (long)min; int index = (int)(offset >> 3); int temp = B[index]; //把末k位变成1 //把右数第k位变成1 例如：(00101001->00101101,k=3) x | (1 << (k-1)) int tempOffSet = (1 << ( (int)(offset & 7) ) ); //判断重合 if (!IsSame) { kkkk = temp & tempOffSet; if ((temp & tempOffSet) >= 1) { IsSame = true; //如果0算最小距离就在这里退出吧。本代码判断重合，但没把0作为结果。 } } int bbb = B[index]; B[index] |= (Byte)(tempOffSet); int aaa = B[index]; } //最小距离初始为最大。 Console.WriteLine("在O(n)的时间内分配到了Byte[]中，正在计算最小距离，请稍候。。。。。"); long minABS = long.MaxValue; long lastIndex = -1; //在常数范围内循环，复杂度不增加。最坏的情况是32*int.MaxValue次。 for (int i = 0; i < B.Length; i++) { //if (B[i] == 0) { continue; } //在常数范围内循环，复杂度不增加。 for (int k = 0; k < 8; k++) { if (((B[i] >> k) & 1) == 1) { if (lastIndex >= 0) { long temp = ((long)i << 3) + k - lastIndex; if (temp < minABS) { minABS = temp; Console.WriteLine("目前得到了最小距离：" + minABS); } } lastIndex = (i << 3) + k; } } } if (IsSame) { Console.WriteLine("有重合点"); } else { Console.WriteLine("无重合点"); } Console.WriteLine("不考虑重合最小距离是：" + minABS); Console.WriteLine("总复杂度是：O(n)"); Console.ReadLine(); } }}
[解决办法]
问题可以理解为：
m,i
min∑(|xi|-|aj|)
i,j
"最小线段合最小"的问题。
首先，发现题目存在问题：
f(A,x1)+f(A,x2)+…+f(A,xm) 本身就是常数，不存在最小合的问题。
如果只为了求出这个数字
第一步，求出最小线段：
aj和xi的关系是“最小线段”的关系：
点到集合最小距离，分2种情况
1，xi点在集合A={a1,a2,…,an}内，要遍历集合取到最小值,
复杂度是:
对A集合桶排序是的时间 + 二分查找m次xi的时间
=O(n) + O(mlogn)
=O(n+mlogn)
如果A集合分散度过高，采用AVL二叉树排序,总复杂度是O(nlogn)+O(mlogn)=O((n+m)logn)
2，xi点全在集合A={a1,a2,…,an}外，取集合最大/小 ，相减就可以了。总复杂度是O(m)。
故第一步复杂度应该是O(m)到O(n+mlogn)或者O((n+m)logn)，取决于两个集合范围和离散程度。
第二步，求最小合后：
最小线段求出后，问题就变成了
m m
min∑(|xi|-Ki)=min∑|yi|
i i
因为其中Ki为常量集合，所以在O(m)内演变成Y ={y1,y2,…,ym} 同样是已知样本。
求其合就可以了。
两步总的复杂度是
O(n+m+mlogn)
或者O(m+(n+m)logn)
根据离散情况选择最小的做法。