アルゴリズム導論(一)Peak Finding

アルゴリズム導論(一)Peak Finding
問題は、ベクトルの中間位置要素について、2つの隣接位置要素に等しい数値より大きい場合はpeakとみなされ、ベクトル境界位置要素にとって、1つの隣接位置要素に等しい数値より大きいだけでよい1次元のベクトルを記述する.指向性量に出力するpeakが必要です.条件が大きい場合peakアルゴリズム1は存在しない可能性がある.最も直接的なアルゴリズム:左から右へ遍歴し、時間の複雑さはθ ( n )\theta(n) θ(n) 2.分治思考のアルゴリズムを利用する:

if a[n/2]

時間の複雑さはθ\theta θ(log 2 n)問題は、ある位置数値が4隣接位置要素(境界が3つまたは2つの比較可能な値しかない)に等しい数値より大きい場合、peakとみなされる2次元ベクトルを記述する.指向性量に出力するpeakが必要です.アルゴリズム1.欲張りAscentアルゴリズムの時間複雑度はθ ( n 2 )\theta(n^2) θ(n2) 2.分治思考のアルゴリズムを利用する:

min = 0;max = m;
Pick a column j = (min+max)/2;
while true
	find the position(i, j) of the maximum of column j
	if (i,j-1)>(i,j)
		max = j;
		pick colum j = (min+max)/2;
	else if (i, j+1)>(i,j)
		min = j;
		pick colum j = (min+max)/2;
	else
		return (i,j);

時間の複雑さはθ\theta θ(nlog 2 m)、ここでnは行数、mは列数を表す