C++编程：算法基础与分析

需积分: 11 101 浏览量更新于2024-07-24 1 收藏 11.45MB PDF 举报

"Algorithms in C++, Parts 1-4 是一本经典的编程书籍，涵盖了算法的基础到高级主题，适合学习和教学使用。" 本书是C++编程领域的经典之作，旨在教授如何设计、理解和分析算法，同时深入C++语言的运用。作者通过清晰的解释和实例，引导读者探索算法的世界，提升编程技能。首先，书中的"Part One: Fundamentals"部分，第一章"Introduction"介绍了算法的基本概念。1.1章节阐述了算法的本质，它是一种解决问题或执行任务的步骤序列。通过1.2章的"ASampleProblem: Connectivity"，作者展示了如何用算法解决实际问题，即如何确定图中的连接性。1.3章则详细讲解了"Union–Find Algorithms"，这是一种用于处理集合关系的高效算法。作者在1.4章提供了一个全面的视角，讨论了算法在计算机科学中的重要性和应用范围，并在1.5章对这部分的内容进行了总结。第二章"Principles of Algorithm Analysis"探讨了算法分析的基础。2.1章提到了实现与经验分析的重要性，强调了实际运行时间和理论分析相结合的必要性。2.2章深入到算法分析的领域，解释了如何评估算法的时间复杂度。2.3章开始讨论函数的增长，这是理解算法效率的关键。接着，2.4章引入了大O符号（Big-Oh Notation），它是描述算法时间复杂度的标准工具。2.5章介绍了基本的递归方程及其解法，通过具体的例子，如公式2.2、2.4和2.5，帮助读者理解不同类型的递归程序如何影响算法的性能。书中还包括了各种习题解答，如图2.6展示了整数函数与二进制表示之间的关系，以及多个公式解题过程，帮助读者巩固所学知识。这些解题步骤和分析进一步强化了对算法分析和C++编程技巧的理解。 "Algorithms in C++, Parts 1-4"是一本全面而深入的教程，涵盖了算法设计、分析和C++实现的诸多方面，适合计算机科学学生和专业人士作为参考和学习材料。无论是对算法的初学者还是寻求提升的程序员，这本书都能提供宝贵的指导和洞见。

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

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

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

剩余652页未读，继续阅读

UFOGGUFO

粉丝: 3
资源: 38

C++编程：算法基础与分析

Algorithms in C++, Parts 1-4 (code)

Algorithms in C++, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching

algorithms in c++pdf

most graph algorithms that take an adjacency-matrix representation as input

链表的研究意义和发展，并引用参考文献

In Defense of Color-based Model-free Tracking

遗传算法python实例代码

最新资源