E*******F
发帖数: 2165 | 1 在一个sorted array里查找“第一次”出现的0
如果用基于比较的方法，复杂度是多少？
我看网上有些人说是O(logn)，可我觉得不对
O(logn)只能找到想查找的元素，
但要确定第一个，要么得往回一个个搜这就是O(n)了显然不好
要么得在前面的区间里再用binary search,
如果碰到极端的情况要用很多次直到只有一个元素
所以怎么也不可能是O(logn)啊 |
G*****7
发帖数: 1759 | 2 why not. you can do o(log(n)) with a variant of binary search that
alternatives between looking for an element smaller than your query and
looking an element equal to your query. in doing so you will bracket the
first occurrence of your query.
check out, for instance, std::equal_range in . equal_range finds
the first and last occurrence of the query in 2*o(log(n)).
【在 E*******F 的大作中提到】
: 在一个sorted array里查找“第一次”出现的0
: 如果用基于比较的方法，复杂度是多少？
: 我看网上有些人说是O(logn)，可我觉得不对
: O(logn)只能找到想查找的元素，
: 但要确定第一个，要么得往回一个个搜这就是O(n)了显然不好
: 要么得在前面的区间里再用binary search,
: 如果碰到极端的情况要用很多次直到只有一个元素
: 所以怎么也不可能是O(logn)啊
|
E*******F
发帖数: 2165 | 3 那你怎么保证较小的元素是最后一个呢。
再说也不知道都有哪些
要找出那个界限constant time是不行的啊
finds
【在 G*****7 的大作中提到】
: why not. you can do o(log(n)) with a variant of binary search that
: alternatives between looking for an element smaller than your query and
: looking an element equal to your query. in doing so you will bracket the
: first occurrence of your query.
: check out, for instance, std::equal_range in . equal_range finds
: the first and last occurrence of the query in 2*o(log(n)).
|
t****t
发帖数: 6806 | 4 人都跟你说了看一下std::equal_range.
【在 E*******F 的大作中提到】
: 那你怎么保证较小的元素是最后一个呢。
: 再说也不知道都有哪些
: 要找出那个界限constant time是不行的啊
:
: finds
|
l*********s
发帖数: 5409 | 5 you locate the bounds by finding the nearest smaller/larger instead.
【在 E*******F 的大作中提到】
: 那你怎么保证较小的元素是最后一个呢。
: 再说也不知道都有哪些
: 要找出那个界限constant time是不行的啊
:
: finds
|
E*******F
发帖数: 2165 | 6 嗯，如果元素都是整数，这个办法是可以的
如果是任意实数，似乎无法确定nearest smaller one
不过实际问题中也用不到了
【在 l*********s 的大作中提到】
: you locate the bounds by finding the nearest smaller/larger instead.
|
l*********s
发帖数: 5409 | 7 glock17 and thrust already told you the answer, equal_range does exactly
this.
【在 E*******F 的大作中提到】
: 嗯，如果元素都是整数，这个办法是可以的
: 如果是任意实数，似乎无法确定nearest smaller one
: 不过实际问题中也用不到了
|
t****t
发帖数: 6806 | 8 equal_range没说只对整数, 只要能比较就行了.
【在 E*******F 的大作中提到】
: 嗯，如果元素都是整数，这个办法是可以的
: 如果是任意实数，似乎无法确定nearest smaller one
: 不过实际问题中也用不到了
|
c*****m
发帖数: 1160 | 9
please define "第一个".
难道你找到的第一个不是人家要找的第一个么？
【在 E*******F 的大作中提到】
: 在一个sorted array里查找“第一次”出现的0
: 如果用基于比较的方法，复杂度是多少？
: 我看网上有些人说是O(logn)，可我觉得不对
: O(logn)只能找到想查找的元素，
: 但要确定第一个，要么得往回一个个搜这就是O(n)了显然不好
: 要么得在前面的区间里再用binary search,
: 如果碰到极端的情况要用很多次直到只有一个元素
: 所以怎么也不可能是O(logn)啊
|
E*******F
发帖数: 2165 | 10 没什么特别的，就是地址最小的那个
一个极端的情况，如果输入数组元素全部都是0
如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
我看了一下网上一些人的折半查找code和讨论，全部都是错的
他们都假设只需要调用constant次的折半查找过程
其实根本不是
不过对于average case是没错
【在 c*****m 的大作中提到】
:
: please define "第一个".
: 难道你找到的第一个不是人家要找的第一个么？
|
|
|
c*****m
发帖数: 1160 | 11
你理解了这些O(logn)的算法的前提是这个数列是sorted的吧？
【在 E*******F 的大作中提到】
: 没什么特别的，就是地址最小的那个
: 一个极端的情况，如果输入数组元素全部都是0
: 如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
: 我看了一下网上一些人的折半查找code和讨论，全部都是错的
: 他们都假设只需要调用constant次的折半查找过程
: 其实根本不是
: 不过对于average case是没错
|
t****t
发帖数: 6806 | 12 为什么全是0的情况下找不到第一个0?
找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
哪里, 也不明白为什么你不愿意看一下现成的STL code.
最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你.
【在 E*******F 的大作中提到】
: 没什么特别的，就是地址最小的那个
: 一个极端的情况，如果输入数组元素全部都是0
: 如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
: 我看了一下网上一些人的折半查找code和讨论，全部都是错的
: 他们都假设只需要调用constant次的折半查找过程
: 其实根本不是
: 不过对于average case是没错
|
E6
发帖数: 105 | 13 没有看懂,
如果都是0
应该还是LG(N)啊
【在 E*******F 的大作中提到】
: 没什么特别的，就是地址最小的那个
: 一个极端的情况，如果输入数组元素全部都是0
: 如果用折半查找或类似方法，O(logn)时间内根本无法找到第一个0
: 我看了一下网上一些人的折半查找code和讨论，全部都是错的
: 他们都假设只需要调用constant次的折半查找过程
: 其实根本不是
: 不过对于average case是没错
|
b***i
发帖数: 3043 | 14 他是真逗
【在 E6 的大作中提到】
: 没有看懂,
: 如果都是0
: 应该还是LG(N)啊
|
E*******F
发帖数: 2165 | 15 同学，折半查找的过程都logn次了，总体复杂度还是O(logn)吗？
这不是common sense？
【在 t****t 的大作中提到】
: 为什么全是0的情况下找不到第一个0?
: 找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
: 就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
: 到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
: std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
: 哪里, 也不明白为什么你不愿意看一下现成的STL code.
: 最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你.
|
E*******F
发帖数: 2165 | 16 你仔细想想
log(n)+log(n/2)+log(n/4)....+log(1)
这个级数求和会是logn吗
总共有logn项呢，不是常数个项
当然这只是worse case
还有，如果都是整数也好办，直接查找-0.5就行了
【在 E6 的大作中提到】
: 没有看懂,
: 如果都是0
: 应该还是LG(N)啊
|
E*******F
发帖数: 2165 | 17 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
当然，遇到这种特殊情况，折半查找不是最优化的
但我的意思是如果用这样的方法，每次跟一个mid比，
要比logn次才能比完
虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
应该是O(logn*logn)
【在 c*****m 的大作中提到】
:
: 你理解了这些O(logn)的算法的前提是这个数列是sorted的吧？
|
p***o
发帖数: 1252 | 18 Can you read C++? Here is the O(log n) implementation that finds the first
_Val if there is any _Val in the sorted sequence _First to _Last.
template inline
_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Diff *)
{ // find first element not before _Val, using operator<
_Diff _Count = 0;
_Distance(_First, _Last, _Count);
for (; 0 < _Count; )
{ // divide and conquer, find half that contains answer
_Diff _Count2 = _Count / 2;
_FwdIt _Mid = _First;
_STD advance(_Mid, _Count2);
if (*_Mid < _Val)
{ // try top half
_First = ++_Mid;
_Count -= _Count2 + 1;
}
else
_Count = _Count2;
}
return (_First);
}
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
|
p***o
发帖数: 1252 | 19 count每次至少减一半，你说要多少次？
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
|
E6
发帖数: 105 | 20 白痴?
【在 E*******F 的大作中提到】
: 你仔细想想
: log(n)+log(n/2)+log(n/4)....+log(1)
: 这个级数求和会是logn吗
: 总共有logn项呢，不是常数个项
: 当然这只是worse case
: 还有，如果都是整数也好办，直接查找-0.5就行了
|
|
|
t****t
发帖数: 6806 | 21 一共两次折半查找, 为什么复杂度不是log n?
【在 E*******F 的大作中提到】
: 同学，折半查找的过程都logn次了，总体复杂度还是O(logn)吗？
: 这不是common sense？
|
t****t
发帖数: 6806 | 22 哪来的求和啊.
【在 E*******F 的大作中提到】
: 你仔细想想
: log(n)+log(n/2)+log(n/4)....+log(1)
: 这个级数求和会是logn吗
: 总共有logn项呢，不是常数个项
: 当然这只是worse case
: 还有，如果都是整数也好办，直接查找-0.5就行了
|
t****t
发帖数: 6806 | 23 你除了查找一个确定的数, 不会查别的了吗? 有没有这么难沟通啊...
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
|
h*******s
发帖数: 8454 | 24 logn+logn --> logn
没错啊
【在 E*******F 的大作中提到】
: 同学，折半查找的过程都logn次了，总体复杂度还是O(logn)吗？
: 这不是common sense？
|
E*******F
发帖数: 2165 | 25 可能我误解了你的意思
你前面不是说要查找logn次吗
还是那个极端的例子，如果全是0，要找第一个0
第一次折半，找到中间那个0（假设总是跟mid比较）
第二次折半，找到1/4处那个0
是这样吗？还是我误解了你的意思
【在 t****t 的大作中提到】
: 一共两次折半查找, 为什么复杂度不是log n?
|
E*******F
发帖数: 2165 | 26 好了，我想清楚了
确实是O(logn)
我想的方法复杂了，就是每次折半以后，再search for key
其实直接找mid跟key比较就可以了，不用search for key
谢谢讨论 |
t****t
发帖数: 6806 | 27 当然啊, 这不是common sense吗?
【在 E*******F 的大作中提到】
: 可能我误解了你的意思
: 你前面不是说要查找logn次吗
: 还是那个极端的例子，如果全是0，要找第一个0
: 第一次折半，找到中间那个0（假设总是跟mid比较）
: 第二次折半，找到1/4处那个0
: 是这样吗？还是我误解了你的意思
|
E*******F
发帖数: 2165 | 28 不错，我开始想的就是在剩下的数组里查找key
其实只要直接用mid比就可以了
所以我想的那个方法过于复杂
【在 t****t 的大作中提到】
: 你除了查找一个确定的数, 不会查别的了吗? 有没有这么难沟通啊...
|
c****n
发帖数: 21367 | 29 对于sorted sequence，存在相等情况的时候
如果
1. 第一个0和最后一个0是等价的，那么二分查找只要一次
中间那个0，左右一看，都相等，那就是这个0了
2. 需要找到地址（序列号）最小的那个0，
二分查找最坏情况log n次，这个界比O(log n)还紧
【在 t****t 的大作中提到】
: 为什么全是0的情况下找不到第一个0?
: 找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
: 就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
: 到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
: std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
: 哪里, 也不明白为什么你不愿意看一下现成的STL code.
: 最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你.
|
c****n
发帖数: 21367 | 30 二分查找的任何一步的起始值比0大比0小都可以啊
【在 E*******F 的大作中提到】
: 全是0的数组也是sorted的啊，本来就是找第一次出现的位置，所以有重复
: 当然，遇到这种特殊情况，折半查找不是最优化的
: 但我的意思是如果用这样的方法，每次跟一个mid比，
: 要比logn次才能比完
: 虽然需要查找的数列大小指数递减，但最后还是比O(logn)慢
: 应该是O(logn*logn)
|
|
|
G*****7
发帖数: 1759 | 31
are you serious.
【在 E*******F 的大作中提到】
: 你仔细想想
: log(n)+log(n/2)+log(n/4)....+log(1)
: 这个级数求和会是logn吗
: 总共有logn项呢，不是常数个项
: 当然这只是worse case
: 还有，如果都是整数也好办，直接查找-0.5就行了
|
c*********e
发帖数: 16335 | 32 这个贴子是我今年看到最逗的。删了吧。
【在 E*******F 的大作中提到】
: 好了，我想清楚了
: 确实是O(logn)
: 我想的方法复杂了，就是每次折半以后，再search for key
: 其实直接找mid跟key比较就可以了，不用search for key
: 谢谢讨论
|
E*******F
发帖数: 2165 | 33 也没什么逗的，人有时候陷入思维定式而已
【在 c*********e 的大作中提到】
: 这个贴子是我今年看到最逗的。删了吧。
|
