C++ 数据结构(一)绪论(5)迭代与递归(1)
     发布在:C/C++      浏览:47      评论:0 条评论

上一篇:《C++ 数据结构(一)绪论(4)算法分析》

To iterate is human, to recurse, divine. 迭代乃人工,递归方神通

数组求和:迭代

问题

计算任意 n 个整数之和

实现

逐一取出每个元素,累加之

int sum(int A[], int n)
{
    int sum = 0; // O(1)
    for (int i = 0; i < n; i++) sum += A[i]; // O(n)
    return sum;  // O(1)
}

分析

无论 A[] 内容如何,都有:

$$ T(n) = 1 + n * 1 + 1 = n + 2 = O(n) = \Omega (n) = \Theta (n) $$

减而治之

为求解一个大规模的问题,可以:

1、将其划分为两个子问题:其一 平凡,另一规模 缩减

2、分别求解子问题

3、由子问题的解,得到原问题的解

C++ 数据结构(一)绪论(5)迭代与递归(1)

数组求和:线性递归

sum (int A[], int n)
{
    return (n < 1) ? 0 : sum(A, n - 1) + A[n - 1];
}

递归跟踪分析

1、检查每个递归实例

2、累计所需时间(调用语句本身,计入对应的子实例)

3、其总和即算法执行时间

C++ 数据结构(一)绪论(5)迭代与递归(1)

本例中,单个递归实例自身只需 O(1) 时间,故:

$$ T(n) = O(1) * (n + 1) = O(n) $$

递推方程

从递推的角度看,为求解 sum(A, n),需

递归求解规模为 n - 1 的问题 sum(A, n-1) T(n-1)

再累加上 A[n-1] O(1)

递归基:sum(A, 0) O(1)

$$
递归方程:
\begin{cases}
T(n) = T(n-1) + O(1) \
\
T(0) = O(1)
\end{cases}
=> T(n) = O(1) + n = O(n)
$$

下一篇:《C++ 数据结构(一)绪论(5)迭代与递归(2)》

Responses