l********s
发帖数: 358 | 1 在坐标系里有若干点，找到一条x-axis的平行线，使得所有点到这条直线的距离和最短
。我想到的方法如下：这条直线必然会经过其中一点；对于每个点上的x-axis平行线，
计算所有点到线的距离和；找出距离和的最小值。算法的复杂度为O(n^2)
不知道有没有更好的办法来减少复杂度？ |
i******t
发帖数: 370 | 2 The y coordinate of the line is simply the median of the y coordinates of
all points. Finding median is O(n).
【在 l********s 的大作中提到】
: 在坐标系里有若干点，找到一条x-axis的平行线，使得所有点到这条直线的距离和最短
: 。我想到的方法如下：这条直线必然会经过其中一点；对于每个点上的x-axis平行线，
: 计算所有点到线的距离和；找出距离和的最小值。算法的复杂度为O(n^2)
: 不知道有没有更好的办法来减少复杂度？
|
k****u
发帖数: 133 | 3 先排个序，然后直接找中间那个点？感觉可以，不太确定，也许可以从数学上证明一下
。 |
p*******r
发帖数: 475 | 4 直接求y坐标的算术平均值
【在 l********s 的大作中提到】
: 在坐标系里有若干点，找到一条x-axis的平行线，使得所有点到这条直线的距离和最短
: 。我想到的方法如下：这条直线必然会经过其中一点；对于每个点上的x-axis平行线，
: 计算所有点到线的距离和；找出距离和的最小值。算法的复杂度为O(n^2)
: 不知道有没有更好的办法来减少复杂度？
|
l*y
发帖数: 21010 | 5 你这个minimize的是squared distance，应该是找median
http://en.wikipedia.org/wiki/Fermat-Weber_problem
【在 p*******r 的大作中提到】
: 直接求y坐标的算术平均值
|
l*y
发帖数: 21010 | 6 找median是O(n)
叫median of medians algorithm
【在 k****u 的大作中提到】
: 先排个序，然后直接找中间那个点？感觉可以，不太确定，也许可以从数学上证明一下
: 。
|
l********s
发帖数: 358 | 7 多谢！2个包子请笑纳
【在 l*y 的大作中提到】
: 你这个minimize的是squared distance，应该是找median
: http://en.wikipedia.org/wiki/Fermat-Weber_problem
|
l********s
发帖数: 358 | 8 Finding median needs the sorting at the beginning. So I think the complexity
should be O(NlnN)
http://easycalculation.com/statistics/learn-median.php
【在 i******t 的大作中提到】
: The y coordinate of the line is simply the median of the y coordinates of
: all points. Finding median is O(n).
|
l*y
发帖数: 21010 | 9 不需要。。
complexity
【在 l********s 的大作中提到】
: Finding median needs the sorting at the beginning. So I think the complexity
: should be O(NlnN)
: http://easycalculation.com/statistics/learn-median.php
|
l*y
发帖数: 21010 | 10 一般情况下需要，特殊情况下不需要（比如对称的） |
|
|
b********h
发帖数: 119 | 11 Sorting is not needed by using Selection algorithm.
http://en.wikipedia.org/wiki/Selection_algorithm
complexity
【在 l********s 的大作中提到】
: Finding median needs the sorting at the beginning. So I think the complexity
: should be O(NlnN)
: http://easycalculation.com/statistics/learn-median.php
|
i******t
发帖数: 370 | 12 I want bao zi too...
【在 l********s 的大作中提到】
: 多谢！2个包子请笑纳
|
t****t
发帖数: 6806 | 13 前面都已经有人给了link了. 都不知道你在想什么.
当然如果是偶数个点, 那中间两点之间任何一个y值都等价, 但是经过其中一个的仍然
是(等价)最优的.
(下次发言前好好想想) |
l********s
发帖数: 358 | 14 1个包子请笑纳! 俺很穷，2年才攒了20个包子
【在 i******t 的大作中提到】
: I want bao zi too...
|
i******t
发帖数: 370 | 15 thanks!
【在 l********s 的大作中提到】
: 1个包子请笑纳! 俺很穷，2年才攒了20个包子
|
k**l
发帖数: 9 | 16 路过，不知道这个问题难点在哪？只要把问题列出来求个导就知道最小值是纵坐标的平
均值。 |
l*y
发帖数: 21010 | 17 。。。。。。
【在 k**l 的大作中提到】
: 路过，不知道这个问题难点在哪？只要把问题列出来求个导就知道最小值是纵坐标的平
: 均值。
|
i******t
发帖数: 370 | 18 he missed the point that the distance is L1 instead of L2...
【在 l*y 的大作中提到】
: 。。。。。。
|
k**l
发帖数: 9 | 19 呵呵，正是，幸好回来看了一眼。一维的那就是median无疑了。
【在 i******t 的大作中提到】
: he missed the point that the distance is L1 instead of L2...
|
t****t
发帖数: 6806 | 20 不懂不要紧, 不懂还要装懂就是你的不是了
明明不懂, 别人还给了link, 你还不看, 那简直是罪大恶极... |
|
|
l********s
发帖数: 358 | 21 No fights, gentlemen. Happy Chinese New Year!!
Check the bus fight at Oakland CA:
http://www.youtube.com/watch?v=lQJFv9SMSMQ |
t****t
发帖数: 6806 | |
S*********g
发帖数: 5298 | |
o*l
发帖数: 29 | 24 一般来说，直线两边的点的数目应该一样多。否则直线上移或下移会得到矛盾。
【在 l********s 的大作中提到】
: 在坐标系里有若干点，找到一条x-axis的平行线，使得所有点到这条直线的距离和最短
: 。我想到的方法如下：这条直线必然会经过其中一点；对于每个点上的x-axis平行线，
: 计算所有点到线的距离和；找出距离和的最小值。算法的复杂度为O(n^2)
: 不知道有没有更好的办法来减少复杂度？
|
c*******d
发帖数: 255 | 25 这不就是这些点的y坐标的median吗？
把这些点的y坐标排序，可以在O(nlog(n))内完成
然后取中点就行了！
【在 l********s 的大作中提到】
: 在坐标系里有若干点，找到一条x-axis的平行线，使得所有点到这条直线的距离和最短
: 。我想到的方法如下：这条直线必然会经过其中一点；对于每个点上的x-axis平行线，
: 计算所有点到线的距离和；找出距离和的最小值。算法的复杂度为O(n^2)
: 不知道有没有更好的办法来减少复杂度？
|
