問題タブ [recurrence]

T(n) = 2T(n/2) + log n を解こうとしています

置換 n = 2^k

したがって、基本的には i*2^i の項を合計する必要があります。ここで、i = 1 で n - 1 をログに記録します
。これらの項を合計する簡単な方法を見つけることができませんでした。私は何か間違っていますか？この再帰を解決する他の方法はありますか? マスター定理は彼女に効くでしょうか? はいの場合、どのように？

ありがとう。

私のデータ構造クラスでは、T(n) や大きな O 問題 O(n) のような再帰関係を見ています。これらを学習するためのリソースをいただければ幸いです。私の教科書は T(n) をカバーしておらず、教授は多くの手順をスキップしています。

これらのことを解決するための、段階を追った適切な方法は見たことがありません。すべての問題は固有のものであることは理解していますが、これらを実行するための何らかのフレームワークが必要です。

ありがとう。

Mathematica で with 条件を作成しようとしていRecurrenceTableますが、再帰的なものは正しく機能していますが、完全には評価されません。

これらは正しい結果ですが、数値形式にする必要があります。{{0.25, 0.}, {0.25, 0.5625} ...

これを行う方法はありますか？ありがとう！

その式を使用してベッセル関数を実装しようとしましたが、これはコードです:

しかし、MATLAB のベッセル関数を使用してこれと比較すると、異なる値が大きすぎます。たとえば、 Bessel(20) と入力すると、結果として 3.1689e+005 が返されます。代わりに bessel(20,1) と入力すると、 3.8735e-025 というまったく異なる結果が得られます。

私はこの再発を解決しようとしています

T(n) = 3 T(n/2) + n lg n ..

n lg n は O(n^2) であるため、マスターの定理ケース 2 に属するという解決策にたどり着きました。

しかし、ソリューションマニュアルを参照した後、彼らが持っているこのソリューションに気づきました

解は、0 から 0.58 の間の e に対して n lg n = O ( n ^(lg 3 - e)) と言う

これは n lg n が O(n) であることを意味します..これは正しいですか? ここで何か不足していますか？

nlgn O(n^2) ではありませんか?

コードのスニペットを考えると、一般的に複雑さをどのように判断しますか。BigOの質問に非常に混乱していることに気づきました。たとえば、非常に簡単な質問です。

TAはこれを組み合わせのようなもので説明しました。これがnのように、2 =（n（n-1））/ 2 = n ^ 2 + 0.5を選択し、定数を削除してn^2になります。intテスト値を入れて試すことはできますが、この組み合わせはどのように行われますか？

ifステートメントがある場合はどうなりますか？複雑さはどのように決定されますか？

では、再帰についてはどうでしょうか...

テストが近づいているので、練習問題の助けが必要です... これを帰納法で証明する必要があります。

再帰関係: m(i) = m(i-1) + m(i - 3) + 1、i >= 3 初期条件: m(0) = 1、m(1) = 2、m(2) = 3

m(i) >= 2^(i/3) を証明する

これまでに私ができることは次のとおりです。

基本ケース: m(3) >= 2 ------> 5 >= 2. したがって、基本ケースが成り立ちます。

帰納仮説m(k) >= 2^(k/3) を満たす ak があるとします。

ここで、k+1 に対して成り立つことを証明しなければなりません。

m(k+1) >= 2^((k+1)/3)

（仮説を代入することにより）等しい：

m(k) + m(k-2) + 1 >= 2^((k+1)/3)

これは私が立ち往生しているところです。ここからどこへ行けばいいのかわからない。どんな助けでも大歓迎です。みんなありがとう！

この問題は、2011 Codesprint ( http://csfall11.interviewstreet.com/ ) からのものです。

コンピュータ サイエンスの基本の 1 つは、数値が 2 の補数でどのように表されるかを知ることです。A から B までのすべての数値を 2 の補数表現で 32 ビットを使用して書き留めるとします。全部で何個の 1 を書き留めますか? 入力: 最初の行には、テスト ケースの数 T (<1000) が含まれます。次の各 T 行には、2 つの整数 A と B が含まれます。 出力: 各テスト ケースに対応する T 行を出力します。制約: -2^31 <= A <= B <= 2^31 - 1

サンプル入力: 3 -2 0 -3 4 -1 4 サンプル出力: 63 99 37

説明: 最初のケースでは、-2 には 31 個の 1 が含まれ、その後に 0 が続きます。-1 には 32 個の 1 が含まれ、0 には 0 個の 1 が含まれます。したがって、合計は 63 です。2 番目のケースの場合、答えは 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99 です。

-X の 1 の数と (-X) = X-1 の補数の 0 の数が等しいという事実を利用して、検索を高速化できることがわかりました。解決策は、答えを生成するための O(log X) 再帰関係があると主張していますが、私はそれを理解していません。ソリューション コードは、 https ://gist.github.com/1285119 で確認できます。

この関係がどのように導き出されるかを誰かが説明できれば幸いです!

二分木 T は、T のすべてのノード m に対して次の場合、半平衡です。

R(m)/2 <= L(m) <= 2*R(m)、

ここで、L(m) は m の左サブツリーのノード数、R(m) は m の右サブツリーのノード数です。

(a) N 個のノードを持つ半平衡二分木の数を数える再帰関係を書きます。

(b) (a) の再帰を計算するための動的計画法のアルゴリズムを提供します。

このための再帰関係を作成するにはどうすればよいですか?

以下は該当しますか？

彼は関数か何かのような再帰関係をもっと求めていると思います.?

また、動的計画法を使用して問題を解決するにはどうすればよいですか? 上記の提案されたコード スニペットを適用する場合、何も保存する必要はないと思います。

親切に助けてください。