主定理复习笔记

· · 个人记录

↑ 老图了）

例题

历年真题

设某算法的时间复杂度函数的递推方程是 T(n) = T(n - 1) + n（ n 为正整数）及 T(0) = 1，则该算法的时间复杂度为（ ）。

A. O(log n)

B. O(n log n)

C. O(n)

D. O(n^2)

这题都不用主定理。

对于每一个 n，都要倒序算到 1，所以是 D。

LaTeX 比较多就截个图吧）

主定理：

所以时间复杂度为 $O(n^{\frac{1}{2}}log$ $n) = O(\sqrt{n}$ $log$ $n)

选 C。