如何在给定运行时间的情况下编写算法

Question

我目前正在进行算法分析课程。测验的问题之一是编写一个运行时间为T(n) = 4T(3n/4) + n^2的算法，算法不必做任何重要的事情。

我找不到任何类似的例子，所以我不确定如何继续。

Answer 1

为简化如何思考这类问题，只需使用一组n元素来表示大小为n的问题。

然后，运行时间T(n)表示在阵列上运行的算法。

运行时间4T(3n/4)表示四次在阵列的四分之三上运行的算法。

运行时间n^2表示数组上的某些二次运算（例如，冒泡排序）。

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