問題タブ [asymptotic-complexity]

分割統治法を使用して数値 (a^n) を累乗するプログラムを実装しました。私は同じ問題の2つのバージョンを実装しました:

バージョン 1:

バージョン 2:

バージョン 3:

Q1: 上記のバージョンのどれが の複雑さを持っていθ(lg n)ますか?

Q2: バージョン 2 の複雑さが の場合θ(lg n)、なぜですか? バージョン2の問題サイズが2分割されていますが、サブ問題の数も2なので、バージョン2は の順で大きくなる気がしθ(nlg n)ます。

私の結論についてはよくわかりません。

ありがとう

線が凸多角形と交差するかどうかを検出する O(n) アルゴリズムは、多角形のエッジが線と交差するかどうかをチェックし、交差の数が奇数か偶数かを調べます。

O(log n) アルゴリズムなど、漸近的に高速なアルゴリズムはありますか?

漸化式

T（n）= 2T（n / 2）+ n lg lg n

（lgは2を底とする対数です）マスター定理を使用して解くことができますが、答えについてはよくわかりません。私は自分の答えを見つけましたが、情報のカスケードを防ぐためにここでは言及していません。上記の大きなOとΩを見つけるのを手伝ってください。

クラスでbig-oの学習を始めたばかりです。すべての x>k |f(x)|<=c|g(x)|. 署名するために <= を含める必要があるかどうか、または < 記号を入れるだけで十分かどうかという質問がありました。

例: f(x)=17x+11 とすると、これが O(x^2) であることを証明します。次に、c=28 で x>k=1 とすると、17x+11<=28x^2 となります。x は常に 1 より大きいことがわかっているので、これは 28x^2 が常に 17x+11 より大きいことを意味します。では、本当に等号 (<=) を含める必要があるのでしょうか、それとも (<) だけでよいのでしょうか。

前もって感謝します。

サイズ n=100 のアルゴリズムの実行には 21 秒かかります。サイズ n=1000 の場合、実行に 31 秒かかり、n=10000 の場合、実行に 41 秒かかります。実行の複雑さは何ですか?

O(n) を試した場合: T(n)=(21*1000)/100 = 210 s (O(n) ではない)
O(n^2) を試した場合: T(n)=(21* 1000^2)/100^2 = 2100 秒 (O(n^2) ではありません)
O(log n) を試してみると: T(n)=(21*log1000)/log100=31.5 (O(log n ではありません) )))

私が与えられた他のオプションは O(1/n) です。これを計算するにはどうすればよいですか？

ずっと頭を悩ませている宿題の質問があります。関数 Sum[log(i)*i^3, {i, n}) (つまり、i=1 から n までの log(i)*i^3 の合計) が big-theta であることを証明するよう求められます。 (ログ(n)*n^4)。

Sum[i^3, {i, n}] は ( (n(n+1))/2 )^2 で、Sum[log(i), {i, n}) は log(n! ）、しかし、1）これら2つは合計内の同じ製品の一部であるため、別々に扱うことができるかどうか、および2）これを証明に役立つ形式にする方法はわかりません。

どんな助けでも本当に感謝しています。ありがとう！

最近、リンクされたリストに関する 1 つの興味深い質問に出くわしました。ソートされた単一リンクリストが与えられ、このリストから 1 つの要素を検索する必要があります。

時間計算量は を超えてはなりませんO(log n)。これは、この連結リストに二分探索を適用する必要があるようです。どのように？リンクされたリストはランダムアクセスを提供しないため、二分探索アルゴリズムを適用しようとすると、リストの長さを見つけて中央に移動する必要があるため、O(n) に到達します。

何か案は？

この再発を解決する方法:T(n) = T(n/2) + T(n/4) + O(1)

これはT(n) = aT(n/b) + f(n). そして、しばらく行き詰まりました。

T(n) = 2T(n/2) + M(n) では、T の前の 2 はどこから来ますか。n/2 は除算であり、M(n) は線形であるためですが、2 が何のためにあるのかわかりませんか?

私が解決しようとしている問題があり、助けていただければ幸いです。の時間複雑度はどのくらいですか...

外側の for ループは n 回実行されます。k+= log n内部ループでの処理方法がわかりません。私の考えでは、それは O(n^2) です。k に log(n) を追加しても n ループが追加されるわけではありませんが、O(n*log n) よりも少ないと思います。明らかに、それは単なる推測であり、それを数学的に示す方法を理解するための助けがあれば大歓迎です!