[알고리즘] 시간복잡도 (time complexity)

알고리즘의 '효율성 분석'을 위해, 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정

- 메모리의 양(정적공간+동적공간) 계산 => 공간복잡도(space complexity)

- 수행시간 => 시간복잡도(time complexity) 

=> 수행시간을 통해 시간복잡도를 구하고 효율적인 알고리즘인지 분석한다.!

# 시간복잡도(time complexity)

알고리즘을 프로그램으로 구현 => 컴퓨터에서 실행시켜 실제 수행시간을 측정하지만, 일반적이지 않다!

(컴퓨터의 속도나 사용한 프로그래밍언어, 프로그램 작성법, 컴파일러의 효율성 등에 종속적)

그렇다면 시간복잡도란 무엇? 

알고리즘이 수행하는 기본적인 연산의 횟수를 합한 것 ★★★

시간복잡도에 영향을 미치는 요인 2가지

① 입력으로 제공되는 데이터 크기 => 입력크기

② 입력 데이터의 상태

시간복잡도는,

- 입력크기 n이 증가 => 수행시간도 증가

- 입력크기의 함수로 표현!! ☆☆☆ f(n) = (    )

- 입력데이터 상태에 종속적

⒜ 평균수행시간 - 입력되는 데이터의 모든 상태를 고려 후 평균을 낸 시간

⒝ 최선수행시간 - 입력데이터가 이상적일 때

⒞ 최악수행시간 - 가장 오래걸림, 입력데이터가 가장 최악 일 때

- 시간복잡도는 최악수행시간을 사용 => 아무리 늦어도 최악수행시간보다 늦을 순 없음

/* n 은 입력크기

시간복잡도는 알고리즘이 수행하는 기본적인 연산의 횟수를 합한 것,

=>  f(n) = 3n + 6 (시간복잡도 수행시간)

while문 i < n 조건으로 실행될 때, i = 0,1,2, ... n-1까지 실제 수행되지만 n 까지 가서 조건을 비교 후 빠져나오므로

6번 째 라인에서 수행되는 연산횟수의 합은 n+1

while문 내부에 실행되는 블록은 i = n-1일 때까지만 실행 => 연산횟수의 합은 n

*/

f(n) = 3n + 6     --- (점근성능 사용하여 표현) --->    O(n)  (Big-Oh표기)
∴ 시간복잡도는 O(n)