ランダウの記号

質問

データ構造とアルゴリズムの分野では有名なオーダーがありますが。

f1(n)f2(n) = O(g1(n)g2(n))

O(f(n)) + O(g(n)) = O(max{ | f(n) | , | g(n) | })

この上記の公式(？)は有名だと思います。

問題は証明なんですが。。。

教授に質問しても, あいまいな返答しか返ってこず図書館でも証明が書いてある本がありませんでした。

簡単な証明でいいので教えていただけないでしょうか？

ご協力お願いします。

回答No.1

Tacosan · ベストアンサー

積の方は, f1(n) = O(g1(n)) かつ f2(n) = O(g2(n)) ですよね?
O(・) の定義から f1(n) と g1(n), f2(n) と g2(n) の関係を書いて, そこから f1(n) f2(n) と g1(n) g2(n) の関係を示し, これが「うまく定数を選ぶ」とO(・) の定義を満たすことを言えば OK.
和の方も, まあ似たような感じです.
ちょっと気をつけなければならないところはありますが, 流れはこんな感じです.