以下算法的 运行 时间是多少（以 -notation 表示）？
What is the running time of the following algorithm (in terms of -notation)?
算法求解一个大小为</code>的问题如下：递归求解3个大小为<code> - 2的子问题，然后及时构造原问题的答案(1).
很明显Master定理不能应用在这里。所以，我想到了画一个递归树，但是困扰我的是，我需要考虑两种情况：什么时候n是odd/even？或者结果总和以及 运行 时间根本不依赖于此？提前致谢。
我们必须假设递归的基本情况发生在 0 或 1 时。也可能是基本情况发生在 1 或 2 时，不允许为 0。我们不太清楚，但不是那么相关。
在第一种情况下，奇数给定的运算次数与-1 的运算次数相同。在第二种情况下，它的操作次数与 +1 相同。
因此，为了确定渐近复杂度，我们可以只看偶数（或只看奇数）。
递归树是一个完美的三元树，高度为 (+1)/2 或 (+2)/2（同样：取决于基本情况）。
在一棵高度为 h 的完美三叉树中，我们有 (3h-1)/2个节点，所以就是O(3h )，即O(3/2) = O((√3) ).
除了@trincot 提出的解决方案之外的另一个（可能更简单的）解决方案：
T(n)=3T(n-2)+O(1)=...=3k(T(n-2k)+O(1) ).
让我们找出这个递归关系的停止条件，即需要找到满足以下条件的k：n-2k=0 --> k=n/2 --> T(n)= O(3n/2)=O(√3n)
算法求解一个大小为</code>的问题如下：递归求解3个大小为<code> - 2的子问题，然后及时构造原问题的答案(1).
很明显Master定理不能应用在这里。所以，我想到了画一个递归树，但是困扰我的是，我需要考虑两种情况：什么时候n是odd/even？或者结果总和以及 运行 时间根本不依赖于此？提前致谢。
我们必须假设递归的基本情况发生在 0 或 1 时。也可能是基本情况发生在 1 或 2 时，不允许为 0。我们不太清楚，但不是那么相关。
在第一种情况下，奇数给定的运算次数与-1 的运算次数相同。在第二种情况下，它的操作次数与 +1 相同。
因此，为了确定渐近复杂度，我们可以只看偶数（或只看奇数）。
递归树是一个完美的三元树，高度为 (+1)/2 或 (+2)/2（同样：取决于基本情况）。
在一棵高度为 h 的完美三叉树中，我们有 (3h-1)/2个节点，所以就是O(3h )，即O(3/2) = O((√3) ).
除了@trincot 提出的解决方案之外的另一个（可能更简单的）解决方案：
T(n)=3T(n-2)+O(1)=...=3k(T(n-2k)+O(1) ).
让我们找出这个递归关系的停止条件，即需要找到满足以下条件的k：n-2k=0 --> k=n/2 --> T(n)= O(3n/2)=O(√3n)