11.1.一些概念

\(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\)的高度代表了它的最坏运行时间,而平均深度决定了它的平均运行时间。