二叉树编程 先序建立 中序遍历

理论分析
数据结构的基础知识中重要的一点就是能否根据两种不同遍历序列的组合（有三种：先序+中序，先序+后序，中序+后序），唯一的确定一棵二叉树。然后就是根据二叉树的不同遍历序列（先序、中序、后序），重构二叉树。显然，这三种组合并不是都能唯一确定二叉树的，其中先序+后序就不能唯一确定一棵二叉树，下面是关于该问题的证明与结论。
①给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。
证明：因为先序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（假设有L个元素）表示左子树，若左边无元素，则说明左子树为空；右边（假设有R个元素）是右子树，若为空，则右子树为空。根据前序遍历中"根-左子树-右子树"的顺序，则由从先序序列的第二元素开始的L个结点序列和中序序列根左边的L个结点序列构造左子树，由先序序列最后R个元素序列与中序序列根右边的R个元素序列构造右子树。
②由中序序列和先序序列能唯一确定一棵二叉树，但是由先序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。
反例：任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。
这两棵二叉树的先序遍历序列都为2-1-3，后序遍历序列都为3-1-2。但是显然它们是不同的二叉树，所以根据先序序列和后序序列并不能唯一确定二叉树。
③已经说明由二叉树的先序序列和中序序列可以确定一棵二叉树，现在来证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
证明：
当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当n=m-1时结论成立，即结点数目为m-1时，中序序列和后序序列可以唯一确定二叉树。现证明当n=m时结论成立。
设中序序列为S1,S2,…,Sm,后序序列是P1,P2,…,Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1,S2,…,Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2,S3,…,Sm}和{P1,P2,…,Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m，则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1,S2,…,Sm-1}和{P1,P2,…,Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1<i<m时，Si把中序序列分成{S1,S2,…,Si-1}和{Si+1,Si+2,…,Sm}。由于后序遍历是"左子树-右子树-根结点"，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1,S2,…,Si-1}和{P1,P2,…,Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,…,Sm}和{Pi,Pi+1,…,Pm-1}可唯一确定二叉树的右子树。

3、构造思路
1）根据先序遍历序列和中序遍历序列构建二叉树
假定已知二叉树如下：
___7___
/ \
10 2
/ \ /
4 3 8
\ /
1 11
那么它的先序遍历和中序遍历的结果如下：
preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}
需要关注的几个要点：
1）先序遍历的第一个结点总是根结点。如上图中的二叉树，根结点为7，也是先序遍历的第一个值。先序遍历时父亲结点总是在孩子结点之前遍历。
2）可以观察到在中序遍历中，7是第4个值（从0开始算起）。由于中序遍历顺序为：左子树，根结点，右子树。所以7左边的{4,10,3,1} 这四个结点属于左子树，而根结点7右边的{11,8,2}属于右子树。
3）可以从上面的结论很轻松的得到递归式。在构建了根结点7后，我们可以根据中序遍历{4, 10, 3, 1} 和{11,8,2}分别构建它的左子树和右子树。我们同时需要相应的先序遍历结果用于发现规律。我们可以由先序遍历知道左右子树的先序遍历分别是{10，4, 3, 1}和{2， 8， 11}。左右子树也分别为二叉树，由此可以递归来解决问题。
4）关于如何得到根结点在中序遍历中的位置问题还没有细讲，如果使用线性扫描查找位置，则每次查找需要O（N）的时间，如果二叉树平衡的话，则整个算法需要O（NlgN）的时间。如果二叉树不平衡，则最坏情况需要O（N^2）时间。为了提高效率，我们可以考虑使用哈希表来存储与查找根结点在中序遍历中的位置，每次查找只需要O（1）的时间，这样构建整棵树只需要O（N）的时间。 这里为了方便，只是用了一个数组用于标记位置，要是用哈希表也会很方便。需要注意的是，这里的二叉树结点值不能有相同的值。
代码：
// 输入：先序和中序的第一个指针和最后一个指针，
// 递归调用，每次确定当前结点
BinaryTreeNode ConstructCore(int startPerorder, int endPreorder, int startInorder, int endInorder)
{
//先序第一个为根节点
int rootValue = startPerorder[0];
BinaryTreeNode root = new BinaryTreeNode;
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;

//递归退出条件
if ( startPerorder==endPreorder )
{
if ( startInorder==endInorder && startPerorder==endInorder )
return root;
else
throw std::exception("Invalid input"); //异常处理
}

// 在中序遍历中找到根节点的值
int rootInorder = startInorder;
while(rootInorder<=endInorder && rootInorder!=rootValue)
++rootInorder;

//异常处理
if ( rootInorder==endInorder && rootInorder!=rootValue)
throw std::exception("Invalid input");

int leftLength = rootInorder - startInorder;
int leftPreorderEnd = startPerorder+leftLength;
if ( leftLength > 0 )
{
//构建左子树
root->m_pLeft=ConstructCore(startPerorder+1,leftPreorderEnd,startInorder, rootInorder-1);
}
if ( leftLength < endPreorder-startPerorder )
{
//构建右子树
root->m_pRight= ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
}

return root;
}

