복잡도(Complexity)
1. 알고리즘 성능을 나타내는 척도
2. 시간 복잡도(Time Complexity)
- 알고리즘의 필요 연산 횟수
- 빅오(Big-O Notation) 표기법을 통해 나타낸다.
3. 공간 복잡도(Space Complexity)
- 알고리즘의 필요 메모리 (MB단위)
4. 시간 복잡도와 공간 복잡도는 Trade-off 관계
- 메모리를 많이사용하면 시간 복잡도를 줄일 수 있다
- 반비례관계
시간 복잡도의 속도를 비교하면 위의 사진과 같다.
빠름 O(1) < O(log N) < O(N) < (O N log N) < O(N^2) < O(2^N) 느림
Big-O 이외에도 Big-Omega 와 Big-Theta Notaion 등이 존재한다.
Big-O notation 은 상한선을 기준으로 표기하지만,
Big-Omega 는 알고리즘 효율을 하한선을 기준으로 하고
Big-Thta는 상한선과 하한선의 사이를 기준으로 판단한다.
참고
https://haeunyah.tistory.com/60
[Algorithms] 시간복잡도 (Big-O Notation) 란?
✨ 시간복잡도 알고리즘의 로직을 코드로 구현할 때, 입력값에 따라 출력값을 내는데 걸리는 시간의 비율을 의미한다. 시간 복잡도는 보통 Big-O Notation (Big-O 표기법) 을 활용하여 나타낸다. Big-O N
haeunyah.tistory.com
GrepIU
www.grepiu.com
[Java] 컬렉션들의 시간복잡도 (Collection Big-O)
자바를 이용해서 알고리즘 문제를 풀거나 큰 사이즈의 데이터를 다룰 때, 컬렉션들의 정확한 시간복잡도(Big-O)를 알고 사용하는 것이 중요하다. 자칫 불필요하게 느린 컬렉션이나 메소드를 사용
hbase.tistory.com
https://soft.plusblog.co.kr/74
자바 컬렉션(Java Collection)들의 Big O (시간 복잡도, Time Complexity)
자바는 다양한 컬렉션 타입들을 제공한다. 이 컬렉션 타입들은 내부 구현에 따라 다양한 시간 복잡도를 갖는데, 이 특징을 잘 알고 사용해야 불필요한 성능저하를 피할 수 있다. List Add Remove Get C
soft.plusblog.co.kr
'Knowledge > CS' 카테고리의 다른 글
| 컴파일과 인터프린터 (0) | 2022.08.17 |
|---|---|
| 해시(Hash)란 무엇인가? (0) | 2022.08.16 |
| block I/O VS non-block I/O 개념 (0) | 2022.08.11 |
| 상속과 구현의 차이 (0) | 2022.08.09 |
| 데이터베이스와 파일처리 시스템의 차이 (0) | 2022.08.09 |
댓글