I've asked the same question on a specific algorithm, the insertion sort, but I've got no feedback from it.
Basically i think that you have to somehow calculate the complexity of each instance of your problem, then group the cases that have the same complexity, plot the different complexities and do something like a weighted average. Of course the case of insertion sort was more interesting then talking in general, since permutations are known groups and i thought that an easy way to figure how many different complexities you have, and how many cases of each complexity is by doing something with equivalence classes.