問題タブ [asymptotic-complexity]

これが私の機能です。それは単純なものです、私は答えが何であるかについて自信がありません。

さて、複雑さを得るために、私は次のことを行います。

T（n）= T（n / 2）+ O（1）

T（n / 2）= T（n / 4）+ O（1）

..。

T（1）= O（1）

今、方程式を追加して、私は得ています

T（n）= O（1）+ O（1）..。

それで、最終的な答えは何ですか？

私はランダム化されたクイックソートアルゴリズムを研究しています。このアルゴリズムの実行時間は、常に「予想実行時間」として表されることに気づきました。

「予想実行時間」を指定または使用する理由は何ですか？最悪の場合または平均的な場合を計算しないのはなぜですか？

次の疑似コードの実行時間を分析するのを手伝ってくれる人はいますか

私が見る方法は、下限の omega(n^3) です。これは、外側の for ループ内がちょうど theta(1) である場合にそうなるからです。

外側のループの最初の n 回だけ実行される内側のループに混乱しています。内部ループの実行時間を平均するだけですか: n^3 * ((1/n^2)*n + (1/n)*1、この場合は O(n^3) ですか?

試験の準備中にこの問題が発生しました。

数値a1、...、anおよびb1、....、bnの2つの配列が与えられ、各数値は0または1であり、、ai + ai + 1のような最大スパン（i、j）を見つけるための最速のアルゴリズム+ .... + aj = bi + bi + 1 + ....+bjまたはそのようなスパンがないことを報告します。

（A）ハッシュが許可されている場合、O（3 ^ n）およびomega（2 ^ n）の時間がかかります。

（B）キー比較モードでO（n ^ 3）とomega（n ^ 2.5）と時間を取ります

（C）シータ（n）の時間とスペースを取ります

（D）2n個の要素の合計が偶数の場合にのみO（平方根（n））の時間がかかります。

n個の要素のバイナリヒープがあり、さらにn個の要素を挿入したいとします（必ずしも次々に挿入する必要はありません）。これに必要な合計時間はどれくらいですか？

1回の挿入でlognが必要になるため、シータ（n logn）だと思います。

クラス階層を構造化するいくつかの方法は、他の方法よりも効率的ですか? これを測定する方法はありますか？設計パターンは計算の複雑さをどのように考慮に入れているのでしょうか? 私はこれについて間違って考えているだけですか？ちょっと興味があるんだけど。

この式f ( n ) = 2 ^{O ( n )}は正確に形式的に何を意味するのでしょうか?

私は動的プログラミングを独学しています。それはほとんど魔法です。しかし、真剣に。とにかく、私が解決した問題は次のとおりGiven a stairs of N steps and a child who can either take 1, 2, or 3 steps at a time, how many different ways can the child reach the top step?です。問題はそれほど難しくありませんでした。私の実装は以下のとおりです。

ただし、今はランタイムを取得したいと考えています。これをどのように把握すればよいですか？私は Akra-Bazzi と Master Theorem に精通しています (それ以上ではありません)。それらはここに当てはまりますか？

http://en.wikipedia.org/wiki/Master_theorem

ここでは、次のように思われます:T(N) = 3 * T(???) + O(1)しかし、私にはよくわかりません。

みんなありがとう。

私は漸近記法の原則を理解しており、たとえば何かが O(1) または O(n ² ) である場合にそれが何を意味するかを理解しています。しかし、O(log n) とはどういう意味ですか? または O(n log n) たとえば?