問題タブ [asymptotic-complexity]

f（n）とg（n）が与えられ、f（n）がO（g（n））、Ω（g（n））、またはΘ（おやすみなさい））

また、正しい関係のためにc（s）とn0を決定する必要があります。

このような問題を開始するにはどうすればよいですか？

これが私が与えられた種類の問題の例です

f（n）= lg（n ^ 2）g（n）= n lg（n）

繰り返しを解決しているときに、床と天井が無視されている場所に出くわしました。

床が無視されているCLRS （第4章、pg.83）の例：

ここ( pg.2、演習 4.1–1 ) は、上限が無視される例です: (編集: これはやや怪しいという世論から収集します。)

実際、CLRS（pg.88）では、次のように述べられています。

「再発を解決するとき、床と天井は通常重要ではありません」

私の質問:

1. ここで「通常」とはすべてのケースを意味しますか? はいの場合、私はいつもそれらを忘れることができます。
2. そうでない場合、再発を解決するときに床と天井が実際にカウントされるのはいつですか?

注: これは宿題の問題ではありません。DS とアルゴリズムの概念を再確認しているときに考えました。

私は友人と一緒に宿題をしようとしています.1つの質問は、線形プローブ方法の検索、追加、および削除の平均実行時間を尋ねます。追加する開いているノードが見つかるまで、特定の数のノードをチェックする必要があるため、O(n)だと思います。検索するときは、元のインデックスから開始し、目的の番号が見つかるまで上に移動します。しかし、私の友人はそれが O(1) だと言っています。どちらが正しいですか？

漸近分析のコースを開始したばかりで、課題の 1 つで、複雑さを変えずに関数に機能を追加することになっています。複雑さは log(N) です。宿題のガイドラインでは、実行時間を「定数」で変更するよう具体的に求められています。3Log(N) にすることは、定数で変更すると見なされますか?

大きなシータ表記の解決に問題があります。大きな O 表記は最悪のケースと上限を表し、オメガ表記は最良のケースと下限を表すことを理解しています。

O(nlogn) 時間と Omega(n) で実行されるアルゴリズムが与えられた場合、どのように Theta が等しいかを推測できますか? O と Omega が等しい場合にのみ、シータ表記が存在すると仮定し始めていますが、これは本当ですか?

関数Fを考えてみましょう：2 ^（3 * n）+ n ^ 2

関数A：2 ^（3 * n）は、Fの特性としてビッグシータ、オメガ、またはOとして使用できますか？なんで？

Big Omega、Big Theta、Big Oの概念を改訂していて、この例に出くわしましたが、どこから始めればよいのかわかりません。

私の友人と私はこの問題を発見しましたが、解決方法がわかりません。自明ではなく、標準の置換方法は実際には機能しません (または正しく適用できません)。これは、ランクの問題でピボットを使用したクイックソートである必要があります。

ここに再発があります：

T(n) = T(n^(1/2)) + T(nn^(1/2)) + n

どんな助けでも大歓迎です。ありがとう！

次の2つのケースで、時間と空間の複雑さに関連する疑問があります

引用符

ケース I:

Recurion: 階乗計算。

ここで、なぜ時間の複雑さが 2*n になり、空間の複雑さが n に比例するのでしょうか。

と

ケース II:

反復:-

時間の複雑さは n に比例し、空間の複雑さは一定です。これはいつも私を混乱させます。

私は自分の本やインターネット上のいくつかのサイトをよく調べましたが、自分の答えについて完全には確信が持てません.

存在する反転の数に関して、InsertionSort と FingerTreeSort (RB ツリーに基づく) の漸近的な実行時間を与える必要があります。InsertionSort は O(n+INV) 時間で実行され、FingerTreeSort は O(n+n*lg(INV/n+1) で実行されます。INV = 0、n、n^1.5、および n^2/ の漸近的なランタイムを指定する必要があります。 4.

私が思いついたのは、InsertionSort が O(n)、O(n)、O(n^2)、O(n^2) で実行されるということです。

これは正しいです？なぜだめですか？(特に INV = n と n^1.5 についてはよくわかりません)

FingerTreeSort の場合: O(n*lg(n))、O(n*lg(n))、O(n*lg(sqrt(n)))、O(n*lg(n^2))

FingerTreeSort のすべてについて疑問がありますが、これらはあるべきだと私が考える方法です。適切な漸近ランタイムを見つけるにはどうすればよいですか? たとえば、FingerTreeSort と n^1.5 の場合、一般的なランタイムにプラグインして O(n+n*lg (sqrt(n)+1) であり、漸近的であるため、+1 や +n などの下位の数値を無視して O(n*lg(sqrt(n))) を得ることができます。これは正しい方法ですか? ?

この質問に答えてくださった方々に、あらかじめ感謝いたします。私はそれを大いに感謝します:)

ps。Javaで書いていますが、質問には関係ありません。

私がこの関数を持っているとしましょう:(Haskell構文）

関数によって実行される作業（計算量）は何ですか？

最初は明らかに一定だと思っていましたが、タイプがx有限でない場合、つまりxが任意の量のメモリを使用できる場合はどうでしょうか。コピーによって行われる作業も考慮に入れる必要がありxますよね？

これにより、関数によって実行される作業は、実際には入力のサイズで線形であると私は信じました。

これはそれ自体が宿題ではありませんが、関数によって実行される作業を定義する必要があるときに思いついたものです。

同様の問題があると私は信じています。