一般分治法的渐近复杂性分析

一般分治法的计算机复杂性可用递归方程Ｔ（ｎ）＝ａ（ｎ））＝ｆ（ｎ）来描述．以往只对具体 形式的ａ（ｎ）、ｂ（ｎ）和ｆ（ｎ）给出解的表格．对于一般的这类递归议程的解没有系统的论述．本文提出 解此类递归议程的一个一般的系统框架，给出了复杂性的一般通式，将通常人们面向问题的讨论 方式转为面向技术的讨论方式。

Asymptotic Analysis for General Divide and Conquer Recurrences

The time complexities of general divide and conquer algorithms can often be ana- lysed by solving the recurrence equations in the form T(n) = a(n). T(b(n)) +f(n). Much work has been done for solving recurrences of this form. The only methods presented pre- viously, however, consist of solution tables for fixed a(n), b(n) and f(n). The systematic way of solving general recurrences of the above form is not available so far. In this paper we present a general frame for solving recurrences of the above form. Thus, the time complexi- ties of general divide and conquer algorithms can be analysed easily.