APSS_04.md

알고리즘 문제해결 전략 4장

알고리즘의 복잡도

• 시간 복잡도
• 공간 복잡도

가장 중요한 것은 시간 복잡도, 공간 복잡도를 희생해서 시간 복자도를 향상시키기도 한다(DP)

시간복잡도 분석

• atomic한 연산이 반복수행되는 횟수
• 시간복잡도가 항상 수행시간을 결정하지 않는다(데이터 사이즈에 따라)

빅오 표기법

• 가장 빠르게 증가하는 최고차항만 남긴 것
• 최악의 경우와 상관 없다. (ex. 퀵정렬의 경우 최악의 경우 O(N^2), 평균적으로 O(NlogN))
• 다만 수행시간의 점근적 상한을 나타낼 뿐

수행시간 어림짐작하기

주먹구구 법칙

1초당 반복문 수행 횟수가 1억번을 넘어가면 시간 제한을 초과할 가능성이 있다. 알고리즘의 시간복잡도와 입력의 크기를 확인해서 이 법칙을 적용할 수 있다. 하지만 그 외 수행시간에 영향을 주는 요소들도 있으므로 보수적으로 10% 이하일 때 허용, 10배 이상일 때 초과로 사용하면 좋다.

• 메모리 사용 패턴이 복잡한 경우(캐싱이 어려운 경우)
• 반복문 내부가 복잡한 경우(반복문 내부를 간단하게 하면 좋다)