목록가지치기 (1)

DNF LOVE

[알고리즘] 연산량 줄이기(feat. 가지치기)

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