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