👉 알고리즘 수행 시간이란
- 알고리즘 효율성 : 자원(시간) 을 얼마나 효율적으로 사용하는가. 대부분 수행시간 과 관련!
변수에 값을 할당하거나 리턴, 반복문을 돌릴 때, 함수를 호출할 때 모두 수행시간에 관여한다.
👉 알고리즘 복잡도
알고리즘의 복잡도를 나타낼 때는 점근적 표기를 쓴다.
- 점근적 표기: 입력이 충분히 클 때의 복잡도 (입력이 작으면 복잡하든 효율적이든 수행시간 차이가 별로 안 남)
표기의 예를 들면.. 2n+3 이지만 점근적 복잡도에서는 n 이라 표기!
최고차항의 차수만 중요, 나머지는 다 무시한다. (상수를 곱하든 않든 차수에 비하면 미미하기 때문)
n, nlogn, n², 2n 등이 있다.
👉 점근적 복잡도 대표적 3가지
0 (빅오) 표기
- 0(n²) : 최고차항의 차수가 n²을 넘지 않는 모든 함수의 집합
상한으로 최악의 경우의 시간 복잡도 를 나타낸다.
여기서 n²은 2차 함수를 총칭하므로 n², 3n³+2n, 5n²-7nlogn 등의 2차 함수가 다 포함되며, 2차 미만의 함수도 포함된다.
위 예시들을 전부 0(n²) 으로 표현해도 되지만 정보손실이 생긴다. 0(2¹⁰⁰) 이라 표현해도 되지만 정보 가치가 전혀 없는 표현이 되기 때문에 엄밀하게 한도를 파악하는 것이 중요하다. 정보 손실이 덜한 쪽으로 표현하자.
추가로, 정렬 알고리즘 중 하나인 버블 정렬(Bubble Sort)의 시간 복잡도가 O(n²)인 경우, n개의 원소를 정렬할 때 최악의 경우에는 비교 및 교환 연산이 n² 번 수행됩다고 이해하면 된다.
Ω (오메가) 표기
- Ω(n²): 최고차항의 차수가 n²보다 작지 않은 모든 함수의 집합을 뜻함.
하한으로 최선의 경우의 시간 복잡도 를 나타낸다.
이 알고리즘의 점근적 표기가 Ω(n²) 라면, 적어도 실행시간이 n²에 비례하는 시간이 걸린다는 거다.
알고리즘의 실행 시간이 최선의 경우에 얼마나 적게 증가하는지를 나타냄. 예를 들어, 비교 기반 정렬 알고리즘은 최선의 경우에도 모든 원소를 비교해야 하므로, 어떤 최선의 경우에도 최소한 O(n*log(n))의 시간이 걸린다. (머지 소트, 퀵 소트 등이 가지는 시간 복잡도)
Θ (세타) 표기
- Θ (n²): 최고차항의 차수가 정확히 n²인 모든 함수의 집합.
Θ 표기에는 상한과 하한이 다 포함되어 있다.
0(n³), Ω(n³) 이기도 하면, 상한과 하한이 겹치므로 Θ(n³)이기도 하다! 이런 경우에는 n³의 형태로 증가한다는 것을 알 수 있기 때문에 더 정확하게 시간복잡도의 정보를 얻을 수 있다!
그래도.. 상한과 하한이 겹치지 않거나 하나를 파악하기가 힘들다면 빅오나 오메가 표기를 쓰도록 하자.
👉 마무리
0 (빅오) : 점근적 상한 -> 최악의 성능
Ω (오메가) : 점근적 하한 -> 최선의 성능
Θ (세타) : 점근적 동일 -> 평균의 성능
'쉽게 배우는 자료구조 with파이썬' 와 인터넷 자료를 참고합니다! 간단한 정리이기 때문에.. 자세하지는 않다는점 참고해주세요.
