我试图弄清楚算法的运行时间。这是一种通过将问题分成 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。系数下降到简单的logn。
这个对吗？我不确定我是否正确扩展了它，或者我的日志操作是否合法......此外，这个最终结果是什么——big-O、theta 等。我不确定我在看什么。 ..
谢谢。