太平洋的抽油烟机太难装了# Living
O*i
1 楼
看去比二分法求方程的根要难些，应该怎么做？为什么最坏情况是O(n)呢？
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
现在给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一个
算法快速查找这个值。我给出的算法最坏情况是O(n)，平均是O(lgn)，但是很可惜没来
得及写完。
跟离散的情况类似。比如一个数组n个元素，先递增然后递减。找到最大元素的index。
类似binary search。版上最近也讨论过。连续的情况，给定x0，要比较f(x0)与f(x0+
delta)的大小然后binary search。delta是答案的精度。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
现在给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一个
算法快速查找这个值。我给出的算法最坏情况是O(n)，平均是O(lgn)，但是很可惜没来
得及写完。
跟离散的情况类似。比如一个数组n个元素，先递增然后递减。找到最大元素的index。
类似binary search。版上最近也讨论过。连续的情况，给定x0，要比较f(x0)与f(x0+
delta)的大小然后binary search。delta是答案的精度。
