从本科计算机专业第一次接触时间复杂度，到现在读研还是读的计算机，对于时间复杂度还是半懂不懂的状态，今天又来回顾一次，不求完全搞懂，但求对其有更深的理解，以后学以致用！

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

但是光有以上三种求法是远远不够的，因为有时候我们会遇到更复杂的算法，这时候就需要用到两个求时间复杂度的定理：

1、分治法主定理

2、问题规模见效和递归求解主定理

首先先要了解增长率，所谓增长率就是随着输入规模的增加，算法运行时间增加的速度，他是输入规模的函数。

常用的增长率：

增长率

然后我们来一个一个地讲时间复杂度的求法：

大O表示法

大O表示法给出了函数f(n)的严格上限。一般来说，它可以表示为f(n)=O(g(n))。这表示当输入规模很大时，f(n)的上界是g(n)。

大O表示法的定义为，O(g(n))={f(n):存在这样的正常数c和n0使得对任意的n>=n0,0<=f(n)<=cg(n)成立}，则g(n)是f(n)的渐近上界。目的是求出大于或等于f(n)的g(n)。

举例说明：

以上就是时间复杂度的三个基础求法，接下来介绍两个定理，帮助我们求复杂的算法的时间复杂度。

分治法主定理

所谓的分治法主定理是把一个问题划分为多个子问题，每个子问题是原问题的一部分，然后执行一些额外的工作来计算最后的答案。下面给出运行时间计算公式：

分治法定理的相关问题：

问题规模减小和递归求解主定理

例题：

素材来源：《数据结构与算法 经典问题解析 java语言描述》[印]纳拉辛哈.卡鲁曼希

排版比较乱，图片也拍得不是很好，请大家见谅