填空题

分治算法的时间复杂性常常满足如下形式的递归方程：

其中，g（n）表示（）。

答案：将规模为n的问题分解为子问题以及组合相应的子问题的解所需的时间

你可能感兴趣的试题

设D_n表示大小为n的输入集合，t（I）表示输入为I时算法的运算时间，p（I）表示输入I出现的概率，则算法的平均情况下时间复杂性A（n）=（）。

答案：

在忽略常数因子的情况下，O、Ω和Θ三个符号中，（）提供了算法运行时间的一个上界。

答案： O