O******i
发帖数: 269 | 1 看去比二分法求方程的根要难些，应该怎么做？为什么最坏情况是O(n)呢？
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
现在给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一个
算法快速查找这个值。我给出的算法最坏情况是O(n)，平均是O(lgn)，但是很可惜没来
得及写完。
跟离散的情况类似。比如一个数组n个元素，先递增然后递减。找到最大元素的index。
类似binary search。版上最近也讨论过。连续的情况，给定x0，要比较f(x0)与f(x0+
delta)的大小然后binary search。delta是答案的精度。 |
O******i
发帖数: 269 | 2 版上最近也讨论过。
孤陋寡闻，有谁知道讨论帖的link么？多谢。 |
p*****2
发帖数: 21240 | |
n*******w
发帖数: 687 | 4 根据binary search稍微变化了一点。代码在这里。
http://www.mitbbs.com/article_t/JobHunting/31992101.html
【在 p*****2 的大作中提到】
: 顶你。我也想看看是如何讨论的。
|
q****x
发帖数: 7404 | 5 要严格递增/递减吧。否则如果是常函数，每个点都是正解。
【在 O******i 的大作中提到】
: 看去比二分法求方程的根要难些，应该怎么做？为什么最坏情况是O(n)呢？
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 现在给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一个
: 算法快速查找这个值。我给出的算法最坏情况是O(n)，平均是O(lgn)，但是很可惜没来
: 得及写完。
: 跟离散的情况类似。比如一个数组n个元素，先递增然后递减。找到最大元素的index。
: 类似binary search。版上最近也讨论过。连续的情况，给定x0，要比较f(x0)与f(x0+
: delta)的大小然后binary search。delta是答案的精度。
|
