選択並べ替え再帰関係

Question

先頭に戻るこれは宿題に関する質問ですが、再発関係を理解するのが難しいです。私は例のためにインターネットを磨き、彼らは私には非常に曖昧です。私は、再帰的アルゴリズムの漸化関係にはそれぞれの処理方法が設定されていないことを理解していますが、これらを理解する方法は分かりません。 - + CN + C T（T（N）= T（1〜N）：私はこれは私が来るよ何であることを理解するものからそう

void selectionSort(int array[]) { 
    sort(array, 0); 
} 

void sort(int[] array, int i) { 
    if (i < array.length - 1) 
    { 
     int j = smallest(array, i); T(n) 
     int temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     sort(array, i + 1); T(n) 
    } 
} 

int smallest(int[] array, int j)  T(n - k) 
{ 
    if (j == array.length - 1) 
     return array.length - 1; 
    int k = smallest(array, j + 1); 
    return array[j] < array[k] ? j : k; 
} 

：ここで私はと仕事をしなければならないアルゴリズムですn-1）はソートの再帰関数を表し、加算されたcnは最小値の再帰関数を表し、nが減少するにつれて減少するはずである。なぜなら、それは毎回アレイに残っている時間量のみと呼ばれるからである。 nを乗じた定数は、追加コードを最小で実行する時間であり、追加定数は、ソートで追加コードを実行する時間です。これは正しいですか？私は完全にオフですか？正しく説明していないのですか？また、次のステップは、これから再帰ツリーを作成することですが、私はこの式をT（n）= aT（n/b）+ cという形では見ません。 。また、正しい場合は、再帰関係がn^2にどのようになるかわかりません。これは私の最初の投稿でもありますので、ここで間違ったことをした場合はお詫びします。助けてくれてありがとう！

Answer 1

時間の複雑さを計算する最も簡単な方法は、それぞれの関数の時間複雑さを別の反復関係でモデル化することです。

反復関係S(n) = S(n-1)+O(1)、S(1)=O(1)を使用して、関数smallestの時間複雑さをモデル化できます。これは明らかにS(n)=O(n)に解決します。

T(n) = T(n-1) + S(n) + O(1)、T(1)=O(1)でsort関数の時間複雑さをモデル化することができます。関数sortの中でsmallestと呼ぶため、S(n)という用語が入ります。 S(n)=O(n)はT(n) = T(n-1) + O(n)と書くことができ、再発を書くことはT(n)=O(n)+O(n-1)+...+O(1)=O(n^2)です。

したがって、合計実行時間は期待通りにO(n^2)です。