복잡도란?
알고리즘의 성능을 나타내는 척도
시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미
공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
복잡도를 측정함으로써 시간복잡도에서는 알고리즘에 의해 필요한 연산의 횟수를,
공간복잡도에서는 사용되는 메모리의 양을 계산할 수 있다.
일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.
시간 복잡도
시간 복잡도 표현할 때는 빅오 Big-O 표기법을 사용
빅오 표기법이란?
:
O(N)
연산횟수 N번 반복문 돌리는 경우
O(1)
연산횟수 1
O(N²)
데이터 개수가 N개일 때, 2중 반복문 돌리는 경우
시간제한이 1초인 문제에 대한 시간복잡도 설계 예시
- N의 범위 500 인 경우 : O(N³) 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위 2,000 인 경우 : O(N²) 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위 100,000 인 경우 : O(NlogN) 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위 10,000,000 인 경우 : O(N) 알고리즘을 설계하면 문제를 풀 수 있다.
시간복잡도.. 듣기는 많이 들었지만 설명 봐도 뭔 소린지도 잘 모르겠고 어려워서 회피했었는데
드디어 내가 시간복잡도에 관심을 가지게 되는 날이 오다니..!
그래도 필요성이 생겨서 찾아봐서 그런지 예전보다는 좀 더 재밌고 이해도 조금씩 되고 있는 듯 하다.
아직 갈길이 멀지만.. 빠이팅하쟈
참고 : https://jeleedev.tistory.com/70
각 자료구조 및 알고리즘의 빅오 표기법
https://www.bigocheatsheet.com/
Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell
Know Thy Complexities! Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting t
www.bigocheatsheet.com
빅오 표기법 연습문제
https://www.geeksforgeeks.org/practice-questions-time-complexity-analysis/
Practice Questions on Time Complexity Analysis - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
'Algorithm > 자료구조 알고리즘' 카테고리의 다른 글
| [자료구조] 스택 / 큐 (+ Swift 구현) (0) | 2022.11.11 |
|---|---|
| [알고리즘] 동적계획법 DP(Dynamic Programming) (1) | 2022.11.11 |
| [알고리즘] 완전탐색 브루트 포스 Brute Force (0) | 2022.04.28 |
| [알고리즘] 해시 Hash (0) | 2022.04.28 |
| [알고리즘] 재귀 Recursion (0) | 2022.04.26 |