최대 서브 어레이 문제 무작위 대입 복잡성

무차별 대입을 사용하는 Maximum subarray problem의 런타임/메모리 복잡도는 얼마입니까?최대 서브 어레이 문제 무작위 대입 복잡성

더 최적화 할 수 있습니까? 특히 메모리 복잡성?

감사

2011-04-13 Sumer Cip

알고리즘은 링크 된 페이지에 있으므로 답변을 얻기 위해 알고리즘을 검사 할 수 있습니까? –

페이지의 알고리즘이 무차별 대입을 통해 구현되지 않았습니다. 이것은 O (n) 및 O (1) 공간 알고리즘입니다. 사실이 특정 문제에 관심이 없습니다. 이 문제에 대한 무차별 대입 접근법의 복잡성 분석은 CS의 다른 많은 문제와 유사합니다. –

적어도 한 번 어레이의 모든 항목을 검사해야하므로 O (n)보다 더 잘 수행 할 수는 없습니다. 누적 합계를 유지해야하기 때문에 최소한 O (1) 개의 추가 공간이 필요합니다. * 알고리즘 *을 개선 할 수 없다고 말하고 싶습니다. 그러나 구현을 최적화하는 것이 거의 확실합니다. –

브 루트 포스 오메가 (N^2)이다. Divide를 사용하여 당신은 Theta (ngg n) 복잡성으로 그것을 할 수 있습니다. 자세한 내용은 Introduction to Algorithms과 같은 많은 서적이나 this lecture과 같은 웹의 다양한 리소스에서 볼 수 있습니다.

출처

2011-04-13 13:20:21 MarcoS

최대 합을 찾는 무차별 대입 알고리즘은 복잡도가 [O (n ** 3)]이며 [max_sum_subsequence] (http://wordaligned.org/articles/the-maximum-subsequence-problem#toc1)를 참조하십시오. 최대 부분 배열을 찾는 무차별 대가가 더 나은 복잡성을 가질 수 없다고 가정하는 것이 합리적입니다. – jfs

최대 서브 어레이 문제 무작위 대입 복잡성

답변

관련 문제