시간복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다.

시간복잡도 측정

시간복잡도를 측정하는데는 몇가지 방법이 있다.

절대시간 측정

• 성능에 따른 차이가 발생하기에 정확하지 않을 수 있다.
• 외부 요인이 크게 작용할 수 있다.

연산횟수 측정

코드가 같다면 항상 동일한 결과가 나온다.

입력값에 따른 변경이 있을 수 있다.

점근적 표기법

N^2+3N+5 각 항의 그래프, N이 커질수록 격차가 커진다.

알고리즘에서 구현방법을 결정할때 어떤 알고리즘을 선택해야할지 확인이 필요하다면 아래 연산 횟수를 바탕으로 확인할 수 있다.

대충 1000만번 연산이 1초라고 생각하면 된다.

출처 - 코딩테스트 합격자되기 c++ (인프런)