알고리즘의 효율성을 판단하기 위한 지표 중 하나
복잡도를 더 잘 쉽게 이해하기 위해서 자료 구조와 알고리즘을 먼저 알아봐야 한다.
데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것.
책장으로 예를 들자. (출처 : https://bnzn2426.tistory.com/115 )
- 가장 많은 책을 넣는 방법은 규칙없이 다 꽂아 넣는 것. -> 당장은 이 책장의 공간을 잘 활용한것 같아보임. 하지만 이후 책을 찾을때 문제 발생
- 규칙이 없기 때문에 모든 범위에서 책을 찾아야함.
일정 규칙을 세워 보자. - 오름차순으로 정리
- 책의 제목을 오름차순으로 꽂아 넣는다는 규칙을 세움 -> 책을 찾기가 수월해짐.
- 공간도 모두 활용 할수 있음 -> 단, 처음 책을 꽂을때, 이후 추가할때 어려움 발생.
일정 규칙을 세워 보자. - 분야 별로 정리
- IT 관련 서적만 찾아볼 수 있게 됨. 하지만 IT관련 서적이 더 있지만 들어갈 공간이 없음
- 반면 소설이 꽂혀있는 라인은 공간이 여유로움
=> 공간의 비효율이 발생하기 시작
일정 규칙을 세워 보자. - 가림막
- 가림막을 이용해 남은 IT관련 서적을 꽂음 -> 공간을 효율적으로 사용함
- 하지만 가림막이 불필요한 공간을 차지함
- 같은 분류가 밑으로 넘어가 버린 책은 헷갈림이 발생할 가능성
- 책장 = 메모리
- 책 = 데이터
=> 디테일은 많이 다를 수 있지만 전체적인 개념을 이해하는데 무리가 없음
연산에 사용되는 컴퓨터의 메모리 자원은 매우 한정적인데 반해 처리해야 할 데이터는 무수히 많을 것 -> 메모리 공간을 효율적으로 사용 해야함!
- 모든 목적에 맞는 자료구조는 없고, 어디에 어떤 자료구조를 써야할지 정답은 없음. 따라서 각각의 자료 구조가 갖는 장점과 한계를 이해하고 알고 사용하는것이 중요함.
- 위의 간단한 예시에서도 다양한 이유와 목적으로 책들을 진열하는 방법을 제시했고 어떤 방법을 사용하든 정답은 없었음
단, 자료 구조에서는 메모리 공간과 실행 시간의 효율성을 따져야만 함 !
알고리즘 : 어떤 문제를 해결하기 위한 일련의 절차나 방법을 공식화한 형태로 표현
=> 문제풀이에 필요한 계산절차, 처리과정의 순서
위의 예를 다시 생각해보자.
알고리즘은 책장에 진열된 책들을 어떤 순서나 규칙을 가지고 찾을 지에 대한 방법
알고리즘의 조건
- 입력 : 외부에서 제공되는 자료가 0개 이상 존재
- 출력 : 적어도 2개 이상의 서로 다른 결과를 출력 (즉 모든 입력에 하나의 출력이 나오면 안됨)
- 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성
- 유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료
- 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것
좋은 알고리즘의 분석 기준
정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.
작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정
기억 장소 사용량 : 수행에 필요한 저장 공간
최적성 : 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 '가장 좋은'의 의미이다
- 복잡도
- 시간 복잡도
- 공간 복잡도
공간 복잡도
- 특정 크기의 입력에 대해 얼마나 많은 메모리를 차지하는지 의미
- 알고리즘을 위해 필요한 메모리의 양
시간 복잡도
- 특정한 크기 입력에 대한 알고리즘이 얼마나 오래걸리는지 의미
- 알고리즘을 위해 필요한 연산의 횟수
- 복잡도를 표현하기 위해 점근 표기법중 빅오 표기법 사용
=> 알고리즘의 실행 속도!!
점근 표기법 : 함수를 단순화하여 함수의 증가율을 다른 함수와 비교 표현 하는 방법
점근적 표기법에서 헷갈리지 말아야 할 것
증가율이 더 빠르다 = 알고리즘이 더 느리게 수행된다.
증가율이 더 느리다 = 알고리즘이 더 빠르게 수행된다.
- 빅 - 오 : O(g(n)) 는 g(n)이라는 함수보다 증가율이 같거나 더 느린 함수들의 집합
- 빅 - 세타 : θ(g(n)) 는 g(n)이라는 함수와 증가율이 같은 함수들의 집합
- 빅 - 오메가 : θ(g(n)) 는 g(n)이라는 함수보다 증가율이 같은 함수들의 집합
먼저, T(n) = n²+3n+1 로 예시를 들어보자
T(n) = n²+3n+1 인 시간 복잡도를 n² 와 3n+1로 나누어 그래프로 나타내면
n값이 증가할수록 3n + 1의 값이 전체 시간 복잡도에 끼치는 영향은 미미하게 됨
n에 값이 무한히 증가할수록 n²+3n+1 그래프와 점근적으로 가까워짐
즉, n에 값이 증가할수록 최고차항 이하의 값들은 함수 증가율에 큰 영향 X
이를 토대로 알고리즘을 비교한다고 가정
알고리즘 1 - T(n) = 10000n +20000
알고리즘 2 - T(n) = n²+3n+1
둘중 어느 알고리즘이 효율적인지 한번에 판단하기는 어려움 그래서
=> 이를 빅오로 표현하면 다음과 같음
알고리즘 1 - T(n) = O(n)
알고리즘 2 - T(n) = O(n²)
- 이 때 함수 g(n)을 함수 f(n)의 점근적 상한 이라고 함.
- 즉, f(n)의 복잡도는 최악의 경우 g(n) 보다 작거나 같다는 의미. f(n) ≤ g(n)
알고리즘 성능이 최악의 경우라도 g(n) 이상이라는 의미
- 이때 함수 g(n)을 함수 f(n)의 점근적 하한 이라고 함.
- 즉, f(n)의 복잡도는 최선의 경우 g(n)보다 크거나 같다는 의미 f(n) ≥ g(n)
알고리즘 성능이 아무리 빨라도 g(n) 이하라는 의미
- 이때 g(n)을 함수 f(n)의 점근적 상한 및 하한이라고 한다
- 즉,f(n)의 복잡도는 최선이나 최악의 경우라도 g(n) 범위 내 존재 f(n) ≥ = g(n)
알고리즘 성능이 g(n)의 상한과 하한에 포함한다는 의미
a. 시간 복잡도 최선을 고려했을 경우 - 하한 점근 ( 빅 오메가 )
- 결과를 반환하는 데 최선의 경우 1초, 평균 1분, 최악1시간이 걸리는 알고리즘을 구현했다고 가정
- 이 알고리즘을 100번 실행한다면, 최선의 경우 100초가 걸림
- 하지만 실제로 걸린 시간이 1시간이 훨씬 넘겼다면?
- 어디서 문제가 발생한건지 쉽게 알수 없음
- 이 문제를 해결하기 위해 거의 대부분의 로직을 파악해야함
- 따라서 최선의 경우를 고려했을때, 문제를 파악하고 해결하는데 많은 시간이 필요
b. 시간 복잡도 중간을 고려했을 경우 - (빅 세타 )
- 평균값을 기대하는 시간 복잡도로 고려
- 알고리즘을 100번 실행할때 100분이 소요된다고 생각했으나,최악의 경우가 몇개 발생하여 300분이 넘게 걸림
- 위 최선의경우를 고려했을 경우와 같은 고민을 안게됨
c. 시간 복잡도 최악을 고려했을 경우 - (빅 오)
- 극단적 예, 위와같이 최악의 경우가 발생하지 않는다는 가정은 제외
- 최악의 경우를 고려하여 대비하는 것이 바람직
=> 가장 많이 쓰는 표기법
위에서 이야기한 자료구조와 알고리즘, 복잡도의 정의와 서로의 상관 관계를 잘 이해해야 한다.
자료구조와 알고리즘은 서로 밀접한 관계를 가지고 있음
다시한번 책장에서 책을 찾는것을 예시로 들어 보자.
"클린코드" 라는 책장에서 찾으려고 한다.
- ㄱ-ㅎ 제목순으로 진열 되어있다면 'ㅋ'이므로 뒤쪽부터 (역순)으로 찾게 될 것.
- 책 분류별로 진열 되어있다면 IT관련서적 쪽을 먼저 찾게 될 것.
즉, 자료 구조의 선택 → 효율적인 알고리즘 선택
넓은 의미에서 자료구조 + 알고리즘(+@) = 프로그램