- Today
- Total
Recent Posts
Recent Comments
Archives
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 코딩문제
- 자료구조 강의
- 자료구조
- gdrive
- 채용문제
- 파이썬3
- c언어
- 파이썬 알고리즘
- 파이썬 강의
- 기말시험
- 파이썬 자료구조
- python data structure
- 파이썬활용
- 프로그래밍
- 면접 파이썬
- 코딩시험
- Crawling
- 파이썬 강좌
- 알고리즘 강좌
- 대학시험
- 파이썬 입문
- python 중간고사
- 쉬운 파이썬
- 알고리즘
- 크롤링
- 셀레니움
- 알고리즘 강의
- 파이썬
- selenium
- 중간시험
Notice
반원 블로그
03d. 시간 복잡도 계산과 빅오(Big-Oh) 표기법 본문
알고리즘 분석에 인정되는 연산
연산 횟수에 카운트 되는 기본 연산은 다음과 같습니다.
- 변수에 값을 배정
- 함수를 호출
- 산술연산(더하기, 빼기, 곱하기, 나누기 등)
- 비교연산(크다, 작다, 같다, 아니다)
- 인덱싱을 이용한 코드
- 반환(return)
- 참조 또는 내부 속성 접근
시간 복잡도 T(n) 계산
만일 n개의 데이터서 각각 기본연산 3번씩한다면 시간 복잡도는 다음과 같습니다.
T(n) = n * 3 = 3n
빅오(Big-Oh) 표기법
경우에 따라서 정확한 시간복잡도를 구하는 게 어려울 수 있습니다. 이에 가장 차수가 높은 것만 남겨놓아 비교하는 빅오 표기법이 있습니다. 차수가 높은 n이 처리할 데이터가 많을수록 그 차이가 크기 때문입니다.
$T(n) = n^5+n^3+n+5$ => $O(n) = n^5 $
빅오 표기법은 식을 단순화하는 것보다 "알고리즘을 수행시간에 따른 성능 기준을 나누기 쉽다"에 의미가 있습니다. 정확한 식을 모르더라도 "이 알고리즘의 성능은 여기 정도다"라고 판단할 수 있는거죠. 다음은 기준으로 자주 사용되는 빅오 표기입니다.
- $O(1)$ : 상수시간(Constant Time)
- $O(logn)$ : 로그시간 또는 대수시간(Logarithmic)
- $O(n)$ : 선형시간(Linear)
- $O(nlogn)$ : 로그선형시간(Log-Linear)
- $O(n^2)$ : 제곱시간(Quadratic)
- $O(n^3)$ = 세제곱시간(Cubic)
- $O(2^n)$ = 지수시간(Exponential)
직접 그래프는 https://www.desmos.com/calculator 에서 그려볼 수 있습니다.
그런데 $2^n$을 제외하면 초반부에 $O(1)$보다 더 좋은 성능처럼 그래프에 나오지만, 실제로 데이터 처리는 개수가 1부터 시작이므로 의미가 없습니다.
위키독스 연재 : https://wikidocs.net/book/2868
'2018~ > 파이썬 자료구조 알고리즘' 카테고리의 다른 글
03c. 속도 기준 알고리즘 비교 (0) | 2019.05.09 |
---|---|
03b. 성능 분석의 기준 (0) | 2019.05.08 |
03. 성능분석 기법 (0) | 2019.05.07 |
03a.자료구조와 알고리즘 (0) | 2019.05.07 |
02c. 이중 연결 리스트(doubly linked list) - v. 탐색 (0) | 2019.05.06 |
02c. 이중 연결 리스트(doubly linked list) - iv. 삭제 (0) | 2019.05.05 |
02c. 이중 연결 리스트(doubly linked list) - iii. 출력 (0) | 2019.05.04 |
02c. 이중 연결 리스트(doubly linked list) - ii. 삽입 (0) | 2019.05.03 |
Comments