时间复杂度概念

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行的次数越多，它花费的时间就越多。

时间频度、语句频度：标记为 T(n)

1、忽略常数项

2、忽略低次向

3、忽略系数

时间复杂度：

一般情况下，算法中的基础操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数 f(n)，使得当n趋近于无穷大时，T(n) / f(n)的极限值为不等于0的常数，则称f(n)是 T(n)的同数量级函数。

记作 T(n)=O(f(n))，称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

例：

T(n) = n²+7n+6 = O(n²)

T(n) = 3n²+2n+2 = O(n²)

复杂度都为： O(n²)

思维引导：

1、常数项忽略：公式1的+6、公式2的+2

2、低次向忽略：公式1的+7n、公式2的+2n

3、系数忽略：公式2的3 * n²，可以把3忽略

计算方式：

1、用常数1代替运行时间中的所有加法常数： T(n) = 2n² + 7n + 6~>T(n)=n² + 7n +1

2、修改后的运行次数函数中，只保留最高阶项： T(n)=2n² + 7n + 1~>T(n) = 2n²

3、去除最高阶项的系数：T(n) = 2n² ~> T(n) = n²~>O(n²)

时间复杂度简单例子：

对数阶 O(㏒2n):

tips：如果N = a^x(a>0,a≠1)，即a的x次方等于N(a>0，a≠1)，那么数x叫以a为底N的对数，记作x = logaN。其中，a叫做对数的底数，N叫做真数，x叫做“以a为底N的对数”