没有合适的资源?快使用搜索试试~ 我知道了~
首页C++中实用算法详解:提升编程效率的关键
C++中实用算法详解:提升编程效率的关键
![](https://csdnimg.cn/release/wenkucmsfe/public/img/star.98a08eaa.png)
"《C++中的算法详解》是一本深入讲解C++编程中实用算法的指南,对提高程序员的技能大有裨益。该书不仅涵盖了基础概念,还探讨了算法设计与分析的核心原则。作者从第一章的算法介绍入手,通过实例——如连通性问题,引导读者理解并应用Union-Find算法。接着,第二章深入剖析算法分析方法,包括实施与经验分析、算法性能评估以及函数增长与Big-O表示法。 在算法分析部分,书中重点讨论了递归程序中常见的三种基本递归关系:一种是递归地将输入减半(例如,快速排序),对应的递推公式解释了这种操作的时间复杂度;另一种是线性扫描输入,随后可能将其分割成两部分(例如,归并排序),公式展示了这种分割过程的影响;最后,一种涉及将输入平分并在子问题上做常量操作的情况(如二分查找)。 每个章节都配以详尽的解决方案和图表,帮助读者直观理解算法的工作原理。此外,书中还提供了课程中的应用场景,强调算法在实际项目中的价值。本书的编写者对编程语言的精通使得内容更加贴近实践,无论是初学者还是进阶开发者,都能从中受益匪浅。通过学习这本书,读者不仅能提升C++编程技巧,还能培养出高效解决问题的能力,为今后的编程生涯打下坚实的基础。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/4947397/bg10.jpg)
Figure 1.6. Example of quick union (not-too-quick find)
This sequence depicts the contents of the id array after each of the pairs at left
are processed by the quick-find algorithm (Program 1.1). Shaded entries are those
that change for the union operation (just one per operation). When we process the
pair p q, we follow pointers from p to get an entry i with id[i] == i; then,
we follow pointers from q to get an entry j with id[j] == j; then, if i and j
differ, we set id[i] = id[j]. For the find operation for the pair 5-8 (final
line), i takes on the values 5 6 9 0 1, and j takes on the values 8 0 1.
Part One: Fundamentals 11
Part One: Fundamentals 11
![](https://csdnimg.cn/release/download_crawler_static/4947397/bg11.jpg)
The connected components depicted in Figure 1.5 are called trees; they are
fundamental combinatorial structures that we shall encounter on numerous
occasions throughout the book. We shall consider the properties of trees in detail
in Chapter 5. For the union and find operations, the trees in Figure 1.5 are useful
because they are quick to build and have the property that two objects are
connected in the tree if and only if the objects are connected in the input. By
moving up the tree, we can easily find the root of the tree containing each object,
so we have a way to find whether or not they are connected. Each tree has
precisely one object that points to itself, which is called the root of the tree. The
self-pointer is not shown in the diagrams. When we start at any object in the tree,
move to the object to which it points, then move to the object to which that object
points, and so forth, we eventually end up at the root, always. We can prove this
property to be true by induction: It is true after the array is initialized to have
every object point to itself, and if it is true before a given union operation, it is
certainly true afterward.
The diagrams in Figure 1.4 for the quick-find algorithm have the same properties
as those described in the previous paragraph. The difference between the two is
that we reach the root from all the nodes in the quick-find trees after following
just one link, whereas we might need to follow several links to get to the root in a
quick-union tree.
Program 1.2. Quick-union solution to connectivity problem
If we replace the body of the while loop in Program 1.1 by this code,
we have a program that meets the same specifications as Program 1.1,
but does less computation for the union operation at the expense of
more computation for the find operation. The for loops and
subsequent if statement in this code specify the necessary and
sufficient conditions on the id array for p and q to be connected. The
assignment statement id[i] = j implements the union operation.
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
12 Part One: Fundamentals
12 Part One: Fundamentals
![](https://csdnimg.cn/release/download_crawler_static/4947397/bg12.jpg)
if (i == j) continue;
id[i] = j;
cout << " " << p << " " << q << endl;
Program 1.2 is an implementation of the union and find operations that comprise
the quick-union algorithm to solve the connectivity problem. The quick-union
algorithm would seem to be faster than the quick-find algorithm, because it does
not have to go through the entire array for each input pair; but how much faster is
it? This question is more difficult to answer here than it was for quick find,
because the running time is much more dependent on the nature of the input. By
running empirical studies or doing mathematical analysis (see Chapter 2), we can
convince ourselves that Program 1.2 is far more efficient than Program 1.1, and
that it is feasible to consider using Program 1.2 for huge practical problems. We
shall discuss one such empirical study at the end of this section. For the moment,
we can regard quick union as an improvement because it removes quick find's
main liability (that the program requires at least NM instructions to process M
union operations among N objects).
This difference between quick union and quick find certainly represents an
improvement, but quick union still has the liability that we cannot guarantee it to
be substantially faster than quick find in every case, because the input data could
conspire to make the find operation slow.
Property 1.2. For M > N, the quick-union algorithm could take more than MN/2
instructions to solve a connectivity problem with M pairs of N objects
Suppose that the input pairs come in the order 1-2, then 2-3, then
3-4, and so forth. After N – 1 such pairs, we have N objects all in the
same set, and the tree that is formed by the quick-union algorithm is a
straight line, with N pointing to N – 1, which points to N – 2, which
points to N – 3, and so forth. To execute the find operation for object
N, the program has to follow N – 1 pointers. Thus, the average number
of pointers followed for the first N pairs is
(0 + 1 + ... + (N – 1))/N = (N – 1)/2.
Now suppose that the remainder of the pairs all connect N to some
other object. The find operation for each of these pairs involves at least
(N – 1) pointers. The grand total for the M find operations for this
sequence of input pairs is certainly greater than MN/2.
Fortunately, there is an easy modification to the algorithm that allows us to
guarantee that bad cases such as this one do not occur. Rather than arbitrarily
connecting the second tree to the first for union, we keep track of the number of
nodes in each tree and always connect the smaller tree to the larger. This change
requires slightly more code and another array to hold the node counts, as shown
in Program 1.3, but it leads to substantial improvements in efficiency. We refer to
this algorithm as the weighted quick-union algorithm.
Figure 1.7 shows the forest of trees constructed by the weighted union–find
algorithm for the example input in Figure 1.1. Even for this small example, the
Part One: Fundamentals 13
Part One: Fundamentals 13
![](https://csdnimg.cn/release/download_crawler_static/4947397/bg13.jpg)
paths in the trees are substantially shorter than for the unweighted version in
Figure 1.5. Figure 1.8 illustrates what happens in the worst case, when the sizes
of the sets to be merged in the union operation are always equal (and a power of
2). These tree structures look complex, but they have the simple property that the
maximum number of pointers that we need to follow to get to the root in a tree of
2
n
nodes is n. Furthermore, when we merge two trees of 2
n
nodes, we get a tree of
2
n+1
nodes, and we increase the maximum distance to the root to n+1. This
observation generalizes to provide a proof that the weighted algorithm is
substantially more efficient than the unweighted algorithm.
Figure 1.7. Tree representation of weighted quick union
This sequence depicts the result of changing the quick-union algorithm to link the
root of the smaller of the two trees to the root of the larger of the two trees. The
distance from each node to the root of its tree is small, so the find operation is
efficient.
Figure 1.8. Weighted quick union (worst case)
The worst scenario for the weighted quick-union algorithm is that each union
operation links trees of equal size. If the number of objects is less than 2
n
, the
distance from any node to the root of its tree is less than n.
14 Part One: Fundamentals
14 Part One: Fundamentals
![](https://csdnimg.cn/release/download_crawler_static/4947397/bg14.jpg)
Program 1.3. Weighted version of quick union
This program is a modification to the quick-union algorithm (see
Program 1.2) that keeps an additional array sz for the purpose of
maintaining, for each object with id[i] == i, the number of nodes
in the associated tree, so that the union operation can link the smaller of
the two specified trees to the larger, thus preventing the growth of long
paths in the trees.
#include <iostream.h>
static const int N = 10000;
int main()
{ int i, j, p, q, id[N], sz[N];
for (i = 0; i < N; i++)
{ id[i] = i; sz[i] = 1; }
while (cin >> p >> q)
{
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
if (i == j) continue;
if (sz[i] < sz[j])
{ id[i] = j; sz[j] += sz[i]; }
else { id[j] = i; sz[i] += sz[j]; }
Part One: Fundamentals 15
Part One: Fundamentals 15
剩余652页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
UANGCAOH
- 粉丝: 0
- 资源: 4
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)