| 2.4算法的时间复杂度分析
本算法的外层循环是一个出队列的操作，假设总共出队列的元素数目为M，那么其时间是O(M)，第(4)步是要遍历出队列的左倾堆，需要花费的时间是O(N),在遍历左倾堆时对于其每个节点我们需要判断是否是一个可插入节点，判断插入左孩子的操作时间是O(1),判断插入右孩子的需要沿着右子树向上回溯，根据左倾堆的性质左子树的距离是比右子树距离要大，因此需要花费的时间最多为O(log2N)。如果可插入的话，就需要复制左倾堆，实际上这也是一个遍历二叉树的操作，因此最多需要付出O(N)的时间。插入右孩子需要回溯，并且有可能需要再次复制左倾树故插入节点操作需要时间O(log2N+N)操作故时间复杂度应为O(M*N(log2N+N+(log2N+N))即为O(M*N(log2N+N))
关于M我们来看程序生成的数据：
表1 实验结果
| N |
1 |
2 |
3 |
4 |
5 |
6 |
| X（i） |
1 |
1 |
3 |
9 |
31 |
131 |
| M(i) |
1 |
2 |
5 |
14 |
45 |
176 |
表2 实验结果
| N |
7 |
8 |
9 |
10 |
| X（i） |
691 |
4135 |
27833 |
208463 |
| M(i) |
867 |
5002 |
32835 |
241298 |
M(i)=X(1)+……X(i)(1≤i≤N)，M(i+1)=M(i)+X(i+1)。随着N的增大，大抵上有这样的规律M（i+1）<i*X(i),而且当N比较大时，X(i+1)将远远大于M(i),故当N较大时可以认为M(i+1)=X(i+1)<i*X(i),故当N较大时M(i+1) <i！，因此可知N较大时时间复杂度应小于O(N!(log2N+N))
3 算法实例分析
假设N为3，不妨简单一些我们让3个节点的键值为1，2，3,按照算法生成的树为：
 
      
4 结束语
根据左倾堆的性质提出了一种生成所有左倾堆的算法,算法涉及了有关左倾堆的操作，使用了链队列和链栈，并对算法的时间复杂度进行了详细的分析。
参考文献
[1][美] Mark Allen Wesis 著 张怀勇等译.数据结构与算法分析C++描述（第3版）[M].北京:人民邮电出版，2007
[2]蔡子经 施伯乐.数据结构教程[M].上海：复旦大学出版社，1994
[3]孙强，沈建华，顾君忠.一种生成所有堆的枚举实用算法[J].计算机工程，2002，28（6）：80-82
2/2 首页 上一页 1 2 |
