平成19年度 - みずぴー日記

最悪な場合は、すでに対象となる配列が整列されている場合、だというのは有名。

この場合、一回につき対象となる配列が1回短くなるだけ。なので、必要な比較回数は
$T(n)=n+(n-1)+(n-2)+...+1=(N+1)N/2$

よって、
$O(n^2)$

また、これが起こるのはp(ピボッド)が、最小または最大の要素だった場合。

最善の場合は、配列の長さが1/2づつになっていく。
なので、必要な比較回数は、
$C(n)=n+2C(n/2)$
という漸化式で表せる。nは分割するときに各要素を調べるので必要。

これを解くと、
$C(n)=n+2(C(n/2)+n/2)=...=nlog(n)$
となる。

よって、
$O(nlog(n))$
またこれが起こるのは、pがちょうど配列を二等分するとき。

qsortを呼ぶときに使用されるスタックが消費される。なので、qsortが呼ばれる回数が問題になる。
そして、qsortは配列の左部分をソートするために呼ばれるので、左部分の長さが問題になる。

左部分の長さが、1づつしか減らない場合が最悪となる。
なので、
$S(n)=1+S(n-1)$
となる。

よって、
$O(n)$
また、これが起るのは、pが最小の要素である場合である。

左部分の長さが、常に1の場合が最善となる。
よって、
$O(1)$
また、これが起るのは、pが最大の要素である場合である。

常に、短い方だけを再帰的にソートすればいい。

if(i-left < right-j){ // 条件があやしい
  // 左のほうが短い
  qsort(a,left,i-1);
  left = j+1;
}else{
  // 右のほうが短い
  qsort(a,j+1,right);
  right  = i;
}

アプリケーションプログラムを製作するときに使うOSのインターフェース。

このれを用いることで、入出力やファイルなどのOSが管理している資源にアクセスすることがきる。

コンパイラの用語らしい。
調べてないです。

モジュールがどれほど、機能的にまとまっているかを示す指標。

これが高いほど、モジュールの独立性が高く、いいモジュールであると言うことができる。