1
我想弄清算法的运行时间。这是一种通过将问题分成2/3组（这是CLR排序）的方式。我有一些麻烦提出来，这是我有：试图找到重复的渐近运行时的问题
T（n）= 3T（[2n]/3）+1（1是因为除了递归调用，有一个交换可能会或可能不会进行。假设它做，它仍然只是一个成本不变）。
T(n)=3T([2([2n]/3+1)]/3+1)+1
T(n)=3T([2([2([2n]/3+1)]/3+1)]/3+1)+1
T(n)=3T([2([2([2([2n]/3+1)]/3+1)]/3+1)]/3+1)+1
等......直到我们可以假设，在某一时刻，我们终于打到基地T（n）的情况，并获得该运行时的常量值1。这给了我们：
3([2([2([2([2(...........)]/3+1)]/3+1)]/3+1)]/3+1)+1 with logn terms (that's the "......." in the middle). This gives:
3*(2n/3+1)^(logn)+1*logn
3*(2n/3+1)^(logn)+logn
那么我认为，因为如果日志的基地为2n/3 + 1，我们可以简化它仅仅是3 * LOGN + LOGN，我们可以这样做。 （我一直听说，当做渐近表示法时，我们选择的日志的基础并不重要....）
这变成了4logn。该系数下降，变成简单的登录。
这是正确的吗？我不知道我是否正确地扩展了它，或者如果我的日志操作是合法的......另外，这个最终结果是什么 - 大O，θ等等。我不确定我在看什么。 ..
谢谢。