퍼즐 점프 게임 복잡성

Question

내 질문은 여기에 제기 된 문제에 대한 특정 : Interview puzzle: Jump Game

상단 대답은 그것이 O(n) 시간에 실행되도록 주장하고있다. 그것은 각 요소는 단 한 번만 (두 번째 시간을 건너 뛸 수 있습니다 간주되는 요소)

간주 될 필요가 있기 때문에 우리는 이미 간주 한 경우, 그냥 확인을이

을 할 수 있다고 말한다 요소는 요소 당 일정한 시간이 걸리므로 O(n^2)을 가져야합니다. 맞습니까? O(n)은 각 새 요소를 고려해야하며 O(n)은 이미 고려한 요소를 제외해야합니다. 왜 이것이 사실이 아닌가?

Answer 1

특정 요소를 이미 고려했는지 확인할 필요가 없습니다. 이미 확인한 색인을 추적하고 방금 전에 점프 한 색인을 제외하고 가장 높은 v를 추적하면됩니다) 배열까지.

그런 다음 계속해서 각 새 요소를 이전 최대 값과 비교할 수 있습니다.