最悪ケースでも長くならないようなキューとか割り込みとかの技術はちょっと前まで一大研究分野になってたと思う。 そういうの使うと平均でもある程度はでるんだけど、最悪を気にするならきちんと分布でみたほうがいい。 べき遅延問題は最近だとネットワークや並列コンピューティングで問題になってて。 ネットワークは正常なのに永遠に返事が来ないなんて最悪ケースもある。 プチコンみたいなブラックボックスの場合。 個々の命令の速度の測定は最速のパターンで調べて、それを組み合わせて最速のアルゴリズムにする。 そのアルゴリズムの実際の速度は、実際に組んでみて実行時間の度数分布をみる。 最悪ケースを対処したいなら度数分布から統計的に許せる速度を推計して使う。 ってのが王道かな。