最大子阵列问题蛮力复杂度 [英] Maximum subarray problem brute force complexity

问题描述

使用蛮力最大子数组问题的运行时/内存复杂度是多少？

What is the runtime/memory complexity of the Maximum subarray problem using brute force?

可以进一步优化它们吗？

Can they be optimized more? Especially the memory complexity?

谢谢

推荐答案

强力是欧米茄（n ^ 2）。使用分而治之，您可以实现Theta（n lg n）复杂度。许多书籍都提供了更多详细信息，例如算法简介或Web上的各种资源中，例如这个讲座。

Brute force is Omega(n^2). Using Divide and conquer you can do it with Theta(n lg n) complexity. Further details are available in many books such as Introduction to Algorithms, or in various resources on the Web, such as this lecture.

这篇关于最大子阵列问题蛮力复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！