//根据先序和中序构建二叉树
BinaryTreeNode Construct(int preorder, int inorder, int length)
{
if(preorder==NULL || inorder==NULL || length <=0)
return NULL;

return ConstructCore(preorder, preorder+length-1, inorder,inorder+length-1);
}

void TraverseTreePostorder(BinaryTreeNode proot)
{
if ( proot == NULL )
return;

if ( proot->m_pLeft != NULL )
TraverseTreePostorder(proot->m_pLeft);
if ( proot->m_pRight != NULL )
TraverseTreePostorder(proot->m_pRight);

cout << proot->m_nValue << " ";
}
主函数测试代码：
int main()
{
int preorder[] = {7,10,4,3,1,2,8,11};
int inorder[] = {4,10,3,1,7,11,8,2};

BinaryTreeNode pRoot = Construct(preorder,inorder,8);

TraverseTreePostorder(pRoot);
cout <<endl;

return 0;
}
2）根据中序遍历序列和后序序遍历序列构建二叉树
原理和上述原理基本一致，任然沿用上述例子
___7___
/ \
10 2
/ \ /
4 3 8
\ /
1 11
那么它的中序遍历和后序序遍历的结果如下：
inorder = {4,10,3,1,7,11,8,2}
postorder = {7,10,4,3,1,2,8,11}
代码：
// 输入：中序和后序的第一个指针和最后一个指针，
// 递归调用，每次确定当前结点
BinaryTreeNode ConstructCore_in_post(int startInorder, int endInorder, int startPostorder, int endPostorder)
{
//后序最后一个结点为根结点
int rootValue = endPostorder;
BinaryTreeNode root = new BinaryTreeNode;
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;

//递归退出条件
if ( startInorder==endInorder )
{
if ( startPostorder==endPostorder && startInorder==endPostorder )
return root;
else
throw std::exception("Invalid input"); //异常处理
}

//在中序中找到当前根节点
int rootInorder = startInorder;
while(rootInorder<=endInorder && rootInorder != rootValue )
++rootInorder;

int leftLength = rootInorder - startInorder;
int leftInorderEnd = startInorder+leftLength-1;
if ( leftLength > 0 )
{
//构建左子树
root->m_pLeft=ConstructCore_in_post(startInorder,leftInorderEnd,startPostorder, startPostorder+leftLength-1);
}
if ( leftLength < endInorder-startInorder )
{
//构建右子树
root->m_pRight= ConstructCore_in_post(rootInorder+1,endInorder,startPostorder+leftLength,endPostorder-1);
}

return root;
}

//根据先序和中序构建二叉树
BinaryTreeNode Construct(int inorder, int postorder, int length)
{
if(inorder==NULL || postorder==NULL || length <=0)
return NULL;

return ConstructCore_in_post(inorder, inorder+length-1, postorder, postorder+length-1);
}

void TraverseTreePreorder(BinaryTreeNode proot)
{
if ( proot == NULL )
return;
cout << proot->m_nValue << " ";

if ( proot->m_pLeft != NULL )
TraverseTreePreorder(proot->m_pLeft);
if ( proot->m_pRight != NULL )
TraverseTreePreorder(proot->m_pRight);
}
主函数测试：
int main()
{
int inorder[] = {4,10,3,1,7,11,8,2};
int postorder[] = {4,1,3,10,11,8,2,7};

BinaryTreeNode pRoot = Construct(inorder,postorder,8);

TraverseTreePreorder(pRoot);
cout <<endl;

return 0;
}

