登入選單
返回Google圖書搜尋
註釋Abstract: "A function f:R [approaches] R is k-modal if its kth derivative has a unique zero. We study the problem of finding the smallest possible interval containing the unique zero of the kth derivative of such a function, assuming that the function is evaluated only at integer points. We present optimal algorithms for the case when k is even and for k = 3, and near-optimal algorithms when k [> or =] 5 and odd. A novel generalization of Kraft's inequality is used to prove lower bounds on the number of function evaluations required. We show how our algorithms lead to an efficient divide-and-conquer algorithm to determine all turning points or zeroes of a k-modal function