복잡도 : 알고리즘의 성능을 나타내는 척도
복잡도 = 시간 복잡도 + 공간 복잡도
시간 복잡도 : 특정 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지
공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지
동일 기능 수행하는 알고리즘이 있다면 일반적으로 복잡도 낮을 수록 좋은 알고리즘
효율적 알고리즘 : 시간 복잡도와 공간 복잡도는 거래 관계
메모리를 더 사용하는 대신 반복되는 연산 생략/ 더 많은 정보 관리하며 계산 복잡도 줄임
시간 복잡도 = 시간 제한
Big O 표시 : 가장 빠르게 증가하는 항 만 고려하기
단순한 이중 반복문의 경우 N * N 이겠지만 내부적 함수 호출이 있다면 더 늘어난다.
일반적으로 N^3 을 넘어가면 문제 풀이 때 못쓴다.
연산 횟수가 10억을 넘으면( N이 5000을 넘으면) 못씀
시간 복잡도 분석이 문제 풀이의 핵심- 문제의 조건을 보고 얼마나 효율적인 알고리즘을 짜야 하는지 파악함
N : 1000만, 제한시간 1초
최악의 경우 O(N) 으로작성해야
시간 제한 1초 기준
N : 500 -> N3
N : 2000 -> N2
N : 100000 -> NlogN
N : 10000000 : N
으로 작성해야 풀이가 가능
공간 복잡도 = 메모리 제한
코테는 대부분 리스트를 사용하는데, int 가 4B인거 생각하면
128 MB는 데이터가 1000만 단위가 넘어가지 않도록 설계 해야 한다
선택 정렬은 30초단위라면 기본 정렬 라이브러리는 1초도 안걸린다.
-> 설계한 알고리즘 성능 확인이 필요