티스토리 뷰
1부터 100까지의 합을 구해보자
1+2+3+...+99+100 을 하면 100번 연산을 해야한다.
(100*(1+100))/2 을 하면 갯수에 상관없이 3번만 연산을 하면된다.
당연히 아래 부분이 효율성이 높다고 할 수 있다.
효율성에는 공간적 효율성과 시간적 효율성이 있다.
공간적 효율성은 얼마나 많은 메모리 공간을 요구하는지를 나타내고
시간적 효육성은 얼마나 많은 시간을 요구하는지를 나타낸다
이 때 복잡도(complexity)가 높을 수록 효율성이 저하된다.
시간 볻잡도 분석이 하드웨어와 소프트웨어의 환경에 따라 달라진다.
따라서 객관적인 분석법이 필요하게 된다.
이때 나온 것이 복잡도의 점근적 표현이다
복잡도의 점근적 표현에는 Big-oh, big-omega, big-theta가 있다.
O(Big-oh) 의 표기
T(n): 실행시간
n은 실행 횟수
n0(처음 실행횟수) 보다 크거나 같은 모든 n에 대해서
T(n) <= c *f(n) 이면
T(n)=O(f(n))이라고 한다
(상수 c와 초기값 n0는 n과 독립적
- O-표기는 복잡도의 점근적 상한을 나타 낸다.
Ω(Big-Omega)표기
T(n) >= c*f(n)
T(n) = Ω(f(n))
- 복잡도는 점근적 하한을 의미
θ(Theta)
T(n)=O(f(n))이고 T(n) = Ω(f(n))일 때
T(n) = θ(f(n))이 성립한다.
c1 * f(n) <= T(n) <= c2 * f(n)이 되는 c1, c2, n0가 존재 할 때만
T(n) = θ(f(n))이라고 한다. Ω <= θ <= O
'알고리즘 > 알고리즘 종류' 카테고리의 다른 글
엔디안(Endianness) (0) | 2020.05.14 |
---|---|
비트 연산 (0) | 2020.05.12 |
[python] 선택정렬(Selection Sort) & 삽입정렬(Insertion Sort) (0) | 2020.04.24 |
[python] BFS 응용 (0) | 2020.04.12 |
[python] BFS 문제 풀기 (0) | 2020.04.10 |
- Total
- Today
- Yesterday
- JavaScript
- mongoDB
- TensorFlow
- UserCreationForm
- 자료구조
- BFS
- DFS
- Vue
- nodejs
- logout
- Python
- 클라우데라
- vuejs
- useHistory 안됨
- useState
- Deque
- NextJS
- typescript
- error:0308010C:digital envelope routines::unsupported
- Express
- 자연어처리
- login
- next.config.js
- nextjs autoFocus
- react autoFocus
- pandas
- read_csv
- Queue
- django
- react
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |