알고리즘 문제 해결 전략 04 - 알고리즘의 시간 복잡도 분석

반복문이 지배한다

• 지배한다(dominate): 한 가지 항목이 전체의 대소를 좌지우지 하는 것
• 알고리즘의 수행시간을 지배하는 것 → 반복문

선형 시간 알고리즘

이동 평균 계산하기

• 이동 평균(moving average), 주식의 가격, GDP, 몸무게 등 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준
• 시간에 따라 관찰된 숫자들이 주어질 때 M-이동 평균은 마지막 M개의 관찰 값의 평균으로 정의
  • 새 관찰 값이 나오면 M-이동 평균은 새 관찰 값을 포함하도록 바뀜