回 帖 发 新 帖 刷新版面

主题:请教一个算法复杂度问题

递归定义
T(n)= O(1)  , n <= 1;
      2T(n/2) +O(n); n >1

T (n) = O()???

请教```

回复列表 (共1个回复)

沙发

找到了
T(n)=2*T(n/2)   +   O(n)   
          =4*T(n/4)   +   2*O(n/2)   +   O(n)   
          =4*T(n/4)   +   2*O(n)   
          =8*T(n/8)   +   3*O(n)   
          ...   
          =2^k   *   T(n/   2^k)   +   k*O(n)   
  令   (n/2^k)=1,   k=log(n)   (注:log(n)是以2为底)   
  则原式T(n)等于   
          =n*T(1)   +   log(n)   *   O(n)   
          =n*O(1)   +   O(n*log(n))   
          =O(n)   +   O(n*log(n))   
          =O(n*log(n))

我来回复

您尚未登录,请登录后再回复。点此登录或注册