から




IV-1-6 Edit

次のC関数のプログラムは個数nのデータに対してある作業を行う。このプログラムの操作の表しているアルゴリズムの計算量は,次のうちどれか。

#define nmax 100000
int b[nmax+1];
f(int a[],int p,int q)
{
	int i,j,k,m;
	if(p<q){
		m=(p+q)/2;
		f(a,p,m);
		f(a,m+1,q);
		for(i=m+1;i>p;i--) b[i-1] =a[i-1];
		for(j=m; j<q;j++) b[q+m-j]=a[j+1];
		for(k=p;k<=q;k++)
			if(b[i]<b[j]) a[k]=b[i++];
			else a[k]=b[j--];
	}
}
  1. O(log n)
  2. O(n)
  3. O(n log n)
  4. O(n log log n)
  5. O(n2)

Tag: アルゴリズムの計算量



トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 下位頁新規  一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-22 Mon 23:18:30 JST (3044d)