[알고리즘] 공간 복잡도, 시간 복잡도, 빅오 표기법

효율적인 알고리즘을 짜려면?

알고리즘이 시작하여 결과가 나올 때까지의 수행시간이 짧으면서 컴퓨터의 자원(ex:메모리)을 덜 사용하도록 짜야한다.

-> 즉, 알고리즘을 짤때 수행시간과 기억공간을 분석하여 시간 효율성과 공간 효율성을 고려해야함

공간 복잡도(space complexity)

알고리즘이 사용하는 기억 공간 분석

시간 복잡도(time complexity) ★

알고리즘의 수행 시간 분석 => 알고리즘의 효율성을 이야기할때 주로 시간 복잡도를 고려

절대적인 수행 시간을 나타내는 것이 아닌 알고리즘을 이루는 연산이 몇 번 수행되는지를 숫자로 표시함

 

• 시간 복잡도 함수 : 연산의 수행 횟수는 보통 입력의 개수에 따라 달라지기 때문에 n에 대한 함수로 나타냄. 이 함수를 시간복잡도 함수라고 하며 T(n)으로 표기

EX) 양의 정수 n을 n번 더하는 문제의 세 가지 알고리즘의 연산 횟수 비교

알고리즘 A	알고리즘 B	알고리즘 C
sum <- n*n;	for i<-1 to n do     sum <- sum + n;	for i<- 1 to n do    for  j<- 1 to n do        sum <- sum +1 ;

 

	알고리즘 A	알고리즘 B	알고리즘 C
대입연산	1	n	n*n
덧셈연산		n	n*n
곱셈연산	1
전체 연산 수	2	2n	2n^2

 

빅오 표기법 : O(n)

• 보통 자료의 개수가 큰 경우 시간 복잡도 함수에서 차수가 가장 큰 항이 전체의 값에 영향을 주기 때문에 (예를 들어 T(n)=n^2+n+1에서 n=1000이면 n^2=1000000이고 n=1000이기 때문에 n은 n^2의 0.1%로 T(n)에 n^2에 비해 영향을 적게 줌) 차수가 가장 큰 항을 기준으로 시간 복잡도를 표시하는 방법
• 연산의 횟수를 대략적(점근적)으로 표기한 것 
• n에 비례하는 수행시간을 가진다고 했을 때 알고리즘의 시간 복잡도를 O(n)이라고 표기
• O(n) 을 빅오 of n이라고 읽는다.
• 다항식의 최고 차항의 계수, 다른 항들과 상수항을 버리고 최고차항의 차수만을 사용한다 .예를 들어 f(n)=3n^2+100이면 O(n)=n^2

• 빅오 표기법의 종류