Big-Theta (または Big-O) の定義に基づいて、この形式の方程式を解く/証明するにはどうすればよいですか: An^2+ Θ(n) = Θ(n^B) where A and B are some constants(つまり、両側に O(n) があります)。
Big-O と Big-Omega を解決/証明する方法は知っていますが、無名関数が関係している場合に c1、c2、および n を見つける方法が完全にわかりません。
Big-O と Big-Theta の両方の例を示していただければ幸いです (両方の例で A=2 と B=2 を使用してみましょう)。
if and only ifAn^2 + Theta(n)にあることに注意してください。
今から仮定しましょう。Theta(n^B)B == 2
Big Theta の定義から、Theta(n) も O(n) であることがわかります。したがって、すべての n > N1: に対して c1 と N1 が存在しますAn^2 + Theta(n) <= An^2 + c1*n。
また、すべての n>N2 に対して c2,N2 が存在することもわかっていAn^2 + c1*n <= c2*n^2ます。大きな O の定義によりAn^2 + Theta(n)、O(n^2)(定数c2と を使用してN=max(N1,N2)) であることがわかりました。同様に、Omega(n^2) についても示さAn^2 + Theta(n)れTheta(n^2)ています。