问一个百思不得其解得问题，关于数据结构的
如何估算一个算法的“平均”时间和空间复杂度？最好和最坏情况都好办，可是什么才是平均情况？
比如：对一个二叉树进行非递归遍历，需要一个栈空间，这个栈空间平均要多大？
又比如，对一个二叉排序树进行插入，其平均的时间复杂度是多少？
请不吝赐教，谢谢！
问题点数：0、回复次数：4Top
1 楼szm866（雨淡风秋）回复于 2005-01-03 17:19:07 得分 0
没人知道吗？Top
2 楼xunfengxxx（寻风）回复于 2005-01-03 17:30:49 得分 0
这种题目看书吧
书上讲了很详细的
找本高级程序员的书看看Top
3 楼szm866（雨淡风秋）回复于 2005-01-03 17:47:21 得分 0
翻了很多书，仔细看就知道，都是介绍最好或最坏情况的，最难的平均情况都没有讲，即使有提到，也只给出结论，没有具体过程。尤其是我上面提的关于非递归遍历二叉树的栈空间大小的问题。而这样的问题居然在考研试题中出现了，所以不弄明白不行啊Top
4 楼melonliu（I believe I can FLY!!）回复于 2005-01-03 20:46:41 得分 0
找一本算法与数据结构吧，我的书第一章就有公式，有些平均复杂度碰巧会是平均数Top
