私はビッグオーとシータを理解しています。 h（n）が増加している場合、f（n）= theta（g（n）=> h（f））= O（h（g）））関数h（n1）> h（n2）のときn1> n2私の宿題で、h（f（n））= O（h（g））を証明したり、反証したりしています。
したがって、上記の質問では、私は増加関数の理解の点に固執しています。それを反証する関数を見つけようとすると、例えば、nと2nはこれを受け入れることができますか？ビッグオーは一定の要因だけでなく急速に成長することを表していますが、h（n）関数が定義されている状態はありません。ここでは間違っているのですか？）
また、h（f（n））がh（g（n））と同じ割合で成長しても、それらが本質的にシータであることを意味しても、 - ああ、テサのゆるい縛りはそれほど大きい私は上記のステートメントを否定することはできません。
私の理解がある程度ずれてしまった場合は、順序を守ってください。ありがとう！
とg(n) = nが与えられたf(n) = theta(g(n))を満たすことで、この問題を解決する矛盾した例が見つかりました。
今、h(x) = 2^xとすると、これはh(f(n)) = 2^2n = 4^nとh(g(n)) = 2^nを意味します。
定義により、これはh(g(n)) = O(h(f(n)))を意味します。したがって、反証された。
私は、矛盾した例が反証するのに十分であることを知らなかった。私はそれを証明するためのより正式な方法を試みていて、細部まで混乱していました。
ありがとうございました。
私はいつも、Theta（f）とO（f）の定義を書き直して書き留めることで、このような問題を開始します。あなたがアサーションを反証する簡単な例を見つけることができれば、何かを証明する必要はありません。私はh（x）= 2^xのようなh（x）を非常に急速に成長させるという考えが好きです。次に、 f（x）= 2x、h（f（x））/ h（f（x） g（x））= 2^x - これらをあなたの定義に入れてみて、何が起こるか見てみましょう。少なくとも私の定義ではf（x）= Theta（g）とg（x）= Theta（f（x））を持つことに注意してください。