私はビッグオーとシータを理解しています。質問は次のとおりです。証明または反証します。h（n）が増加関数の場合、f（n）= theta（g（n）=> h（f（n））= O（h（g（n））） 。n1>n2の場合、h（n1）> h（n2）
それで、上記の質問では、私は増加する関数を理解する点で立ち往生しています。それを反証する関数を見つけようとしている場合、たとえば、nと2nはこれで問題ありませんか？becos big-ohは、一定の係数だけでなく急速に成長していることを表しますが、h（n）関数が定義されているような条件はありません（つまり、>は文字通りここよりも大きいと思いますが、それは間違っていますか？）
また、h（f（n））のようなものがh（g（n））と同じ速度で成長しているのを見つけたとしても、それは本質的にシータであることを意味します。シータのbecosルーズバウンドは大きいです-ああ、その場合、私は上記のステートメントを反証することはできません。
シーケンスの途中で理解がずれた場合は訂正してください。ありがとう！
私はいつもこのような問題を、Theta（f）とO（f）の定義を読み直して書き留めることから始めます。アサーションを反証する簡単な例を見つけることができれば、何も証明する必要はありません。私は、h（x）= 2 ^ xのように非常に急速に成長するh（x）のアイデアが好きです。次に、たとえばf（x）= 2x、g（x）= x、h（f（x））= 2 ^（2x）、h（g（x））= 2 ^ x、h（f（x ））/ h（g（x））= 2 ^ x-これらを定義にプラグインして、何が起こるかを確認してください。f（x）= 2g（x）なので、少なくとも私の定義では、f（x）= Theta（g（x））およびg（x）= Theta（f（x））であることに注意してください。
与えられたを満たしてf(n) = 2n、この問題を解決するための矛盾した例を見つけました。g(n) = nf(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)))ます。したがって、反証されました。
矛盾した例が反証するのに十分であることを私は知りませんでした。私はそれを証明するためのより正式な方法を試みていて、詳細をめちゃくちゃにしていました。
ありがとう。