第二章 算法时间复杂度

一、主定理 1、 主要是计算 n_log_b_a 。求出来之后和后面的Fn进行比较,然后按照规则些出结果就行。 2、一句话解释:这两个值哪一个大就取谁;想等的话先看Fn里面log的次数,最终的结果在log的基础之上+1就是最终结果log的次数。例题如右下角 3、要注意的一点就是:保证T(n)的形式要和定理里面的一样,一个大问题拆解成为几个相等的小问题。 1、例题如上。 2、N!是阶数最高的,属于NP难问题。复杂度是最大的。 3、n的n次方乘以log n。 Fib数列递推公式的证明(斐波那契数列) 斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