시간복잡도(time complexity)를 알차게 설명합니다! 빅 오(Big O)를 포함해서 점근적 표기법
참고하였습니다 : https://www.youtube.com/watch?v=tTFoClBZutw&t=1135s
말 그대로 시간이 얼마나 복잡하냐?
근데 이렇게 한국인이 이해하는건 사실상 불가능하다.
시간 복잡도 라는 말은 알고리즘 세계에서 사용 되는 단어, 알고리즘의 성능 지표로 사용된다.
먼저 빠르게 짧게 이해하고 가자
시간복잡도
=> 알고리즘 성능이 얼마나 좋은가?
=> 실행시간이 얼마나 짧은가?
우리는 보통 코드를 보면, 무언가 값을 넣었을때, 실행시간이 짧으면 짧을 수록 성능이 좋다고 생각한다.
당연하다. 음식점에서 주문해놓고 한참동안 음식이 안오면 얼마나 빡치겠는가? (한국인 8282~~)
아래의 코드가 있다. 보자.
우리는 위의 코드의 성능을 알고 싶어서 실행시간을 알고싶다.
그런데,,,
이 실행시간이란 것은 컴퓨터 성능에 따라 천차만별이다.
예를 들어 입력값이 방대한 데이터 라면, 고성능 컴퓨터의 경우 2분안에 처리 할수 있다면, 저사양의 컴퓨터일 경우 하루가 더 걸릴수도 있는 일이다.
단순히 현재 세팅에서 실행시간을 아는건 별 의미 없다는 것이다.
그럼 실행시간을 대신하여 성능을 평가할 지표가 없을까?
다시 코드를 보자
보아하니,
정수배열을 반환값으로 하는 multiply 함수는
총 4줄의 수행코드로 이뤄져 있다.
1 번째 줄은 딱 1번만 실행된다.
2 번째 줄은 입력값 정수배열 inputs 의 길이(N) + 1 만큼 실행된다. ( inputs.length(N) + 1 )
=> +1 은 for 반복문을 탈출하는 조건인 inputs.length(N) + 1 번 수행될때 반복문을 탈출한다.
3 번째 줄은 입력값 정수배열 inputs 의 길이 만큼(N) 실행된다
4 번째 줄은 번째 줄은 딱 1번만 실행된다.
이것을 표로 만들면
오른쪽은 cost(코드 수행 비용), time(실행 횟수) 이다.
지금 cost, time 이해할려고 하지마라. 그냥 쭉 내려서 계속 읽어라.
각 줄의 cost x time 을 모두 더하면
aN + b 같은 변수와 상수로 조합된 실행횟수 식이 나오게 된다.
시간복잡도
⇒ 알고리즘 성능이 얼마나 좋은가?
⇒ 실행시간이 얼마나 짧은가?
⇒ 실행횟수가 얼마나 작은가?
라고 일단 생각할수 있겠다.
여기서부터가 중요한데
일반적으로 알고리즘 성능은 입력값 변수 N 이 무한하게 클때, 얼마나 빠르게 처리는가가? 핵심이다.
그래서 크게 영향을 주지 않는, 계수와 상수를 제거한다.
이렇게 계산하면 결국 변수 N 하나만 남게 되는데
이것을 점근적 표기법 이라고 한다.
최종적으로 시간복잡도 는
⇒ 알고리즘 성능이 얼마나 좋은가?
⇒ 실행시간이 얼마나 짧은가?
⇒ 실행횟수가 얼마나 작은가?
⇒ 실행횟수 식의 변수 N 이 무한하게 클때, 점근적 표기법으로 단순하게 보여지는 표현식
(같은 문제를 해결하는 코드에, 시간 보다 얼마나 더 적은 단계로 문제를 해결하는가? = 핵심은 단계 이다.)
결론
시간복잡도는, 실행횟수 식의 변수 N 이 무한하게 커지면서, 점근적 표기법으로 단순하게 보여지는 표현식
다시한번 말하지만. 같은 문제를 해결하는 코드에, 시간 보다 얼마나 더 적은 단계로 문제를 해결하는가? = 핵심은 단계 이다.
시간복잡도의 퀄리티는 아래 5단계 로 판단된다.
- Horrible : 최악이네..
- bad : 안좋아.. 개선해야해..
- Fair : 처리해야하는 양만큼 비례
- Good : 호~ 쓰기좋네
- Excellent : 어떤상황에서든지 최고다!!
'알고리즘' 카테고리의 다른 글
| 시간 복잡도(Time Complexity) - 2 (0) | 2022.10.24 |
|---|
