[자료구조] 알고리즘 복잡도 표현 기법: 시간 복잡도
1. 알고리즘 복잡도 계산이 필요한 이유
하나의 문제를 푸는 알고리즘은 다양할 수 있음
- 정수의 절대값 구하기
- 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기
- 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기
다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함
2. 알고리즘 복잡도 계산 항목
- 시간 복잡도: 알고리즘 실행 속도
- 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈
가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함
3. 알고리즘 시간 복잡도의 주요 요소
- 반복문이 지배합니다.
마찬가지로, 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문
- 입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배함
4. 알고리즘 성능 표기법
- Big O (빅-오) 표기법: O(N)
- 알고리즘 최악의 실행 시간을 표기
- 가장 많이/일반적으로 사용함
- 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문 - Ω (오메가) 표기법: Ω(N)
- 오메가 표기법은 알고리즘 최상의 실행 시간을 표기 - Θ (세타) 표기법: Θ(N)
- 오메가 표기법은 알고리즘 평균 실행 시간을 표기
시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨
대문자 O 표기법
- 빅 오 표기법, Big-O 표기법 이라고도 부름
- O(입력)
- 입력 n 에 따라 결정되는 시간 복잡도 함수
- O(1), O( 𝑙𝑜𝑔𝑛 ), O(n), O(n 𝑙𝑜𝑔𝑛 ), O( 𝑛2 ), O( 2𝑛 ), O(n!)등으로 표기함
- 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
- 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다.
- 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기합니다.
- n이 1이든 100이든, 1000이든, 10000이든 실행을
빅 오 입력값 표기 방법
- 예:
5. 실제 알고리즘을 예로 각 알고리즘의 시간 복잡도와 빅 오 표기법 알아보기
1부터 n까지의 합을 구하는 알고리즘
시간 복잡도 구하기
- 알고리즘 1
- 입력 n에 따라 덧셈을 n번 반복해야 한다
- 시간복잡도: n, 빅 오 표기법으로는O(n) - 알고리즘 2
- 입력 n이 어떻든 간에 곱셉/덧셈/나눗셈 하면 된다 (반복문이 없다)
- 시간복잡도: 1, 빅 오 표기법으로는O(1)
참고
이후 자료구조, 알고리즘부터는 빅 오 표기법으로 성능을 계산해보면서, 빅 오 표기법과 계산방법에 익숙해지기로 하자.
💛 개인 공부 기록용 블로그입니다. 👻