这几个的确句型有些长,翻译习惯也可以参照一下别人的,反正今天好象回答你的人好多
-------------------------------
overview
The order of growth of the running time of an algorithm, defined in Chapter 2, gives a simple
characterization of the algorithm's efficiency and also allows us to compare the relative
performance of alternative algorithms Once the input size n becomes large enough, merge
sort, with its Θ(n lg n) worst-case running time, beats insertion sort, whose worst-case running
time is Θ(n2) Although we can sometimes determine the exact running time of an algorithm,
as we did for insertion sort in Chapter 2, the extra precision is not usually worth the effort of
computing it For large enough inputs, the multiplicative constants and lower-order terms of
an exact running time are dominated by the effects of the input size itself
When we look at input sizes large enough to make only the order of growth of the running
time relevant, we are studying the asymptotic efficiency of algorithms That is, we are
concerned with how the running time of an algorithm increases with the size of the input in
the limit, as the size of the input increases without bound Usually, an algorithm that is
asymptotically more efficient will be the best choice for all but very small inputs
概要
算法运行时间的成长次序, 被定义在第二章里, 给算法的特性一个简单的描述并允许我们把它与供选择的算法进行比较。一旦输入大小n变得足够大, 合并排序法, 以Θ(nlgn) 最差运行时间,来检验最差运行时间是Θ(n2)的插入排序。虽然我们有时能确定算法确切的运行时间, 但如同在第二章里我们为了插入排序,而努力计算额外精确度通常并没有价值。为了足够大的投入, 常数和一具体运行时间的低秩序期限的积由投入规模本身所控制
当投入规模大到足够确定相关命令运行时间的情况下, 我们应该学习渐进效率算法。即，当输入大小的增加没有限制，我们就要考虑怎样计算运行时间的增长变化，就像输入大小有限制的时候那样。通常, 除了非常小的输入，渐进算法是更加高效率的算法，将是最佳的选择。
This chapter gives several standard methods for simplifying the asymptotic analysis of
algorithms The next section begins by defining several types of "asymptotic notation," of
which we have already seen an example in Θ-notation Several notational conventions used
throughout this book are then presented, and finally we review the behavior of functions that
commonly arise in the analysis of algorithms
本章讲述了算法渐进分析的几种简化方法。下一部分将首先定义几种“渐进符号”，在这些符号中我们已经见过的如Θ符号。还将给出本书中通篇出现的几种符号约定。最后我们将重温一下出现在算法分析中的常用函数的特性。
31 Asymptotic notation The notations we use to describe the asymptotic running time of an algorithm are defined in
terms of functions whose domains are the set of natural numbers N = {0, 1, 2, }
Such notations are convenient for describing the worst-case running-time function T (n), which is
usually defined only on integer input sizes
It is sometimes convenient, however, to abuse asymptotic notation in a variety of ways
For example, the notation is easily extended to the domain of real numbers or, alternatively, restricted to a subset of the natural numbers It is important, however, to understand the precise meaning of the notation so that when it is
abused, it is not misused This section defines the basic asymptotic notations and also
introduces some common abuses
31 渐进法
我们用来描述连续运行时间算法的一种记数法，其定义是：函数项的域值为自然数N={0，1，2，…}。
这种记数法在描述最简单的连续时间函数T(n)是方便的，因为它的输入范围通常仅取整数。它有时是方便的，然而，我们需要用比较多的方式来描述不规则渐进记法。例如，记法很容易在实数域内取值，或者交替地限定在自然数的一个子集内。尽管记数法重要，但我们需要了解其精确涵义，以便函数不规则时它没有被误用。本节定义了基本的渐进记法并且介绍一些一般的不规则函数。

