問題タブ [big-theta]

私はビッグオーとシータを理解しています。質問は次のとおりです。証明または反証します。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ルーズバウンドは大きいです-ああ、その場合、私は上記のステートメントを反証することはできません。

シーケンスの途中で理解がずれた場合は訂正してください。ありがとう！

私はビッグO、ビッグオメガ、ビッグシータ表記の違いについて本当に混乱しています。

ビッグOが上限で、ビッグオメガが下限であることは理解していますが、ビッグθ（シータ）は正確に何を表していますか？

タイトバウンドという意味だと読みましたが、どういう意味ですか？

こんにちは、誰か(x^3)/1000 - 100*x^2 - 100*x + 3が大きなシータ表記で表現するのを手伝ってくれませんか。x^3それは私のように見えますが、x = 0明らかにこの多項式は 3 の値を与えます。x^3定数を掛けてもまったく役に立ちません。この種の問題にアプローチする標準的な方法はありますか?

次のコードを持つ Theta ランタイムはどれですか?

私はこれを思いつきました: T(n) = log(n) * (1 + log(n)) = log(n) + log^2(n) そして今、シータ表記に何を入れるべきかわかりません?

この特定のコードの Theta ランタイムを計算するにはどうすればよいですか。

これまでのところ私はこれを得ましたが、それが正しいかどうか、またはシータ表記でそれをどのように持ってくるかはわかりません。

アルゴリズムの学習を開始しました。のような「定期的な繰り返し」からシータ表記を見つける方法を理解していますT(n) = Tf(n) + g(n)。しかし、私はこの再発で迷っています: 問題 1-2e :

T(n) = T(√n) + Θ(lg lg n)

シータを見つける方法を選択するにはどうすればよいですか? で、えーと、この再発は何ですか？繰り返し内の表記法がよくわかりません。

Big-Theta に関する情報をあちこち探しましたが、十分に理解できたと思います。ただし、疑問が残ります。予想される入力サイズが小さい場合、Big Theta Notation はアルゴリズム効率の効率的な尺度でしょうか?

予想される入力サイズが小さい場合、Big Theta Notation はアルゴリズム効率の効率的な尺度ではないと考えています。まず、Big Theta についての私の理解の一部を次に示します。関数 f(n) は、O(n) と Big Omega(n) の場合、Big Theta(n) です。これらすべての値の数学的定義には、n>n0 が必要です。したがって、私の推論によれば、小さな入力サイズが n0 未満になる可能性があります (そして可能性が高いです)。したがって、私の推論は、Big Theta Notation は、n< n0 の値のアルゴリズム効率の効率的な尺度ではないということです。

ビッグ シータ、ビッグ オー、ビッグ オメガの概念を理解しています。それを証明するのに苦労しています。誘導を行ってから長い時間が経ったので、さびて単純なものが欠けているだけだと確信しています。

たとえば..私が助けを必要としている問題は、それを示すこと5n² - 6n = Θ(n²)です。

問題の Big-Oh 部分を取得しました (big-Oh と Ω を別々に修正しますか?)。

そして大きなオメガ部分は：

....しかし、ここからどこへ行くのですか?! 私は誘導から何かを思い出します... 私はこれらが真実であると仮定します.そして今(n+1)、それぞれnにプラグインして..何かをしますか？この時点で私は自分を見失いました。

こんばんは、

big-OアルゴリズムとΘアルゴリズムを比較するための助けが必要です。
2つのbig-Oを比較する方法は理解できますが、
big-OをΘと比較する方法やbig-OとΩなどを比較する方法を理解するのに問題があります。

以下にいくつかの例を投稿します：

Θ（2ⁿ）vsΟ（2ⁿ）
Θ （n0.6）vsΘ （^nlogn） O（n） ^vsΩ
（n⋅logn）