목록배열 시간복잡도 (1)

DNF LOVE

[알고리즘 성능 상향] 배열 사용 시 성능을 향상시킬 수 있는 방법(LUT)

공간 복잡도는 낮지만 시간 복잡도가 굉장히 높은 경우 어떻게 해야할까? 그럴때에는 보통 공간(메모리)을 사용하여 시간 복잡도를 낮추는 방법이 있다. 시간 복잡도를 안좋게 하는 가장 대표적인 일이 '불필요한 연산'이다. 계산하는 과정에서 발생하는 불필요한 연산/정보는 자료구조 중 가장 많이 쓰이는 배열에서는 어떻게 해결할까? 공간과 배열의 특징, 'Index'를 활용한다. Index를 통한 배열의 검색의 시간 복잡도는 O(1)이다. 아래 영상처리 개념을 예시로 설명해 보도록 하겠다. 원본 영상에서 명암을 15씩 증가하여 밝기를 높이는 영상처리를 만든다고 가정해보자. 영상처리에서 이러한 기법을 LUT(Look-up Table)이라 한다. LUT연산은 산술 연산을 고속으로 수행할 때 사용한다. 이는 LUT로 ..
Algorithm 2019. 8. 4. 21:34
이전 Prev 1 Next 다음