←検索窓の楽しみ方
  ショッピングモール  掲示板ランキング


【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※返信付き投稿の削除は禁止!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら


 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板1こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.4024

選択整列法について
投稿者---Rose(2005/06/16 09:40:57)


#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) { Item t = A; A = B; B = t; } 
#define compexch(A, B) if (less(B, A)) exch(A, B)
void selection(Item a[], int l, int r){ 
  int i, j;
  for (i = l; i < r; i++){ 
    int min = i;
    for (j = i+1; j <= r; j++) 
      if (less(a[j], a[min])) min = j;
    exch(a[i], a[min]);}}
main(int argc, char *argv[]){ 
  int i, N = atoi(argv[1]), sw = atoi(argv[2]);
  int *a = malloc(N*sizeof(int));
  if (sw) 
    for (i = 0; i < N; i++) 
      a[i] = 1000*(1.0*rand()/RAND_MAX);
    else 
      while (scanf("%d", &a[N]) == 1) N++; 
  selection(a, 0, N-1);
  for (i = 0; i < N; i++) printf("%3d ", a[i]);
  printf("\n");}



上記の選択整列法(プログラム中の関数void selection)のプログラムに関し,入力には,N 個の相異なる値のすべての順列が等確率で現れるとすると、内側の反復の中で変数 min が更新される回数の平均がNlogNになることを習ったのですが、なぜNlogNになるのかがわかりません。どなたかなぜこうなるのかを数学的な証明で教えてください。



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:選択整列法について 4025 もぐりん 2005/06/16 10:42:54
<子記事> Re:選択整列法について 4026 επιστημη 2005/06/16 10:48:49


No.4025

Re:選択整列法について
投稿者---もぐりん(2005/06/16 10:42:54)


選択整列法についての質問なんですか?
それともC言語に関する質問なんですか?
前者なら専門書を購入して勉強してください。



この投稿にコメントする

削除パスワード

No.4026

Re:選択整列法について
投稿者---επιστημη(2005/06/16 10:48:49)


ごめんなさいわかんない。
ソートに要する時間計算量はΟ(N^2)なのは明らかだけど。
習ったのなら、教えてくれたヒトに教わるのが一番ではないかと。



この投稿にコメントする

削除パスワード

No.4027

Re:選択整列法について
投稿者---Rose(2005/06/16 11:47:44)


すいません。
漸化式を用いたら数学的に証明できました。
ありがとうございました。




この投稿にコメントする

削除パスワード

No.4028

Re:選択整列法について
投稿者---επιστημη(2005/06/16 13:32:21)


>漸化式を用いたら数学的に証明できました。

後学のため、教えてくださいゼヒ。




この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧




掲示板提供:Real Integrity