問題タブ [recurrence]

数値に電力を供給する効率的な方法として、次の再帰関数で漸近解析を実行しようとしています。累乗が奇数の場合と偶数の場合の方程式が異なるため、漸化式を決定するのに問題があります。この状況にどう対処するかわかりません。実行時間はtheta（logn）であることを理解しているので、この結果に進む方法についてアドバイスをいただければ幸いです。

私が書いたアルゴリズムの複雑さを調べるために再帰関係を解こうとしています。これが等式..

T(n) = T(n-1) + Θ(n)

そして、O(n2) の答えを見つけましたが、それが正しかったかどうかはわかりません。誰か確認してくれませんか？

更新: 式が T(n) = T(n-1)+Θ(nlogn) の場合はどうなりますか? それでも O(n2) でしょうか?

アルゴリズムの正当性を証明するためのルール/スキームが存在するかどうか疑問に思っていますか？たとえば、自然数で定義され、以下で定義されている関数$F$があります。

ここで、$ n \ \ text {div} \ 2 = \ left \ lfloor \ frac {n} {2} \ right \ rfloor $

タスクは、$ F（n、k）= \ begin {cases} 1 \ Leftrightarrow {n \ choice k} \ \ text {mod} \ 2 = 1 \ 0 \text{それ以外の場合は}\end{cases}であることを証明することです。 $

それほど複雑には見えませんが（私は間違っていますか？）、この種の証明をどのように構成する必要があるのか​​わかりません。助けていただければ幸いです。

私はこの再発を見ていて、正しいアプローチを取っているかどうかを確認したかった.

したがって、答えは n^(1/2) のシータ境界になります。

次の問題を解決する方法を見つけるのに助けが
必要f(n)です: そして与えられた。 マスター定理を 試してみましたが、3 つのケースすべてがここに当てはまりませんでした。置換法を使用していると思いますが、それを適用する方法がわかりません。9f(n/3)+(n2)*(log3n)n > 1
f(1)=1
f(n)

再帰関係の式は T(n)=aT(n/b)+f(n) であることを知っています。そして、その方程式を考えると、BigO を解く方法を知っています。宿題の質問で、リスト内のノードの数をカウントする再帰関数を書くように言われました。それを実行したのに、再帰関係を書くように言われました。これが私のコードです：

しかし、私は独自の再帰関係式を作成/定式化する方法について完全に迷っています...どうすればaまたはbを見つけることができますか....どこから始めればよいかわかりません。この関数の再帰関係をどのように記述すればよいですか? ありがとうございました。

私はデータ構造/アルゴリズム試験の準備をしていて、再帰関数の再帰関係とコードのスニペットの大きな O ランタイムを見つけることを扱う練習問題をいくつかやりたいと思っていました...誰かが私を正しい方向に向けることができますか (オンラインリソース好ましい）？

x 週間ごとに特定の曜日に実行される cron ジョブを作成したいと考えています。例: 毎週日曜日と月曜日の真夜中に 2 週間ごとに実行します。

cron 式は「計画」ごとに保存され、SQL Server 2008 でncrontab関数を使用して、指定された cron 式の日付を生成します。

という表現はありますか？またはいくつかの式の結合？

次の式を使用しようとしましたが、常に同じ日を月で返します

編集:
x 日/週ごとの繰り返しを探していましたが、cron の主な問題は、繰り返しが毎回月の最初の日にリセットされることです。たとえば、3 日ごとに 29 日に繰り返しを開始すると、次の発生は翌月の 1 日になります。

次の解決策として cron を無視しました: http://www.codeproject.com/Articles/20343/Recurring-Date-Generator-with-Pattern-Coding

再発する一連のイベントがあります。これらのイベントが今後5週間ほどでいつ発生するかを計算できる必要があります。

このシステムは、今月中にこれらのイベントが発生することをユーザーに通知します。

例えば：

イベント1

• 開始日=2011年12月19日月曜日
• 再発パターン=月曜日/隔週

イベント2

• 開始日=2012年2月3日木曜日
• 再発パターン=木曜日/3週間ごと

今は3月22日です。今後5週間以内に、イベント1と2の日程が決まります。

それがクリスマスであるかどうかを検出できると便利です。そうすれば、イベントは別の日になります。

私は.NETMVC2を使用していますが、それは偶然だと思います。

助けてくれてありがとう

Math.SE で回答、再帰関係の行列を生成

再帰のf(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4)場合、行列のべき乗によって解決できるように、どのようにして生成行列を取得できますか?

f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)対応する生成行列は次のとおりです。

では、必要な繰り返しのために同じものを取得する方法は? また、次のような再発の場合の手順は次のとおりです。

f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+..+someconstant*f(n-k)?

ありがとう。