标签: recurrence

考虑这个例子:

T(n) = T(7n/8) + 2n 

我假设T(1)= 0

并尝试以下列方式解决它

T(n) = T(7n/8) + 2n
     = T(49n/64) + 2.(7n/8) + 2n
     = T(343n/512) + 2.(7n/8).(7n/8)+ 2.(7n/8) + 2n 
     = T(1) + 2n ( (7n/8)^i + ..... + 1)               

但我无法得出任何结论.我对下一步该怎么办感到困惑.

我们要通过重复替换来解决递归关系:

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

我开始替换并得到以下内容.

T(n)=T(n-2)+log(n)+log(n-1)

按对数乘积规则,log(mn)= logm + logn,

T(n)=T(n-2)+log[n*(n-1)]

继续这个,我明白了

T(n)=T(n-k)+log[n*(n-1)*...*(n-k)]

我们知道基本情况是T(1),所以n-1 = k - > k = n + 1,并在我们得到的中取代

T(n)=T(1)+log[n*(n-1)*...*1]

显然n*(n-1)*...*1 = n!所以,

T(n)=T(1)+log(n!)

我不知道如何解决这一点.答案只是O(log(n!))？我已经读过其他解释说它是Θ(nlogn),因此它遵循O(nlogn)和Ω(nlogn)分别是上限和下限.

求解:T(n)= T(n-1)+ T(n/2)+ n.

我试图解决这个使用递归trees.There两个分支T(n-1),并T(n/2)分别.T(n-1)将进一步深入.所以我们得到了O(2^n).这个想法是否正确？

我正在尝试按照我的要求对时间序列中的模式进行聚类

如何使用python聚类音节类型？

我尝试使用递归图技术来解决我的问题，因此我在 python 中编写了一些代码来重现这些图。我想知道我的代码是否正常，我用声音时间序列进行了尝试，根据距离参数值，我得到了这种结果：

http://ceciliajarne.web.unq.edu.ar/envelope-problem/

我还包括数据集。我正在使用 ch2。这是我的代码：

import numpy as np
import scipy
import os

from scipy.io import wavfile
import wave, struct
import matplotlib.pyplot as pp

from pylab import *

import scipy.signal.signaltools as sigtool
import scipy, pylab
from scipy.io import wavfile
import wave, struct
import scipy.signal as signal
from scipy.fftpack import fft

 #Data set input
data=np.random.rand(44000*3) 
#random secuence to compare with almost 3 seconds of data, cold be other
print 'data:', data

#set size 
sissse=data.size
print 'size: ',sissse
print …

我有一个活动清单.我创建了一个每日重复的新项目(开始时间:2010年1月5日上午12:00和结束时间:2010年5月30日12:00 AM).我想删除具有开始时间的项目:5/12/2010 12:00 AM但我的应用程序抛出了异常.

