2. 计算语句执行次数的数量级
3. 用大O来表示结果
继续以上述算法为例,进行分析:
1.
执行次数最多的语句为num2 += num1
2.
T(n) = n*log2n
f(n) = n*log2n
3.
// lim(T(n)/f(n)) = 1
T(n) = O(n*log2n)
最后,列出几个比较有用的递归分治的时间复杂度计算公式吧。