quasistatic https://blog.hatena.ne.jp/quasistatic/ 借りてきた猫のように静か https://quasistatic.hatenadiary.jp/ comp 整列に要する比較や交換の回数は隣接交換法では要素数の二次の多項式でおさえられる。 整列処理全体の時間計算量についてはどうだろう。 要素の比較にしても交換にしてもその回数は要素数の二次オーダであるが、 交換については一回の操作当たり定数回のリストの走査を要する。 リストの走査は要素数の一次オーダの時間計算量を要するため、 整列に要する時間計算量は交換に関する時間計算量が支配的になり、 それは要素数の三次のオーダとなるはずである。 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fquasistatic.hatenadiary.jp%2Fentry%2F20120720%2Fp1" title=" 単連結リストの整列 #70 隣接交換法の時間計算量 - 借りてきた猫のように静か" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-07-20 00:00:00 rich https://quasistatic.hatenadiary.jp/entry/20120720/p1 1.0 100%