コーメンらによるアルゴリズム入門の47ページでこの一節に出くわしました。:
式中の無名関数の数は、漸近表記の出現回数に等しいと理解されます。たとえば、式では次のようになります。
Σ ( i =1 ～n ) O( i )
無名関数 ( iの関数) は 1 つだけです。この式は O(1) + O(2) + ... + O( n )と同じではなく、実際には明確な解釈がありません。
これは何を意味するのでしょうか？
質問する
701 次
2 に答える
6
彼らがその表記法（big-Oの合計）を使用するとき、それは単一のO（i）関数（それf(i)を と呼ぶ）があることを意味し、式はその1からnまでの合計を指すと言っていると思います関数。
nこれは、異なる関数 ( を呼び出すf_1(i))f_n(i)があり、それぞれが でありO(i)、式が の合計を参照する場合と同じではありませんf_1(1) + f_2(2) + ... + f_n(n)。後者のことは、表記が意味するものではありません。
于 2012-10-01T00:33:26.177 に答える
0
「式中の無名関数の数は、漸近表記の出現回数に等しいと理解される」ということをまず理解しておくとよいと思います。それはもし
Σ (i=1 to n) O(i)
したがって、無名関数は次のような O(i) に等しいものですΣ (i=1 to n) f1(i)
そして、Σ (i=1 to n) O(i)+O(i)
無名関数が次のように O(i)+O(i) に等しい 2 つの関数を持つ必要がある場合Σ (i=1 to n) f1(i)+f2(i)
于 2014-07-02T03:45:32.557 に答える