マージソートのオーダー
マージソートの分析
マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。
このことから、再帰方程式は、以下のようになる。
この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。
：
よって、
選択法とクイックソートの処理時間の比較
データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。
- データ件数 N= 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
- データ件数何件以上なら、クイックソートの方が高速になるか答えよ。
設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。
高専ライブ：2018年5月6日（第573回）
- ゴールデンウィークの思い出
- サイエンス共和国 第２８回「ｉＰｈｏｎｅで儲ける技術者の話」
- お弁当の話
- キャンパスウォークの話
担当：木村（２Ｍ，ＭＣ）、山野（２ＥＩ，ＭＩＸ）、田中（２Ｃ），西（教員）
xenial の snapd いるの？
以前から発生していた、Ubuntu のサーバで snapd がうまくインストールできないトラブル。 install しようとすると古いバージョンを削除するときの prerm script でエラーとかいうメッセージがでるので、/var/lib/dpkg/info/snapd.prerm を編集して、エラーの出る処理の前に exit 0 を入れたりしながら、無理やり削除して、インストールを試みるけど、こんどは、postinst でエラー。
原因がつかめずに、四苦八苦していたけど、「バージョンアップして trusty を使っているなら、/etc/apt/sources.list などの中にある xenial 関係を消せ」という記事を見つける。
まさに、xenial を upgrade した trusty だったので、/etc/apt/ を探すと、php 関係のパッケージで、
deb http://ppa.launchpad.net/ondrej/php/ubuntu xenial main
というのが見つかったので、早々に消してみた。その後、”aptitude update ; aptitude safe-upgrade” を実行したけど、特にパッケージが消されたりもしなかったし、これで OK かな。