-2

私と私の友人は、次のアルゴリズムの問​​題について話し合いました、

"Describe a recursive algorithm for finding the maximum element in an array A of n        
elements. What is your running time and space usage?"

O（n）時間の使用があると結論付けました。このステートメントによれば、F（n）= A [n]をF（n-1）と比較し、再帰の基本ケースで、A[0]とA[1]を比較してから、大きい方を返します。 A[2]。再帰が進むにつれて、最終的には配列内の最大要素を返します。

n回の再帰ごとに、1回だけ比較するため、最終的にO（n）回の使用があると推測しました。私の質問は、私たちの解決策がわからないということです。そのため、このアルゴリズムと私たちの解決策について他にコメントが必要です。ありがとうございました。

4

2 に答える 2

0

はい。あなたは正しいです、それは事実O(n)です。非常に簡単にできる方法は、

アルゴリズムの基本操作は比較です。そして、再帰のステップでは、比較は一度だけ行われます。

だからあなたは言うことができます

m(n) = m(n-1) + 1
m(n-1) = m(n-2) + 1 + 1
m(n-2) = m(n-3) + 2 + 1

得られる一般化

m(n-i) = m(n-1-i) + i + 1

現在、ベースケースでは比較を行っていません (ベースケースには要素が残っていないため、現在の最大のものを返します)。これを次のように書くことができます

m(0) = 1

基本ケースを取得するために再帰方程式に代入すると、i = n-1

我々が得る

m(n) = m(0) + n - 1 + 1

しかしm(0) = 0

だから私たちは得る

m(n) = n

したがって、アルゴリズムはO(n)です。これを証明する他の方法もあります。O(n)また、数学的な証明がなくても、アルゴリズムは再帰ステップごとに 1 つの基本操作のみを実行し、アルゴリズムは入力に関係なく常に n ステップを再帰するため、論理的に言うことができます。

于 2013-03-11T13:14:43.333 に答える
0

配列に含まれている場合、時間の複雑さを見つけるためのアプローチは問題ありませんintegers。数値の場合、2 つの数値を比較することは単位操作と見なすことができます。そして、配列を繰り返し処理しながら、最大値を見つけるために、この操作がn何度も実行されます。したがってO(n)。

ただし、配列に複雑なデータ型が含まれている場合、たとえばstringの場合、2 つの文字列の比較は単位操作とは見なされません。文字列を比較するには、文字列の各文字を反復処理する必要がある場合があります。この場合、アルゴリズムの時間の複雑さは、配列内の文字列の長さに応じて開始される場合もあります。他のデータ型についても同様に、2 つのオブジェクトの比較は単位操作ではない場合があります。しかし、あなたの場合、配列には数字が含まれているように見えるので、あなたは良いです。

于 2013-03-11T13:16:54.040 に答える