Adaptive heap sort: Difference between revisions

Revision as of 01:17, 17 October 2022

Revision as of 01:22, 17 October 2022

Line 76:

=== Oscillations (''Osc'') ===

For sequence <math>X = <x_1, x_2, x_3, .... ,x_n></math>, ''Cross''(''x_i'') is defined as the number edges of the line plot of ''X'' that are intersected by a horizontal line through the point (''i, x_i''). Mathematically, it is defined as <math>\mathit{Cross}(x_i) = \{ j \mid 1 \leq j < n\ and \ \min\{ x_j, x_{j+1}\} < x_i < \max\{ x_j, x_{j+1}\} \text{ for } 1 \leq j </math> n \}\text{, for <math>}1\leq i \leq n</math>. The oscillation(''Osc'') of X is just the total number of intersections, defined as <math>\mathit{Osc}(x) = \textstyle \sum_{i=1}^n \displaystyle\lVert Cross(x_i) \rVert</math>.<ref name=":0" />

=== Other measures ===