동적 프로그래밍과 관련된 혼동

Question

동적 프로그래밍과 관련하여이 페이지를 살펴 보았습니다. I는 $ 복잡도 O (N^2)로 주어진다 $ 제 경우 여기

주어진 복잡도에 대해 큰 혼란이다. 나는 그것이 어떻게되었는지 확실하지 않다. 누구든지 자세히 설명해 주실 수 있습니까? 복잡성이 여기에서 어떻게 계산되었는지.

Answer 1

만약 i와 j가 둘 다 1에서 n까지 자유라면, 1을 고정시키고 i를 1-n에서 j까지 범위를 정하면서 생각하면 n^2 하위 문제를 볼 수 있습니다. 그런 다음 i 1-n의 모든 값에 대해 동일하게 수행하십시오. 그러나 그림과 표기법은 j> i (인접한 고유 집합)를 암시하는 것으로 보이므로 약간 혼란 스럽습니다. 나는 x = 2, x = 3 (x의 수를 2로 시작하는 것으로 해석 하는가?) 또는 x2, x1 (j를 지수로 해석하는 것) 일 수 있는가?