首页 > 试题广场 >

某递归算法的递归关系式为T( n ) = 2*T(n2)

[单选题]

某递归算法的递归关系式为T( n ) = 2*T(n/2) + O( n )，那么它所对应的时间复杂度为 


  • O(log n)
  • O(n*log n)
  • O(n)
  • O(n^2)
查看正确选项
添加回答
Explorer_ndh头像 Explorer_ndh
每次向下递归，递归算法量减少一半，共log n复杂度。而每次递归中包含一次复杂度为n 的算法。即n * log n
发表于 2019-02-24 15:58:41 回复(0)
天天1024头像 天天1024
O（n）代表时间复杂度为n的一个操作，二分法时间复杂度是log n，结果就是n*log n。
发表于 2019-03-05 10:43:56 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 算法工程师 第四范式 PHP工程师 2019 Java工程师
上传者：小小
难度：
2条回答 1490浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号