28

私は最近 MIT の 6.006 講義を見始めました。最初の講義では、インストラクターがピーク検出アルゴリズムを提示しました。

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf

彼の定義によると：

配列 [a,b,c,d,e,f,g] が与えられ、ここで ag は数値であり、a <= b かつ b>= c の場合に限り、b はピークです。

彼は再帰的なアプローチを与えました：

if a[n/2] < a[n/2 -1] then look for a peak from a[1] ... a[n/2 -1]
else if a[n/2] < a[n/2+1] then look for a peak from a[n/2+1] ... a[n]
else a[n/2] is a peak

彼は、アルゴリズムは T(n) = T(n/2) + o(1) = o(lgn) であると言いました

彼の pdf で、彼は完全な例も示しました。[6,7,4,3,2,1,4,5]

7 と 5 の両方がピークです。しかし、上記のアルゴリズムは、真ん中の要素がたまたま最初の分岐を満たすという理由だけで、ピークとして 7 を見つけるだけではありませんか?

  1. では、すべてのピークを見つけなければならない場合でも、配列全体を見ていくことになりますか? それは最悪のケースNを意味しますか？

  2. 彼の定義は、単一のピークを見つけるだけでよいことを意味しているのでしょうか?

この問題は、Riverst のアルゴリズム入門書で最大要素と最小要素を見つけることと見なすことができると思います。

4

5 に答える 5

5

昨日このコースを始めたばかりで、問題文は次のとおりです。

問題: 存在する場合はピークを見つける (常に存在するか?)

したがって、アルゴリズムが行うことは、可能な限り短い時間で最初に利用可能なピークを見つけようとすることです。

これが、このアルゴリズムが 1 つのピークのみを検出する理由です。

于 2013-11-20T16:57:57.783 に答える
0

このアルゴリズムは、二分探索アルゴリズムによく似ています。二分探索はソートされた配列でのみ機能し、このピーク検索アルゴリズムは別の定義で機能するように見えます: forおよび for のx[p]場合はピークです。質問の定義が間違っていて、これが正しいと判断した場合、すべて問題ありません。そして、それは間違っているように見えます.2番目のケースではいくつかのピークを与えるので、あなたは正しいです.0 <= i < p x[i] <= x[i + 1]p <= i < x.size x[i] >= x[i + 1]

于 2013-09-21T12:23:43.913 に答える