某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为 (请作答此空) ,若问题的规模增加了16倍,则运行时间增加 ( ) 倍。

1740 次浏览
  • A、O(n)
  • B、O(nlgn)
  • C、O(n2)
  • D、O(n2lgn)
"对于递归式,假设T(1)=1,则: T(n)=T(n-1)+n =T(n-2)+n-1+n =T(n-3)+n-2+n-1+n =1+2+…+n-1+n =n(n+1)/2 可见,时间复杂度为O(n2)。若问题的规模增加了16倍,则运行时间增加了162=256倍。"
挑战成功
2年前
挑战失败
2年前
挑战失败
2年前