問題タブ [big-theta]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
complexity-theory - ネストされた 3 つの for ループの漸近解析
このネストされた for ループのシータ複雑度を計算したい:
n^3 だと思いますが、これは正しくないと思います。各 for ループは 1 から n にならないからです。私はいくつかのテストを行いました：
n = 5 -> 10
10 -> 120
30 -> 4060
50 -> 19600
したがって、n^2 と n^3 の間にある必要があります。総和の公式などを試してみましたが、結果が高すぎます。n^2 log(n) ですが、それも間違っています...
algorithm - 最終勉強中：漸近記法
私は現在、アルゴリズムの最終段階に向けて勉強しています。これは宿題の問題ではなく、過去の期末試験に由来します。
log log n が log n よりもかなり小さいため、重要でないことは明らかです。しかし、どうすればそれを正式に示すことができますか？私は制限とロピタルに精通しているので、その方法でそれを行う方法を教えていただければ幸いです。
runtime-error - 大きなシータ実行時の複雑さを見つけるのを手伝ってくれる人はいますか
私は Big Theta ( Θ ) 実行時の複雑さの概念に慣れていません。
分析する次の再帰関係があります。
T(n) = 2T(n/3) + 5n 2となり、 Θ( 2 ) が得られました
T(n) = T(n/4) + n 4となり、 Θ(n 4 ) が得られました。
私の答えを確認してください。
string - 文字列を繰り返し 2 倍にする時間計算量は?
次の C++ コードを考えてみましょう。
通常、コード片の時間計算量を分析するときは、内側のループが実行する作業量を特定し、外側のループの実行回数を掛けます。ただし、この場合、構築される文字列がどんどん長くなるため、内側のループによって実行される作業の量は反復ごとに異なります。
このコードをどのように分析して、膨大な時間の複雑さを取得しますか?
algorithm - ビッグシータ境界、アルゴリズム分析
さまざまなアルゴリズムのビッグシータ境界を見つける方法を学ぼうとしていますが、ここでいくつかの質問を読んだり、講義や教科書を読んだりしても、その方法を理解するのに苦労しています。たとえば
配列 a のインデックスの数 n に関して、これが通過する追加の数のビッグシータ境界を把握したいと思います。外側のループ自体が log(n) 回繰り返されることはわかりますが、内側のループで何が起こっているかを表現する方法がわかりません。誰かが説明を持っていますか、あるいは私が相談できるリソースさえありますか?
asymptotic-complexity - 大きなシータ値の比較
これらの異なる大きなシータ値を最大から最小に並べ替えようとしています:
一部の値は同等です。特に、定数項が 1 つのビッグ シータ値を定数項のない同一のビッグ シータ項よりも大きくするかどうかを知りたい (たとえば、これら 2 つの値は等しいか: Θ(22n) & Θ(n)?)。
python - 2 回の再帰呼び出しの Big Theta バウンド
および: f(x, y)_g(n)
のビッグシータ境界はg(n)何ですか?
x == y であるため、条件 inf(x, y)が真になることは決してないため、2 つの再帰呼び出しによって複雑さが決まると考えました。
のみを考慮f(x - 1, y - 1)すると、基本ケースに到達するにはn回の再帰呼び出しが必要であり、各呼び出しは別の呼び出しに分岐しf(x - 1, y - 1)ます。この時点で、私は続行する方法がわかりません。
(答えは Θ(2 n ) です。)