常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。

我也知道没有O(n/2)啊

第一个选Ｃ
第二个是Ｏ（Ｎ）／／这个我知道了
第三个３Ｘ２.４５／６－＊＋

麻烦解释其他两个！谢谢！真的不懂！

１．从一棵二叉搜索树中查找一个元素是，其时间复杂度大致为（）
其实很简单,因为每一棵子树做搜索要不往左要不往右.假设一棵二叉树结点个数为n,我们考虑最好的情况,就是尽量做到两棵子树相对平衡(简单点就是两边的结点个数相差不大).这样大致一棵二叉树的高度为Log2(n),这就是要比较的次数.
所以时间复杂度为Log2(n).

３．中缀表达式３＋Ｘ＊（２.４／５－６）所对应的后缀表达式为＿＿．

所谓后缀表达式就是操作符在两个操作数之后(当然也有单目操作运算了).
所以将上面的表达式转换为(3 + (x*((2.4/5)-6)))
这样就比较明朗了每一个括号内就是对应的一个操作数.
因此(3 (x( ( 2.4 5 / ) 6 - ) * ) +)
将括号去掉即可.

晓得毛.

好文章哈！

呵呵~理解复杂度确实是数据结构中一大难点。

１．二叉搜索树不是线索二叉树？
２.那个时间复杂度为Log2(n)，是不是这样算的：因为深度为Ｋ的二叉树至多有２Ｋ－１／／２的Ｋ次方个结点，所以Ｋ＝Log2(n＋１)，即Log2(n)？？
其他的就晓得里！

[此贴子已经被作者于2007-6-21 11:29:23编辑过]

１．二叉搜索树不是线索二叉树？
就是简单的有序二叉树.
第二个算你说对了.

哦!我们老师没讲过!

二叉排序树