分而治之算法的最坏情况运行时间

Question

我是一名正在学习编程 class 数据结构和算法的学生，我需要帮助解决一道我似乎无法掌握的考试题。

这是问题所在：

考虑以下算法 func 在给定数组 A = {a1, a2, ...,一个}:

给出该算法最坏情况运行时间的递归。

如果我的解释不清楚，这里是作业图片的link：http://i.imgur.com/VftEgDX.png

我知道这是一个分而治之的问题，但我很难弄清楚如何解决它。

谢谢 :)

Answer 1

If a1 > an, then exchange a1 and an.

这是一个常量运算 - 所以 O(1)

Run func on {a1, a2, ... ,a2n/3}.

你递归调用数组的 2n/3，所以 T(2n/3)

Run func on {an/3, a(n/3)+1, ... ,an}.
Run func on {a1, a2, ... ,a2n/3}.

和上面类似，每一个都是T(2n/3)

这给你总共 T(n) = 3T(2n/3) + O(1)，和 T(1) = O(1)。

现在，我们可以得到一个大 O 符号，使用 master theorem case 1:

log_{3/2}(3) ~= 2.7

O(1) 在 O(n^2.7) 中，因此我们可以使用大小写，并得到 T(n) 在

中

Theta(n^log_{3/2}(3)) ~= Theta(n^2.7)

Worst-case running time of divide and conquer algorithm