問題タブ [recurrence]

T(n) = T(n-1) + n反復法と答えを使用して解決する方法はtheta(n^2)

誰かがこの再発を解決する方法を知っていますか？

マスター定理はここでは機能しません。

私はこの再帰関係を与えられています：

C > 0 、a >= 1 ..

私の問題は T (a) にあります。定数を「再帰」する方法がわかりません??

同様に、再帰ツリーを構築しようとしている場合は、次のようにします。

私が何を意味するか分かりますか？T(a) は何を表していますか??

どんなリソースでも大歓迎です。ありがとう。

または、繰り返し考えてみてください。

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

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

さまざまな機器で予防保守を実行する必要があるときに、基本的にユーザーにプロンプ​​トを表示するアプリケーションを開発しています。各機器 (ツールと呼びます) には、異なる再発パターンがあります。90 日ごとなど、時間に基づくものもあれば、使用状況などの他の要因に基づくものもあります。たとえば、特定のツールが X 回チェックアウトされた後、PM が必要になる場合があります。

すべてのツールは個人に割り当てられるため、そのユーザーがアプリケーションにサインインするときに、その時点で PM を必要とするツールのリストを表示する必要があります。PM が完了すると、これらのアイテムはリストから削除され、日付が変更されたり、ツールがベビーベッドにチェックインされたりするなどの他の状況が発生すると、ツールが追加されます。

このリストを返すサービス メソッドの設計から始めて、リスト内の項目を解決するために使用するアプローチに関するヘルプを探しています。入力には、ユーザーの識別子と現在の日付が含まれます。その上で、ツールのリストを照会し、ツールの繰り返しパターン、最後に PM が実行された時刻、および最後の PM 以降に発生したイベントに基づいて、そのアイテムをリストに表示するかどうかを判断する必要があります。

うまくいけば、それは理にかなっています。このロジックにどのようにアプローチすべきかについての考えやガイダンスに感謝します。

自分自身を 1 回だけ呼び出すアルゴリズムの再帰関係を行う方法は知っていますが、1 回の発生で自分自身を複数回呼び出す方法はわかりません。

例えば：

次の質問があります。

Big'O'表記を使用して、答えを単純化する漸化式を解きます。

これが一次の不均一な漸化式であることを知っており、質問に答えましたが、基本ケース（f（0）= 2）の正しい出力を取得できないようです。

質問は、証明内で等比数列フォーラムラの合計を使用する必要があります。

これが私の答えです-sum（x = y、z）は大文字のシグマ表記の代わりです。ここで、xはyに初期化された合計の下限であり、zは合計の上限です。

まず、11行目の方程式をさらに簡略化できると確信しています。次に、n = 0でサブスクライブすると、結果として2が得られます。13行目に到達したときにこの答えを得ることができません...

編集：私が知る必要があるのは、12行目の方程式にn = 0をサブサブするときにf（0）= 2が得られない理由です。また、私が知りたいのは、f（n）の方程式を単純化する方法です。 12行目？

誰...？

再帰関係に対して次の閉じた形式のソリューションがある場合、大きな O の下でそれを単純化するにはどうすればよいですか。

f(n) = 3^n + n.9^n

私は推測を危険にさらします：

f(n) は O(9^n) のメンバーです -> これが正しいかどうかわかりませんか? 誰かが大きなOの下で上記の方程式を単純化する方法と、どのルールを使用したかを教えてください...

前もって感謝します

このアルゴリズムから再帰方程式を見つける必要があります。

私はそれについて推論し、n<=2 の場合、T(n) = O(1) と結論付けました

内側の while は O(n) (反復ごとに j が 1 ずつ減少) であり、外側の while は O(logn) (反復ごとに i が半分になる) であり、O(n*log( n)):

T(n) = T(n/3) + T(n/2) + O(n*log(n)) n > 2の場合

これは良い議論ですか？