而传统的 TDIDT 决策树（Top-Down Induction of Decision Trees，包括 ID3 和 C4.5 算法）其训练复杂度为, 其中, 而是第个特征的取值个数。显然，该类算法的算法复杂度与特征个数是超线性关系。在一般情况下，所以随机决策树算法的计算复杂度是远小于这类算法的。
精度和效率前面简单介绍了随机决策树算法的实现和训练复杂度，这一节将简要介绍下其精度和训练效率，并与其他经典算法进行比较。
一个简单例子
该例子引自范伟博士的网站：有一二维的人造正负样本分布，如图 1 所示。其中红色为正样本，绿色为负样本。显然这个问题不是线性可分的，
图 1. 二维人造正负样本分布
下面图 2—图 5 分别给出随机决策树算法、决策树，线性 SVM 和 RBF 核的 SVM 算法的训练结果。
图 2. 随机决策树（训练时间 5 秒）
显然，随机决策树对原分布的估计是较好的，与 RBF SVM 的效果在同一水平上。而决策树算法则带来了明显的锯齿型边界，而线性 SVM 则无法将右上方的正样本正确划分。从训练时间看，SVM 开销非常大（可能未使用 SMO 方法），树的算法都很快。但是随机决策树算法的训练开销比决策树要高 5 倍，与我们前面的分析相反。这有两个原因，一是对于低维度问题，随机决策树算法的效率与决策树相比并没有明显优势。因为决策树算法的时间复杂度与特征数量的关系是超线性的，在特征较少时，其复杂度并不会太高，而随着特征的增长，计算复杂度会快速增长。二是这个实验是使用的随机决策树的原始实现，其效率并不是太高。
Dice 测试结果
我们从 Libsvm 选取了 9 个二分类数据集，这些数据集的统计信息列在表 1 中。
表 1. 从 Libsvm 选取的 9 个二分类数据集的统计信息Name Feature Type Feature Number Train Data Number Test Data Number Train Data Size Test Data Size
a1a Binary 123 1,605 30,956 0.11M 2.11M
a9a Binary 123 32,561 16,281 2.22M 3.33M
mushrooms Binary 112 7,124 1,000 0.753M 0.105M
w1a Binary 300 2,477 47,272 0.166M 3.15M
w8a Binary 300 49,749 14,951 3.31M 1.00M
splice Categorical 60 1,000 2,175 0.7M 1.48M
cod-rna Numeric 8 59,535 271,617 4.45M 20.3M
covtype Numeric 54 481,082 100,000 56.2M 11.6M
gisette Numeric 5,000 6,000 1,000 50.4M 8.52M