積の法則(規則？)

[大工]

基本的なことを聞いてすみません＞＜。

積の法則の証明は理解できたのですが

手持ちの本では

1. big ←　D[1];
2. for(i = 2; i <= n; i = i + 1){
3. if(D > big){
4. big ← D;
5. }
6. }
7. print(big);

あと、Ｏ(ｃ・f(ｎ))　=　Ｏ(ｆ(ｎ))となる理由がいまいち分かりません＞＜。

[管理人]

いくつか意図のわからない部分があるのですが、

・全体の計算量についての問題なのでしょうか？
・f(n)とは、n回繰り返される時の全体の計算量なのでしょうか？
・big←Dとは、普通のイコールの代入文とどう違うのでしょうか？

質問を拝見するに、和の法則とか積の法則じゃなくて極限の問題であるような気がするのですが・・。

1+nにおいて、

limit (n→∞)(1+n) = ∞

　
とかそういう事ではないのでしょうか？
計算量の近似値を求める問題のように思えるのですが。

積の法則というのは排反事象の事ではないのでしょうか？

[大工]

アルゴリズムの本には積の規則って書いてあるんですが＾＾；

・全体の計算量についての問題なのでしょうか？

　　全体の計算量についての質問です。

・f(n)とは、n回繰り返される時の全体の計算量なのでしょうか？

　　T(ｎ)のオーダーはf(ｎ)であるということです。

・big←Dとは、普通のイコールの代入文とどう違うのでしょうか？

　　えっと。。。代入文と違いはないと思います。


証明の結論を載せるのを忘れてました。

・・積の規則・・

T1(ｎ)とT2(ｎ)をそれぞれＯ(ｆ1(ｎ))、Ｏ(ｆ2(ｎ))である計算量とする。この時、Ｔ１(ｎ)・Ｔ２(ｎ)はＯ(ｆ1(ｎ)・ｆ2(ｎ))である。

[組木紙織]

ランダウの記号 フリー百科事典『ウィキペディア（Wikipedia）』
にオーダーの定義が書いてありました。

それを私なりに要約すると（間違っているかもしれませんが、）
f(n)のオーダーは
limit_(n→∞) (f(n)/g(n)) = <定数>
となるもっとも単純な関数をg(n)とする。
このときのg(n)を
f(n)のオーダーとする。
h(n) = Ｏ(f(n))と表記する。

これを基にして考えると
limit_(n→∞) (f(n)/g(n)) =<定数>
limit_(n→∞) (c・f(n)/g'(n)) =<定数>

g(n) = g'(n)となるので
＞Ｏ(ｃ・f(ｎ))　=　Ｏ(ｆ(ｎ))
となります

極限の計算ができればわかるのですが、

[大工]

>h(n) = Ｏ(f(n))

h(n)ってどこから・・・？

[管理人]

う～ん、問題の意味がまだよくわかりません・・。
プログラム自体は最大値を求めるプログラムなんですか？
で、十分大きな配列「D[n]」の中にランダムな数がそれぞれ入っていると？

if(D > big){

この条件文にマッチするのはしだいに減っていくはずですから、
nが大きいほどここは無視できるようになると思いますよ。
積とかなんとかじゃんくて単なる近似値の問題のような気がしますが・・。

[管理人]

xを試行回数、numを条件文が行われた回数として、
以下のように試行回数と条件文の実行される確率を求めました。

#include <stdio.h>
#include <stdlib.h>

void main(){
	int ran[100000],i,j,x=10,big,num;

	for(i=0;i<100000;i++)
		ran=rand();

	for(j=0;j<5;j++){
		num=0;
		big=ran[0];
		for(i=0;i<x;i++){
			if(big<ran){
				big=ran;
				num++;
			}
		}
		printf("試行回数：%6d回　代入確率:%.5f％\n",x,(double)num/x);
		x*=10;
	}

}

実行結果

試行回数：    10回　代入確率:0.30000％
試行回数：   100回　代入確率:0.06000％
試行回数：  1000回　代入確率:0.00600％
試行回数： 10000回　代入確率:0.00070％
試行回数：100000回　代入確率:0.00008％

　
　

[大工]

読み返してみたら質問がはっきりしてませんね。。。＞＜。・・。、申し訳ないです。。。

手持ちの本に記載されている証明が理解できなかっただけなんです。。。

[大工]

手持ちの本は近似値よりも規則にしたがって問題を進めていく形式のようです。。

頑張って理解してみます。

[ぽん太]

>forループにとってその定数倍
forループが入れ子になっている場合などは計算サイズが増えるとforループの中の計算も
影響してくるけど今回の場合はサイズの増加に関係しない処理という意味ではないでしょうか？

>Ｏ(ｃ・f(ｎ))=Ｏ(ｆ(ｎ))
結局これを示せば(理解すれば)よいということですよね？
よくわかりませんが
(1) Ｏ(ｃ・f(ｎ))⊆Ｏ(ｆ(ｎ))
(2) Ｏ(ｃ・f(ｎ))⊇Ｏ(ｆ(ｎ)) の２つを示せばいいのではないでしょうか？

[組木紙織]

私の上記の記述に間違えがありました。

＞h(n) = Ｏ(f(n))と表記する。
g(n) = Ｏ(f(n))と表記する。

です。
すみません。