「アルゴリズム導論」[第2章]アルゴリズム入門-[2.2]アルゴリズム分析
2079 ワード
124概念の回顧
アルゴリズム解析とは、アルゴリズムに必要なリソースを予測することです.
一つのアルゴリズムについては、一般的にその最悪の場合の運行時間だけを調べます.理由は三つあります.アルゴリズムの最悪の場合の動作時間は、任意の入力において実行時間の上限である. は、いくつかのアルゴリズムにとって、最悪の場合はかなり頻繁に発生します. 大体において、「平均状況」は通常最悪の場合と同じです. 練習問題が解けます
2.2-1用Θ形式表現関数n³/1000-10 n²-100 n＋3です
答え:Θ(n³)
2.2-2配列Aのn個の数を並べ替える問題を考える.まず、Aの中の最小要素を見つけて、Aの中の要素と交換します.次に、Aの中の次数の最小要素を見つけて、A[2]の要素と交換します.Aの中の先頭n-1個の要素をこのプロセスに続けます.このアルゴリズムの疑似コードを書き出します.このアルゴリズムは並べ替えを選択(selection)と呼ばれます.このアルゴリズムでは、サイクル不変式は何ですか?なぜ、n-1要素のすべてではなく、頭n-1要素で動作する必要があるのですか?選択順序の最適性と最悪の場合の運転時間をO形式で書き出します.
[問題1]ダミーコードは以下の通りです.
初期化:この時i=1で、サブアレイA［1.i］です.つまり、1つの要素A［1］だけが含まれています.明らかに順序付けされています.
保持:2番目のfor循環体では、A[i]からA[n]までの配列要素の中から一番小さいのを選択し、i番目の要素であるA[i]と互いに対応する値を交換します.このとき、A[1.i-1]がすでに並べられていると仮定して、新たに選択されたのもA[i.i-1]のいずれかの数より大きいです.つまり、A[1.i]も並べ替えられています.
終了:i=n-1の場合、2番目のforサイクルは、A[n-1]とA[n]の中から、より小さいのを選んで、A[n-1]と値を交換します.その後、すべての要素は並べ替え済みです.
[問題3]i=n-1の場合、2番目のforはA[n-1]とA[n]の二つの要素しかないので、その中から小さい数を選んでA[i]の値と交換した後に最後の2番目に配置されますが、大きな数(同時に全部の要素の中で一番大きい)は自然に最後の位になります.明らかに順序付けの要求を満たしています.
[問題4]ベストと最悪の場合の運行時間は全部Θ(n²).このような直接的な選択により、キーワードの比較回数は各要素の元の配列順序とは無関係である.
2.2-3線形検索問題(練習2.1-3参照)を再度検討します.平均的には、入力シーケンスのいくつかの要素をチェックします.検索対象の要素は配列の中のいずれかの要素の可能性が等しいと仮定します.最悪の場合はどうなりますか?Θ形式で表すと、線形検索の平均状況と最悪の場合の運行時間はどうなりますか?あなたの答えについて説明します.
平均的な状況は(n-1)/2要素を検索する必要があります.最悪の場合はすべてのn要素を遍歴する必要があります.
検索対象の要素は、配列の中の任意の要素の可能性が等しいので、すなわち、すべて1／nである場合、平均的な場合の検索回数は、次のようになります.
(1+2+3+…+n)*(1/n)=(n-1)/2
最悪の場合は、この数列に対応する値が見つからないので、完全な数列を経て確認することができます.
使う?遣うΘ形式を表すΘ(n)
2.2-4はどのようにアルゴリズムを修理すれば、より良い最適な実行時間を持つことができますか?
答え:コアアルゴリズムの開始前に、まず判断を行います.入力されたデータが結果を満たしたら、直接アルゴリズムから飛び出して結果を出力します.逆に、正常な手順で解決します.
アルゴリズム解析とは、アルゴリズムに必要なリソースを予測することです.
一つのアルゴリズムについては、一般的にその最悪の場合の運行時間だけを調べます.理由は三つあります.
2.2-1用Θ形式表現関数n³/1000-10 n²-100 n＋3です
答え:Θ(n³)
2.2-2配列Aのn個の数を並べ替える問題を考える.まず、Aの中の最小要素を見つけて、Aの中の要素と交換します.次に、Aの中の次数の最小要素を見つけて、A[2]の要素と交換します.Aの中の先頭n-1個の要素をこのプロセスに続けます.このアルゴリズムの疑似コードを書き出します.このアルゴリズムは並べ替えを選択(selection)と呼ばれます.このアルゴリズムでは、サイクル不変式は何ですか?なぜ、n-1要素のすべてではなく、頭n-1要素で動作する必要があるのですか?選択順序の最適性と最悪の場合の運転時間をO形式で書き出します.
[問題1]ダミーコードは以下の通りです.
SELECTION-SORT(A)
for i←1 to n-1
do min←∞
for j←i to n
do if A[i]<min
then min←A[j]
minlabel←j
exchange A[i]↔A[minlabel]初期化:この時i=1で、サブアレイA［1.i］です.つまり、1つの要素A［1］だけが含まれています.明らかに順序付けされています.
保持:2番目のfor循環体では、A[i]からA[n]までの配列要素の中から一番小さいのを選択し、i番目の要素であるA[i]と互いに対応する値を交換します.このとき、A[1.i-1]がすでに並べられていると仮定して、新たに選択されたのもA[i.i-1]のいずれかの数より大きいです.つまり、A[1.i]も並べ替えられています.
終了:i=n-1の場合、2番目のforサイクルは、A[n-1]とA[n]の中から、より小さいのを選んで、A[n-1]と値を交換します.その後、すべての要素は並べ替え済みです.
[問題3]i=n-1の場合、2番目のforはA[n-1]とA[n]の二つの要素しかないので、その中から小さい数を選んでA[i]の値と交換した後に最後の2番目に配置されますが、大きな数(同時に全部の要素の中で一番大きい)は自然に最後の位になります.明らかに順序付けの要求を満たしています.
[問題4]ベストと最悪の場合の運行時間は全部Θ(n²).このような直接的な選択により、キーワードの比較回数は各要素の元の配列順序とは無関係である.
2.2-3線形検索問題(練習2.1-3参照)を再度検討します.平均的には、入力シーケンスのいくつかの要素をチェックします.検索対象の要素は配列の中のいずれかの要素の可能性が等しいと仮定します.最悪の場合はどうなりますか?Θ形式で表すと、線形検索の平均状況と最悪の場合の運行時間はどうなりますか?あなたの答えについて説明します.
平均的な状況は(n-1)/2要素を検索する必要があります.最悪の場合はすべてのn要素を遍歴する必要があります.
検索対象の要素は、配列の中の任意の要素の可能性が等しいので、すなわち、すべて1／nである場合、平均的な場合の検索回数は、次のようになります.
(1+2+3+…+n)*(1/n)=(n-1)/2
最悪の場合は、この数列に対応する値が見つからないので、完全な数列を経て確認することができます.
使う?遣うΘ形式を表すΘ(n)
2.2-4はどのようにアルゴリズムを修理すれば、より良い最適な実行時間を持つことができますか?
答え:コアアルゴリズムの開始前に、まず判断を行います.入力されたデータが結果を満たしたら、直接アルゴリズムから飛び出して結果を出力します.逆に、正常な手順で解決します.