実行時にアルゴリズムを書く方法

Question

私は現在アルゴリズム解析コースを受けています。クイズの質問の1つは、ランタイムT(n) = 4T(3n/4) + n^2でアルゴリズムを書くことでした。ここでアルゴリズムは重要なことをする必要はありません。

同様の例が見つかりませんでしたので、進める方法がわかりません。

Answer 1

この種の問題の考え方を簡単にするには、n要素の配列を使用して、サイズnの問題を表現してください。

実行時間T(n)は、アレイで実行されるアルゴリズムを表します。

実行時間4T(3n/4)は、アレイの3/4で4回実行されるアルゴリズムを表します。

実行時間n^2は、アレイ上のいくつかの2次演算（バブルソートなど）を表します。

silly_algo (arr[], n) 
    if n == 0 return 
    for i : 1..4 
     silly_algo(arr, 3*n/4) 
    bubblesort(arr, n)