\(11.1\)一些概念

1.\(O()\)与最坏运行时间的区别

  大\(O\)不等于最坏运行时间！\(O\)表示的是运行时间的上界，只要一个函数的运行时间小于\(O(times)\)，那么它就算在\(O\)内。最坏运行时间比\(O\)更为严苛，因为对于最坏运行时间\(worst_time\)，函数必须能取到这个时间、而非仅仅小于等于这个时间。

2.对\(BST\)性能的衡量

  \(BST\)性能的衡量需要考虑以下概念：

• 深度(\(depth\))：节点到树根间链接的数量。
• 高度(\(height\))：树的最大深度。
• 平均深度(\(average\))：树所有深度的平均值，可以用\({\sum_{i=0}^D d_in_i}\over N\)，\(d_i\)代表深度，\(n_i\)代表节点的数字。

  \(BST\)的高度代表了它的最坏运行时间，而平均深度决定了它的平均运行时间。