引入

所谓时间复杂度粗略讲即是程序运行时间，然而运行时间受很多因素影响 (平台，硬件，操作系统等)。所以为了在数学上能统一定量分析，需要一些假定: 加(减)，乘(除)等数值运算，比较等逻辑运算，赋值等表达式，return 语句的时间复杂度都为常数时间 (为 1, one time unit)。

现分析下面程序的时间复杂度作为示例：

// e-1
int Sum(int N) {
    int i, S;
    S = 0;
    for(i = 1; i <= N; i++) {
        S += i * i * i;
    }
    return S;
}

分析如下:

第 2 行声明或定义，在编译期完成而非程序运行时期，忽略时间；
第 3 行赋值，时间为 1；
第 7 行返回值给调用的地方，时间为 1；
第 4-6 为 for 循环，第一次进入循环，i=1 (时间为 1)，i <= N (时间为 1)。S+=i*i*i <=> S=S+i*i*i 包含两次乘法 (时间为 2)，一次加法 (时间为 1)，一次赋值 (时间为 1)，故这条语句总时间为 4。之后，i 从 2 到 N 取值，每次取值循环都包含：i++ (时间为 1)，i <= N (时间为 1)，S+=i*i*i (时间为 4)。故 i 从 1 到 N 时，每次循环时间都为 6，故总时间为：6N + 2 (i 第 N 次循环完成后，还要执行一次 i++ 和 i<=N 运算)。

故 e-1 的时间复杂度为 6N + 4 = 6N + 2 + 2。

从 e-1 例子可以看出，输入数据是给定的，运算方式也固定，即该时间复杂度不受输入数据的影响。但在其它一些情形下，相同的一段代码会随着输入数据分布不同产生不同的时间复杂度。比如冒泡排序，对输入序列 1 2 3 4 5 和 2 4 3 1 5 时间复杂度是不同的，并且在生产环境中，并不能事先知道下一条输入数据会是怎样的。所以这种情况下所计算的时间就有很多可能，会在一个范围内变化。为衡量这种情况下的时间复杂度，引入渐进符号。

复杂度记号

记号

用表示以下函数集合: (g(n)) = {f(n): 存在正常数 , 和 , 使得对所有的 , 有 }, 通常记作 f(x)=(g(n)).

记号给出函数上界与下界。

证明: .

需确定的值, 使对所有 , 有:

选择合适的便可求得。

记号

用表示以下函数集合: (g(n)) = {f(n): 存在正常数 , 和 , 使得对所有的 , 有 }, 通常记作 f(x)=(g(n)).

记号

用表示以下函数集合: (g(n)) = {f(n): 存在正常数 , 和 , 使得对所有的 , 有 }, 通常记作 f(x)=(g(n)).

其它时间复杂度记号参见算法导论一书。

常使用的是记号，表征函数上界，即最坏情况运行时间。

递归简述

首先以阶乘为例：

// e-2
long int Factorial (n) {
    if (n <= 1) {
        return 1;
    }
    else {
        return n * Factorial(n-1);
    }
}

然后是斐波拉契数列为例：

// e-3
long int Fib (n) {
    if (n <= 1) {
        return 1;
    }
    else {
        return Fib(n-1) + Fib(n-2);
    }
}

简单分析其运行时间，当时，，其中 2 是行 2 和行 6 的时间和。

现简单计算其时间复杂度，由于斐波拉契通项公式为：。故可知，又因为，进一步当时，。故可知 e-3 运行的时间是指数级的。后面会给出另一个更高效的算法，并解释为何 e-3 算法复杂度会这么高。

求解递归式三种方法

一般有代入法，递归树法，主方法三种。都可以求出算法的和的渐近界。

代入法

例 1：求下面递归式的上界

猜想其解为；
根据的定义，存在正常数 , 使时满足，故要找到这样的。由递归表达式可推出；
设上界对所有都成立，当，有。代入得：

要

只需即可。

例 2：求下面递归式的上界

递归树法

以

为例说明递归树法。

主函数法

形如：

的递归式，其中可解释为或者 ,由以下主定理给出解答：

若对某个常数有，则；
若，则；
若对某个常数有，且对某个常数和所有足够大的 n 有，则。

例子: