DNF LOVE

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

https://dnf-lover.tistory.com/2 이전에 우리는 '시간복잡도'의 개념에 대해 배웠다.그렇다면 이 시간복잡도 즉, 연산량을 줄이는 방법은 무엇이 있을까? 1. 시간 복잡도의 한계실제 연산량을 계산할 때, 함수의 계수와 낮은 랭크의 항을 무시하게 되기 때문에 실제 연산량과 시간 복잡도를 통해 계산한 연산량의 차이가 클 수 있다. 또, 함수들은 값의 범위에 따라 대소 관계가 다르다는 점때문에 낮은 랭크의 시간 복잡도가 항상 높은 랭크의 시간 복잡도보다 적은 연산량을 보장하지 않는다.위의 그래프를 보면, 길게 보았을 때에는 제곱근들에 비해 Y = X가 더 퍼포먼스가 좋지만, X축이 1이하일 때 퍼포먼스는 y = X 보다 y = X^2 혹은 X^3의 퍼포먼스가 더 좋다는 것을 확인할 수 있..