笔记 1

数据结构主要研究组织大量数据的方法，算法分析则是对算法运行时间的评估。

用下列四个定义表示函数增长率的大小：

1. 如果存在正常数 c 和 n0 使得当 N>=n0 时 T(N)<=cf(N), 则记为 T(N) = O(f(N)).

2. 如果存在正常数 c 和 n0 使得当 N>=n0 时 T(N)>=cg(N), 则记为 T(N) = Ω(g(N)).
3. T(N) = θ(h(N)) 当且仅当 T(N) = O(h(N)) 且 T(N) = Ω(h(N)).
4. 如果 T(N) = O(p(N)) 且 T(N) ≠ θ(p(N)), 则 T(N) = o(p(N)).

例如，T(N) = 1000N, f(N) = N^2
用大 O 记法表述为：1000N = O(N^2)

即：

1. T(N) 增长率小于等于 f(N).

2. T(N) 增长率大于等于 g(N).
3. T(N) 增长率等于 h(N).
4. T(N) 增长率小于 p(N).

几个法则：
若 T1(N) = O(f(n)), T2(N) = O(g(n)), 则：

1. T1(N) + T2(N) = max(O(f(N)), O(g(N)))
2. T1(N) × T2(N) = O(f(N) × g(N)).

几个典型的函数增长率：

函数	名称
c	常数
logN	对数级
(logN)^2	对数平方
N	线性级
NlogN
N^2	平方级
N^3	立方级
2^N	指数级

PS: N 的增长率要快于 logN 的任意次幂。

运行时间计算

计算 3次幂之和 的示例代码：

int Sum(int N)
{
         int i, PartialSum;

/* 1 */  PartialSum = 0;
/* 2 */  for (int i=1; i<=N; i++)
/* 3 */    PartialSum += i * i * i;
/* 4 */  return PartialSum;
}

运行时间分析：

1. 声明不计时间；
2. 第 1 行和第 4 行各占一个时间单元；
3. 第 3 行每执行一次占用 4 个时间单元（两次乘法，一次加法，一次赋值），而执行 N 次共占用 4N 个时间单元；
4. 第 2 行在初始化 i, 测试 i<= N 和对 i 的自增运算中隐含着开销（初始化1个时间单元，所有的测试 N+1 个时间单元，以及所有的自增运算 N 个时间单元，共2N+2）。

我们忽略调用函数和返回值的开销，得到总量是6N+4，因此我们说该函数是 O(N).

计算运行时间的一般法则

• for 循环
  一次 for 循环的运行时间至多是该 for 循环内语句（包括测试语句）的运行时间乘以迭代次数。

• 嵌套的 for 循环
  从里向外分析。一组嵌套内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的 for 循环的大小的乘积。例如：

for (i=0; i<N; i++)
    for (j=0; j<N; j++)
      k++;

该程序片段为 O(N^2).

• 顺序语句
  将各个语句的运行时间求和即可（即，其中的最大值）。例如，下述程序片段先用去 O(N), 再花费 O(N^2), 总开销也是 O(N^2).

for (i=0; i<N; i++)
    a[i] = 0;
for (i=0; i<N; i++)
    for (j=0; j<N; j++)
      a[i] += a[j] + i + j;

• if/else 语句
  对程序片段

if (condition)
    S1
else
    S2

一个 if/else 语句的运行时间不超过判断再加上 S1 和 S2 中运行时间长者的总运行时间。

《数据结构与算法分析》