开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >LCP时间复杂度分析

问LCP时间复杂度分析
EN

Stack Overflow用户

提问于 2020-03-02 18:48:31

回答 1查看 129关注 0票数 0

对于这篇leetcode解决方案文章中描述的方法3解决方案(分而治之)：https://leetcode.com/articles/longest-common-prefix/

谁能详细解释一下时间复杂度T(n)=2T(n/2)+O(m)最终是O(mn)？

time-complexity

EN

回答 1

Stack Overflow用户

发布于 2020-03-02 23:55:43

T(n) =2* T(n/2) + O(m) =2* (2 * (T(n/4) + O(m)) + O(m)) = ...

我们可以找到，例如n= 2^50，它将有2^50 * T(1) + 2^50 * O(m)。所以答案是O(m*n)

票数 0

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/60487273

复制

相似问题