我的代码如下:

   DateTime eventDate = DateTime.Parse(list.Fields.GetFieldByInternalName("EventDate").GetFieldValueAsHtml(DateTime.Parse(this.DateTimeOfItem).ToUniversalTime()));
                            SPQuery pQuery = new SPQuery();
                            pQuery.ExpandRecurrence = true;
                            pQuery.CalendarDate = eventDate.AddDays(-1);
                            pQuery.Query = string.Format("<OrderBy><FieldRef Name=\"EventDate\"/></OrderBy><Where><And><DateRangesOverlap><FieldRef Name=\"EventDate\" /><FieldRef Name=\"EndDate\" /><FieldRef Name=\"RecurrenceID\" /><Value Type=\"DateTime\"><Week /></Value></DateRangesOverlap><Eq><FieldRef Name=\"ID\" /><Value Type=\"Counter\">{0}</Value></Eq></And></Where>", this.ID);
                            SPListItemCollection itemColl = list.GetItems(pQuery);
                            int index = 0;
                            while (index < itemColl.Count)
                            {
                                SPListItem item = itemColl[index];
                                if (DateTime.Parse(item["EventDate"].ToString()).CompareTo(eventDate) == 0)
                                {
                                    web.AllowUnsafeUpdates = true;
                                    item["UID"] = Guid.NewGuid().ToString();
                                    item["EventType"] = 3;
                                    item["RecurrenceID"] = eventDate;
                                    item["MasterSeriesItemID"] = this.ID;
                                    item["XMLTZone"] = null;
                                    item["RecurrenceData"] = "Every 1 …

如何解决T(n) = T(n-1) + n使用迭代方法和答案是theta(n^2)

如何构造segs返回列表中所有连续段列表的函数？例如,(segs '(l i s t))应该产生以下答案:

(() (t) (s) (s t) (i) (i s) (i s t) (l) (l i) (l i s) (l i s t))

我对如何按照HtDP中描述的设计原则解决这个问题特别感兴趣(不,这不是书中的问题,所以请随时讨论它!)如何解决？在程序推导中使用哪些原则？

在Cormen的算法入门书中,我试图解决以下问题:

通过替换表明递归关系T(n)= T(n-1)+ n的解为O(n2)

(没有给出初始条件,这是问题的全文)

但是,我似乎无法找出正确的过程.教科书只是简单地触及它,我搜索过的大多数网站似乎都认为我已经知道了.如果有人可以给我一个简单的,一步一步的指南,甚至是一个链接,我将不胜感激.

对于踢球,这是我到目前为止的尝试:

T(n)<= c(n ^ 2)
       <= c(n-1)^ 2 + n
       <= c(n ^ 2 -2n +1)+ n(我很确定不是<c( N ^ 2))

再次感谢.

更新:这是我试图完成的方法的一个例子,以避免混淆.

证明解是O(nlog(n))
T(n)= 2T([n/2])+ n
替换方法要求我们证明T(n)<= cn*lg(n)可供选择常数c> 0.假设此约束适用于所有正m <n,其中m = [n/2],得到T([n/2])<= c [n/2]*lg([n/2] ).将其代入复发产生以下结果:
T(n)<= 2(c [n/2]*lg([n/2]))+ n
       <= cn*lg(n/2)+ n
       = cn*lg(n) - cn*lg(2)+ n
       = cn*lg(n) - cn + n
       <= cn*lg(n)
其中最后一步保持,只要c> = 1

我可以遵循这个逻辑很好,但是当我尝试复制上述问题中的步骤时,我会陷入困境.

我只能找到关于如何递归和迭代地实现gcd函数的帖子,但是我找不到这个.我确定它在Stackoverflow上然而我找不到它所以我道歉如果它是一个重复的帖子.

我查看了维基百科(这里)的分析,无法理解它们的递归关系.

考虑以下在C中递归实现的GCD函数的实现.它具有一个前提条件,即两个数字必须为正数,但与运行时间无关.

int gcd( int const a, int const b ) {
  // Checks pre conditions.
  assert( a >= 0 );
  assert( b >= 0 );

  if ( a < b ) return gcd( b, a );

  if ( b == 0 ) return a;

  return gcd( b, a % b );
}

对运行时间进行分析我发现每个操作都是O(1),因此我们知道到目前为止的递归关系是:T(n)= O(1)+ ???.现在分析递归调用,我不知道如何将(mod b)解释为我的递归调用以正确陈述我的递归关系.

在我的算法和数据结构类中,我们给了一些递归关系来解决或者我们可以看到算法的复杂性.

起初,我认为这些关系的单纯目的是为了记下递归分而治之算法的复杂度.然后我在麻省理工学院的作业中遇到了一个问题,其中一个被要求为迭代算法提供递归关系.

考虑到一些代码,我怎么能真正想出一个递归关系呢？有什么必要的步骤？

我是否可以记下任何情况,即最坏的,最好的,具有这种关系的平均情况,这是否正确？

有可能有人给出一个代码如何变成递归关系的简单例子吗？

干杯,安德鲁