Average case complexity of search data structures
One such notion is that of smoothed analysis, in which we compute the worst-case expected complexity of an algorithm on a randomly perturbed input. In more detail, let $N(x)$ be a randomly perturbed version of $x$, and let $T$ be the time complexity of the algorithm. Then we are interested in
$$
\sup_x \mathbb E[T(N(x))].
$$
The "worst case" aspect is with respect to the unperturbed input, and the "average case" aspect is with respect to the perturbation.

The simplex algorithm has been shown to be polynomial time in this sense, although its worst case complexity is exponential.