卡特兰数(Catalan number) 其实来源于卡特兰解决凸n+2n+2n+2边形的剖分问题得到的数列f(n)f(n)f(n)（为了便于区分组合数，这里用f(n)f(n)f(n)表示）。卡特兰数是组合数学中常出现在各种计数问题中的数列。1,1,2,5,14,42,132...1,1,2,5,14,42,132...1,1,2,5,14,42,132...卡特兰数的性质通项公式: f(n)=C2

主定理是分析分治算法时间复杂度很重要的一个定理。我们之前对于一个递归类的代码进行时间复杂度分析，一般会采用递归树的方式，下面我们先介绍一下递归树的方式，理解之后，再引入主定理的相关内容。分治的介绍分治算法总是将问题的规模不断的拆分，以归并排序为例。假设T(n)T(n)T(n)代表原问题的规模，nnn为输入数据的规模。第一次拆分后，假设拆分成两份，规模就变成了n2\frac{n}{2}2n​​，然后