如何在给定运行时间的情况下编写算法
问题描述:
我目前正在进行算法分析课程。测验的问题之一是编写一个运行时间为T(n) = 4T(3n/4) + n^2
的算法,算法不必做任何重要的事情。如何在给定运行时间的情况下编写算法
我找不到任何类似的例子,所以我不确定如何继续。
答
为简化如何思考这类问题,只需使用一组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)
这使现在更有意义。谢谢。 – user6916859