問題タブ [big-theta]

クライアントのJSONを生成するサーバー側プログラムがあります。私の同僚の何人かは、ネットワークを介して送信するデータの量を減らすために、zip/gzip圧縮を使用することを提案しました。ただし、私の平均的なJSONメッセージの1つに対してテストした場合、両方とも実際に送信されるデータの量を増やしました。私が異常に大きな応答を送信するまで、ジッピングが開始されて有用でした。

それで私はstackoverflowを突っ込み始めました、そして私は最終的にLZOを見つけました、それはテストされたとき、私がしたいことを正確に実行しました。ただし、アルゴリズムの実行時のドキュメントが見つからないようです。また、コードに腰を下ろして自分で理解するのに十分ではありません:)

tl; dr？LZOの実行時間？

配列が 19 を繰り返し追加することによって大きくなる場合、選択ソート アルゴリズムの Big-Theta (T) 表記での最良の場合と最悪の場合の複雑さはどのようになりますか?

例えば：

など。n配列の長さを表すために使用されます。

したがって、同じ数値を配列の末尾に追加していますが、この数値はたまたま最大の数値でもあるため、配列の末尾にとどまります。これは、実際に効率に影響がないことを意味しますか? 私はとても混乱しています。

大きなシータを計算する方法のリアルタイムの例を教えてください。

大きなシータは平均的なケース (最小-最大)/2 のようなものですか?

つまり (最小時間 - 大きな O)/2

間違っていたら訂正してください、ありがとう

指数時間である Θ(2^n) の実行時間を持つ再帰関係を解決しました。同じ再帰関係の Ω と O を見つける方法を教えてください。

Θ(2^n) なら O(2^n) でもいいのかな？下限である Ω を見つけるにはどうすればよいですか?

再帰関係を解いてみました：

T(n) = 2T(n-1) + C.

^{私は、通常の Θ(n 2} ) 二重ループよりも少し手の込んだ二重ネストされた for ループで Big Theta ランタイムを突き止めようとしています。

^{O(n 2} )と言えるのは分かっていますが、Θ形式でお願いします。

等比数列について質問があります。なぜですか

1 + c + c ² + ... + c ⁿ =Θ（c ⁿ）

c> 1の場合？c = 1の場合はΘ（n）であり、c <1の場合はΘ（1）である理由は理解できますが、^c > 1の場合はなぜΘ（cn）であるのか理解できません。

ありがとう！

x = x + 1以下のセグメントでステートメントが実行された回数について、nに関するΘ表記を見つけます。

iの成長率はわかっていますが、の表記O(3^k)方法がわかりません。Θn

宿題の質問があります：

1. ステートメント x = x + 1 が実行される回数のシータ表記を見つけます。（10点）。

これは私がやったことです：

では、まず簡単にしましょう。最初に、次の成長の順序を見つけます。

成長の順序を持O(log(n)) ​​つ実際には対数ベース2

もう一方の内側の for ループは n 回実行されるため、アルゴリズムは次の順序である必要があります。

O(log(n)*n)

私が混乱する部分は、theta 表記が big-O ではないことを見つけることになっていることです。シータ表記は、上限と下限で関数をバインドすると想定されていることを知っています。正解はTheta(log(n)*n)？

このリンクで答えを見つけましたが、その答えにたどり着く方法がわかりません。答えが Theta(n) であると彼らが主張するのはなぜですか?

宿題の質問があります：

T（n）が、アルゴリズムでステートメントx = x+1が実行された回数を表すとします。

x = x+1が実行された回数のシータ表記を見つけます。（10ポイント）。

これが私がしたことです：

次の作業量が実行されます。-ベースケースチェックのための一定量の作業-数をカウントするためのO（n）作業-半分のサイズへの再帰呼び出しに必要な作業

これは漸化式として表すことができます：T（1）= 1 T（n）= n + T（n / 2）

これがどのように見えるか見てみましょう。これに注意することで、これを拡張し始めることができます

ここでパターンが見え始めます。T（n / 2）ビットをk回展開すると、次のようになります。T（n）= n + n / 2 + n /4+⋯+n/ 2 ^ k + T（n / 2 ^ k）

最終的に、これがn/2^k =1 発生すると、これは停止します。T（n）= n + n / 2 + n / 4 + n /8+⋯+1

これは何に評価されますか？興味深いことに、この合計は2n + 1に等しくなります。これは、合計がn+ n/2 + n/4 + n/8 +…. = 2n. 結果としてこの最初の関数がO（n）であるためです。

@templatetypedefが回答したこの質問のおかげで、その回答が得られました

シータ表記と混同していることを知ってください。答えは同じでしょうか？シータ表記は関数を下限と上限で制限することになっていることを私は知っています。それは私が機能する必要があることを意味しますか？

ここで答えを探しているわけではありませんが、次の問題の最悪/最良のケースを見つける方法 (シータ表記) です。for ループは一般に (theta(n)) であり、これは最良のケースと最悪のケースを示しますが、ここでは何か他のことが起こっていると思います。どんな助けでも大歓迎です。

回答を編集:

x + n が返されるため、定数 (theta(1)) が最適です。

最良 = (シータ(1)) 最悪 = (シータ(n))