g*****u
发帖数: 298 | 1 Local minimum of a matrix. Given an N-by-N array a of N^2 distinct integers,
design an O(N) algorithm to find a local minimum: an pair of indices i and
j such that a[i][j] < a[i+1][j], a[i][j] < a[i][j+1], a[i][j] < a[i-1][j],
and a[i][j] < a[i][j-1]. |
g*****y
发帖数: 7271 | 2 boundary pixel 也可以是 local minimum吧？基本上，沿着x，y一步一步往gradient最大的方向走，最多2N步就找到了吧。
integers,
and
【在 g*****u 的大作中提到】
: Local minimum of a matrix. Given an N-by-N array a of N^2 distinct integers,
: design an O(N) algorithm to find a local minimum: an pair of indices i and
: j such that a[i][j] < a[i+1][j], a[i][j] < a[i][j+1], a[i][j] < a[i-1][j],
: and a[i][j] < a[i][j-1].
|
p****n
发帖数: 148 | 3
gradient最大的方向走，最多2N步就找到了吧。
为什么“最多2N步就找到了”
例如，如何处理螺旋下降？
【在 g*****y 的大作中提到】
: boundary pixel 也可以是 local minimum吧？基本上，沿着x，y一步一步往gradient最大的方向走，最多2N步就找到了吧。
:
: integers,
: and
|
O*******d
发帖数: 20343 | 4 "gradient最大的方向走"
【在 p****n 的大作中提到】
:
: gradient最大的方向走，最多2N步就找到了吧。
: 为什么“最多2N步就找到了”
: 例如，如何处理螺旋下降？
|
p****n
发帖数: 148 | 5 请在下面7X7的矩阵上演示一下"gradient最大的方向走" “最多2N步就找到”
假定从左上角1048开始
1048 1047 1046 1045 1044 1043 1042
5041 5040 5039 5038 5037 5036 1041
1026 1025 1024 1023 1022 5029 1040
1027 5026 5025 5024 1021 5022 1039
1028 5019 1018 1019 1020 5015 1038
1029 5012 5011 5010 5009 5008 1037
1030 1031 1032 1033 1034 1035 1036
【在 O*******d 的大作中提到】
: "gradient最大的方向走"
|
p***o
发帖数: 1252 | 6 最差O(N)估计搞不定，平均O(N)应该没问题。
http://www.jstor.org/pss/2243696
【在 p****n 的大作中提到】
: 请在下面7X7的矩阵上演示一下"gradient最大的方向走" “最多2N步就找到”
: 假定从左上角1048开始
: 1048 1047 1046 1045 1044 1043 1042
: 5041 5040 5039 5038 5037 5036 1041
: 1026 1025 1024 1023 1022 5029 1040
: 1027 5026 5025 5024 1021 5022 1039
: 1028 5019 1018 1019 1020 5015 1038
: 1029 5012 5011 5010 5009 5008 1037
: 1030 1031 1032 1033 1034 1035 1036
|
X****r
发帖数: 3557 | 7 先看一维的情况，在a[1..n]里找局部最小。还记得小学数学学过华罗庚的优选法，
正合适用在这里，设p={\sqrt{5}-1}/2=0.618，那么每一步对当前的一段区间，
在p和1-p处取两个值（除了第一步以外这两个值中有一个已经在上一步里被取过了）
去除两个值中较大者所对应的边上的那段子区间，剩下长度为原来p倍的子区间。
这样只要O(log(n))时间就能找到局部最小。
再扩展到二维，可以在两个方向上轮流做，每一步的X方向，在p和1-p处取两列，
找到两列里数值最小的元素，保留它所在的p倍宽的子矩阵，Y方向同理，这样第i步
所花时间是O(n/p^i)，最后加起来是O(n)。
integers,
and
1][j],
【在 g*****u 的大作中提到】
: Local minimum of a matrix. Given an N-by-N array a of N^2 distinct integers,
: design an O(N) algorithm to find a local minimum: an pair of indices i and
: j such that a[i][j] < a[i+1][j], a[i][j] < a[i][j+1], a[i][j] < a[i-1][j],
: and a[i][j] < a[i][j-1].
|
X****r
发帖数: 3557 | 8 又想了想其实优选法用p=0.618是为了减少试验次数，这里数组或者矩阵存取代价
不大，所以稍微改一改算法每一步取中间的两个数（或列或行）可以每次留下一半
区间。当然这些都是常数系数，不影响时间复杂度。
【在 X****r 的大作中提到】
: 先看一维的情况，在a[1..n]里找局部最小。还记得小学数学学过华罗庚的优选法，
: 正合适用在这里，设p={\sqrt{5}-1}/2=0.618，那么每一步对当前的一段区间，
: 在p和1-p处取两个值（除了第一步以外这两个值中有一个已经在上一步里被取过了）
: 去除两个值中较大者所对应的边上的那段子区间，剩下长度为原来p倍的子区间。
: 这样只要O(log(n))时间就能找到局部最小。
: 再扩展到二维，可以在两个方向上轮流做，每一步的X方向，在p和1-p处取两列，
: 找到两列里数值最小的元素，保留它所在的p倍宽的子矩阵，Y方向同理，这样第i步
: 所花时间是O(n/p^i)，最后加起来是O(n)。
:
: integers,
|
h*****0
发帖数: 4889 | 9 保证O(N)是显然不可能的。最坏情况肯定是O(N^2)的。
integers,
and
【在 g*****u 的大作中提到】
: Local minimum of a matrix. Given an N-by-N array a of N^2 distinct integers,
: design an O(N) algorithm to find a local minimum: an pair of indices i and
: j such that a[i][j] < a[i+1][j], a[i][j] < a[i][j+1], a[i][j] < a[i-1][j],
: and a[i][j] < a[i][j-1].
|
X****r
发帖数: 3557 | 10 如果任两个元素不相同的话就可以。
【在 h*****0 的大作中提到】
: 保证O(N)是显然不可能的。最坏情况肯定是O(N^2)的。
:
: integers,
: and
|
|
|
p***o
发帖数: 1252 | 11 a[1..n]没排序你怎么用二分查找阿 ...
【在 X****r 的大作中提到】
: 先看一维的情况，在a[1..n]里找局部最小。还记得小学数学学过华罗庚的优选法，
: 正合适用在这里，设p={\sqrt{5}-1}/2=0.618，那么每一步对当前的一段区间，
: 在p和1-p处取两个值（除了第一步以外这两个值中有一个已经在上一步里被取过了）
: 去除两个值中较大者所对应的边上的那段子区间，剩下长度为原来p倍的子区间。
: 这样只要O(log(n))时间就能找到局部最小。
: 再扩展到二维，可以在两个方向上轮流做，每一步的X方向，在p和1-p处取两列，
: 找到两列里数值最小的元素，保留它所在的p倍宽的子矩阵，Y方向同理，这样第i步
: 所花时间是O(n/p^i)，最后加起来是O(n)。
:
: integers,
|
X****r
发帖数: 3557 | 12 不需要排序啊，只是要局部最小，又不是要全局最小。
对于一维的情况，很容易证明每一步剩下的区间内必然含有一个局部最小值。
【在 p***o 的大作中提到】
: a[1..n]没排序你怎么用二分查找阿 ...
|
p***o
发帖数: 1252 | 13 前面person的例子你的算法怎么解?
【在 X****r 的大作中提到】
: 不需要排序啊，只是要局部最小，又不是要全局最小。
: 对于一维的情况，很容易证明每一步剩下的区间内必然含有一个局部最小值。
|
X****r
发帖数: 3557 | 14 你是说已经排好序的极端情况吗？那也一样啊，比如降序排列的，按这个算法
每一步就会去掉左边的一截，最后只剩下最右边几个元素的区间了，当区间里
的元素数目小于某一个阈值的时候就可以直接找最小元素，于是就找到最右边
的元素，的确为局部最小。
【在 p***o 的大作中提到】
: 前面person的例子你的算法怎么解?
|
X****r
发帖数: 3557 | 15 先取第三、五列，得最小值为1018，所以将第五、六、七列舍去；
再取第三、五行，得最小值为1018，所以将第一、二、三行舍去；
得：
1027 5026 5025 5024
1028 5019 1018 1019
1029 5012 5011 5010
1030 1031 1032 1033
以下用新坐标：
取第二、三列，得最小值为1018，所以将第一、二列舍去；
取第二、三行，得最小值为1018，所以将第三、四行舍去；
得：
5025 5024
1018 1019
只剩四个元素，直接取最小值1018即是。
【在 p***o 的大作中提到】
: 前面person的例子你的算法怎么解?
|
X****r
发帖数: 3557 | 16 这个根本就不是一会事嘛，那篇文章说的是unit d-cube上的vertex，
对于二维来说就是2x2的矩阵中找局部最优至少要两步，和我们讨论的这道题
没什么关系。
【在 p***o 的大作中提到】
: 最差O(N)估计搞不定，平均O(N)应该没问题。
: http://www.jstor.org/pss/2243696
|
h*****0
发帖数: 4889 | 17 没有局部最小的情况也可以在O（N）时间内验证出来？
【在 X****r 的大作中提到】
: 如果任两个元素不相同的话就可以。
|
X****r
发帖数: 3557 | 18 任两个元素不相同必然有局部最小。
【在 h*****0 的大作中提到】
: 没有局部最小的情况也可以在O（N）时间内验证出来？
|
p***o
发帖数: 1252 | 19 有道理，d-cube比这个难。
【在 X****r 的大作中提到】
: 这个根本就不是一会事嘛，那篇文章说的是unit d-cube上的vertex，
: 对于二维来说就是2x2的矩阵中找局部最优至少要两步，和我们讨论的这道题
: 没什么关系。
|
h*****0
发帖数: 4889 | 20 中间大四周小的情况呢？
【在 X****r 的大作中提到】
: 任两个元素不相同必然有局部最小。
|
|
|
X****r
发帖数: 3557 | 21 局部最小当然可以在边界上。
这个证明很容易啊：既然所有元素互不相同，那就有一个唯一的全局最小，
它自然也就是局部最小。
【在 h*****0 的大作中提到】
: 中间大四周小的情况呢？
|
d*****l
发帖数: 8441 | 22 平均运算量还是绝对运算量啊？
如果算平均的话可是跟数据的统计分布有关系的啊。 |
O*******d
发帖数: 20343 | 23 优选法的数据不需要排续。 但好像是在连续值上取点，可以迅速找到局部峰值。 一维
，多维都可以作。
【在 p***o 的大作中提到】
: a[1..n]没排序你怎么用二分查找阿 ...
|
g*****y
发帖数: 7271 | 24
佩服，佩服，本来沿着这个思路也想了一下，结果觉得会是O(nlogn)，就没再深入了。
第i步
【在 X****r 的大作中提到】
: 先看一维的情况，在a[1..n]里找局部最小。还记得小学数学学过华罗庚的优选法，
: 正合适用在这里，设p={\sqrt{5}-1}/2=0.618，那么每一步对当前的一段区间，
: 在p和1-p处取两个值（除了第一步以外这两个值中有一个已经在上一步里被取过了）
: 去除两个值中较大者所对应的边上的那段子区间，剩下长度为原来p倍的子区间。
: 这样只要O(log(n))时间就能找到局部最小。
: 再扩展到二维，可以在两个方向上轮流做，每一步的X方向，在p和1-p处取两列，
: 找到两列里数值最小的元素，保留它所在的p倍宽的子矩阵，Y方向同理，这样第i步
: 所花时间是O(n/p^i)，最后加起来是O(n)。
:
: integers,
|