超时说明你用的方法不够好。
其实很多问题都可以用暴力方法解决，只不过所需要的时间实在是太长或者空间太大，人们不得不想出各种算法来解决这些问题，这也是算法的意义。刷leetcode最主要还是学习里面的方法，不是单纯的得到答案。一般情况下普通的问题时间复杂度超过O(N^2)的话，基本都会超时的，你应该多学习一下算法和数据结构，能优化的问题尽量把时间复杂度尽量控制在O(NlgN)以内，没有特殊要求的问题一般都可以过。

打你屁股，这么简单的问题都不认真研究一下。
冒泡排序是最慢的排序，时间复杂度是 O(n^2)。
快速排序是最快的排序。关于快速排序，我推荐你看看《代码之美》第二章：我编写过的最漂亮的代码。作者所说的最漂亮，就是指效率最高的。
--------------------------------摘自《代码之美》---------------
当我撰写关于分治（divide-and-conquer）算法的论文时，我发现CAR Hoare的Quicksort算法（“Quicksort”，Computer Journal 5）无疑是各种Quicksort算法的鼻祖。这是一种解决基本问题的漂亮算法，可以用优雅的代码实现。我很喜欢这个算法，但我总是无法弄明白算法中最内层的循环。我曾经花两天的时间来调试一个使用了这个循环的复杂程序，并且几年以来，当我需要完成类似的任务时，我会很小心地复制这段代码。虽然这段代码能够解决我所遇到的问题，但我却并没有真正地理解它。
我后来从Nico Lomuto那里学到了一种优雅的划分（partitioning）模式，并且最终编写出了我能够理解，甚至能够证明的Quicksort算法。William Strunk Jr针对英语所提出的“良好的写作风格即为简练”这条经验同样适用于代码的编写，因此我遵循了他的建议，“省略不必要的字词”（来自《The Elements of Style》一书）。我最终将大约40行左右的代码缩减为十几行的代码。因此，如果要回答“你曾编写过的最漂亮代码是什么？”这个问题，那么我的答案就是：在我编写的《Programming Pearls, Second Edition》(Addison-Wesley)一书中给出的Quichsort算法。在示例2-1中给出了用C语言编写的Quicksort函数。我们在接下来的章节中将进一步地研究和改善这个函数。
示例 2-1 Quicksort函数
void quicksort(int l, int u)
{ int i, m;
if (l >= u) return; 10
swap(l, randint(l, u));
m = l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
如果函数的调用形式是quicksort(0, n-1)，那么这段代码将对一个全局数组x[n]进行排序。函数的两个参数分别是将要进行排序的子数组的下标：l是较低的下标，而u是较高的下标。函数调用swap(i,j)将会交换x[i]与x[j]这两个元素。第一次交换 *** 作将会按照均匀分布的方式在l和u之间随机地选择一个划分元素。
在《Programming Pearls》一书中包含了对Quicksort算法的详细推导以及正确性证明。在本章的剩余内容中，我将假设读者熟悉在《Programming Pearls》中所给出的Quicksort算法以及在大多数初级算法教科书中所给出的Quicksort算法。
如果你把问题改为“在你编写那些广为应用的代码中，哪一段代码是最漂亮的？”我的答案还是Quicksort算法。在我和M D McIlroy一起编写的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol 23, No 11）中指出了在原来Unix qsort函数中的一个严重的性能问题。随后，我们开始用C语言编写一个新排序函数库，并且考虑了许多不同的算法，包括合并排序（Merge Sort）和堆排序（Heap Sort）等算法。在比较了Quicksort的几种实现方案后，我们着手创建自己的Quicksort算法。在这篇文章中描述了我们如何设计出一个比这个算法的其他实现要更为清晰，速度更快以及更为健壮的新函数——部分原因是由于这个函数的代码更为短小。Gordon Bell的名言被证明是正确的：“在计算机系统中，那些最廉价，速度最快以及最为可靠的组件是不存在的。”现在，这个函数已经被使用了10多年的时间，并且没有出现任何故障。
考虑到通过缩减代码量所得到的好处，我最后以第三种方式来问自己在本章之初提出的问题。“你没有编写过的最漂亮代码是什么？”。我如何使用非常少的代码来实现大量的功能？答案还是和Quicksort有关，特别是对这个算法的性能分析。我将在下一节给出详细介绍。
22 事倍功半
Quicksort是一种优雅的算法，这一点有助于对这个算法进行细致的分析。大约在1980年左右，我与Tony Hoare曾经讨论过Quicksort算法的历史。他告诉我，当他最初开发出Quicksort时，他认为这种算法太简单了，不值得发表，而且直到能够分析出这种算法的预期运行时间之后，他才写出了经典的“Quicksoft”论文。
我们很容易看出，在最坏的情况下，Quicksort可能需要n2的时间来对数组元素进行排序。而在最优的情况下，它将选择中值作为划分元素，因此只需nlgn次的比较就可以完成对数组的排序。那么，对于n个不同值的随机数组来说，这个算法平均将进行多少次比较？
Hoare对于这个问题的分析非常漂亮，但不幸的是，其中所使用的数学知识超出了大多数程序员的理解范围。当我为本科生讲授Quicksort算法时，许多学生即使在费了很大的努力之后，还是无法理解其中的证明过程，这令我非常沮丧。下面，我们将从Hoare的程序开
11
始讨论，并且最后将给出一个与他的证明很接近的分析。
我们的任务是对示例2-1中的Quicksort代码进行修改，以分析在对元素值均不相同的数组进行排序时平均需要进行多少次比较。我们还将努力通过最短的代码、最短运行时间以及最小存储空间来得到最深的理解。
为了确定平均比较的次数，我们首先对程序进行修改以统计次数。因此，在内部循环进行比较之前，我们将增加变量comps的值（参见示例2-2）。
示例2-2 修改Quicksort的内部循环以统计比较次数。
for (i = l+1; i <= u; i++) {
comps++;
if (x[i] < x[l])
swap(++m, i);
}
如果用一个值n来运行程序，我们将会看到在程序的运行过程中总共进行了多少次比较。如果重复用n来运行程序，并且用统计的方法来分析结果，我们将得到Quicksort在对n个元素进行排序时平均使用了14 nlgn次的比较。
在理解程序的行为上，这是一种不错的方法。通过十三行的代码和一些实验可以反应出许多问题。这里，我们引用作家Blaise Pascal和T S Eliot的话，“如果我有更多的时间，那么我给你写的信就会更短。”现在，我们有充足的时间，因此就让我们来对代码进行修改，并且努力编写出更短（同时更好）的程序。
我们要做的事情就是提高这个算法的速度，并且尽量增加统计的精确度以及对程序的理解。由于内部循环总是会执行u-l次比较，因此我们可以通过在循环外部增加一个简单的 *** 作来统计比较次数，这就可以使程序运行得更快一些。在示例2-3的Quicksort算法中给出了这个修改。
示例2-3 Quicksort的内部循环，将递增 *** 作移到循环的外部
comps += u-l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
这个程序会对一个数组进行排序，同时统计比较的次数。不过，如果我们的目标只是统计比较的次数，那么就不需要对数组进行实际地排序。在示例2-4中去掉了对元素进行排序的“实际 *** 作”，而只是保留了程序中各种函数调用的“框架”。
示例2-4将Quicksort算法的框架缩减为只进行统计
void quickcount(int l, int u)
{ int m;
if (l >= u) return;
m = randint(l, u);
comps += u-l;
quickcount(l, m-1);
quickcount(m+1, u);
}
12
这个程序能够实现我们的需求，因为Quichsort在选择划分元素时采用的是“随机”方式，并且我们假设所有的元素都是不相等的。现在，这个新程序的运行时间与n成正比，并且相对于示例2-3需要的存储空间与n成正比来说，现在所需的存储空间缩减为递归堆栈的大小，即存储空间的平均大小与lgn成正比。
虽然在实际的程序中，数组的下标（l和u）是非常重要的，但在这个框架版本中并不重要。因此，我们可以用一个表示子数组大小的整数(n)来替代这两个下标（参见示例2-5）
示例2-5 在Quicksort代码框架中使用一个表示子数组大小的参数
void qc(int n)
{ int m;
if (n <= 1) return;
m = randint(1, n);
comps += n-1;
qc(m-1);
qc(n-m);
}
现在，我们可以很自然地把这个过程整理为一个统计比较次数的函数，这个函数将返回在随机Quicksort算法中的比较次数。在示例2-6中给出了这个函数。
示例2-6 将Quicksort框架实现为一个函数
int cc(int n)
{ int m;
if (n <= 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
在示例2-4、示例2-5和示例2-6中解决的都是相同的基本问题，并且所需的都是相同的运行时间和存储空间。在后面的每个示例都对这些函数的形式进行了改进，从而比这些函数更为清晰和简洁。
在定义发明家的矛盾（inventor's paradox）(How To Solve It, Princeton University Press)时，George Póllya指出“计划越宏大，成功的可能性就越大。”现在，我们就来研究在分析Quicksort时的矛盾。到目前为止，我们遇到的问题是，“当Quicksort对大小为n的数组进行一次排序时，需要进行多少次比较？”我们现在将对这个问题进行扩展，“对于大小为n的随机数组来说，Quichsort算法平均需要进行多少次的比较？”我们通过对示例2-6进行扩展以引出示例2-7。
示例2-7 伪码：Quicksort的平均比较次数
float c(int n)
if (n <= 1) return 0
sum = 0
for (m = 1; m <= n; m++)
sum += n-1 + c(m-1) + c(n-m)
return sum/n
如果在输入的数组中最多只有一个元素，那么Quichsort将不会进行比较，如示例2-6
13
中所示。对于更大的n，这段代码将考虑每个划分值m（从第一个元素到最后一个，每个都是等可能的）并且确定在这个元素的位置上进行划分的运行开销。然后，这段代码将统计这些开销的总和（这样就递归地解决了一个大小为m-1的问题和一个大小为n-m的问题），然后将总和除以n得到平均值并返回这个结果。
如果我们能够计算这个数值，那么将使我们实验的功能更加强大。我们现在无需对一个n值运行多次来估计平均值，而只需一个简单的实验便可以得到真实的平均值。不幸的是，实现这个功能是要付出代价的：这个程序的运行时间正比于3n（如果是自行参考（self-referential）的，那么用本章中给出的技术来分析运行时间将是一个很有趣的练习）。
示例2-7中的代码需要一定的时间开销，因为它重复计算了中间结果。当在程序中出现这种情况时，我们通常会使用动态编程来存储中间结果，从而避免重复计算。因此，我们将定义一个表t[N+1]，其中在t[n]中存储c[n]，并且按照升序来计算它的值。我们将用N来表示n的最大值，也就是进行排序的数组的大小。在示例2-8中给出了修改后的代码。
示例2-8 在Quicksort中使用动态编程来计算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += n-1 + t[i-1] + t[n-i]
t[n] = sum/n
这个程序只对示例2-7进行了细微的修改，即用t[n]来替换c(n)。它的运行时间将正比于N2，并且所需的存储空间正比于N。这个程序的优点之一就是：在程序执行结束时，数组t中将包含数组中从元素0到元素N的真实平均值（而不是样本均值的估计）。我们可以对这些值进行分析，从而生成在Quichsort算法中统计比较次数的计算公式。
我们现在来对程序做进一步的简化。第一步就是把n-1移到循环的外面，如示例2-9所示。
示例2-9 在Quicksort中把代码移到循环外面来计算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += t[i-1] + t[n-i]
t[n] = n-1 + sum/n
现在将利用对称性来对循环做进一步的调整。例如，当n为4时，内部循环计算总和为：
t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0]
在上面这些组对中，第一个元素增加而第二个元素减少。因此，我们可以把总和改写为：
2 (t[0] + t[1] + t[2] + t[3])
我们可以利用这种对称性来得到示例2-10中的Quicksort。
示例2-10 在Quichsort中利用了对称性来计算
t[0] = 0
14
for (n = 1; n <= N; n++)
sum = 0
for (i = 0; i < n; i++)
sum += 2 t[i]
t[n] = n-1 + sum/n
然而，在这段代码的运行时间中同样存在着浪费，因为它重复地计算了相同的总和。此时，我们不是把前面所有的元素加在一起，而是在循环外部初始化总和并且加上下一个元素，如示例2-11所示。
示例2-11 在Quicksort中删除了内部循环来计算
sum = 0; t[0] = 0
for (n = 1; n <= N; n++)
sum += 2t[n-1]
t[n] = n-1 + sum/n
这个小程序确实很有用。程序的运行时间与N成正比，对于每个从1到N的整数，程序将生成一张Quicksort的估计运行时间表。
我们可以很容易地把示例2-11用表格来实现，其中的值可以立即用于进一步的分析。在2-1给出了最初的结果行。
表2-1 示例2-11中实现的表格输出
N Sum t[n]
0 0 0
1 0 0
2 0 1
3 2 2667
4 7333 4833
5 17 74
6 318 103
7 524 13486
8 79371 16921
这张表中的第一行数字是用代码中的三个常量来进行初始化的。下一行（输出的第三行）的数值是通过以下公式来计算的：
A3 = A2+1 B3 = B2 + 2C2 C3 = A2-1 + B3/A3
把这些（相应的）公式记录下来就使得这张表格变得完整了。这张表格是“我曾经编写的最漂亮代码”的很好的证据，即使用少量的代码完成大量的工作。
但是，如果我们不需要所有的值，那么情况将会是什么样？如果我们更希望通过这种来方式分析一部分数值（例如，在20到232之间所有2的指数值）呢？虽然在示例2-11中构建了完整的表格t，但它只需要使用表格中的最新值。因此，我们可以用变量t的定长空间来替代table t[]的线性空间，如示例2-12所示。
示例2-12 Quicksoft 计算——最终版本
sum = 0; t = 0
15
for (n = 1; n <= N; n++)
sum += 2t
t = n-1 + sum/n
然后，我们可以插入一行代码来测试n的适应性，并且在必要时输出这些结果。
这个程序是我们漫长学习旅途的终点。通过本章所采用的方式，我们可以证明Alan Perlis的经验是正确的：“简单性并不是在复杂性之前，而是在复杂性之后” ("Epigrams on Programming," Sigplan Notices, Vol 17, Issue 9)。

什么是NP问题
概念1:
在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题，称之为NP类问题。
概念2:
多项式时间（Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。
以数学描述的话，则可说m(n) = O(n)，此n为一常数值（依问题而定）
拿推销员旅行问题为例，假设推销员亨利有向6个城市推销公司产品的任务，并规定了一个旅行预算。他手中有一张航班票价表，他要从A城开始走遍图中的6个城市后返回A城，并且不超出预算，请你帮他找出应走的路线。如果给出的预算宽裕，则任务很简单；如果预算比较紧张，你就得认真设计路线了。你得考虑每一种可能的次序，以使旅费最少。
而NP问题中最困难的问题称之为NP完全问题(NP-complete)，已经证明的包括：电话网络的最优几何设计、格子棋的最佳走法。根据库克定理，任意一个NP完全问题如果能够在多项式时间内解决，则所有的NP问题都能在多项式时间内解决，而至今这一问题仍无答案。
什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。
这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间（多项式时间： 运行时间最多是输入量的多项式函数）内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。
完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。
解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。
前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好象是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。
什么叫做NP问题，什么叫做NPC问题
首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质。比如对于排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O(n^2)，快速排序平均情况下是O(nlgn)等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。
为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A到B是否有长度为1的路径？从A到B是否有长度为2的路径？。。。从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。
如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。
然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP这个问题至今还未解决。注意，NP问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，你能说他很难解么？ 刚才说了，现在还不知道是否有P=NP或者P<>NP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信P<>NP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。
类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是难解的问题。
NP中的某些问题的复杂性与整个类的复杂性相关联这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的这些问题被称为NP-完全问题(NPC问题)
判定方法:一个判定性问题，满足：(1)∏∈NP(2)对任意一个∏’∝poly∏ (注:poly为规约符号)则问题∏称为NP-完全的(NP-complete，NPC)；如果问题∏仅满足条件(2)而不满足条件(1)，则问题NP称为NP-难的(NP-hard)。
总结来说:
P类:已有多项式时间算法的判定问题
NP类:已有指数时间算法的判定问题,包括P类
NPC类:是NP的一个子集,且其中每一个问题均能由NP中的任何问题在多项式时间内转化成
NPH问题:若问题A不属于NP类,已知某一NPC问题可在多项式时间内转化为问题A,则称A为NPH

---