📕 시간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미

📜 빅오 표기법

가장 빠르게 증가하는 항만을 고려하는 표기법

• 3N^3 + 2N^2 + 300000000000

• 시간 복잡도는 O(N^3)

• N이 1000일 때의 연산 횟수
  O(N) -> 1000
  O(NlogN) -> 10,000
  O(N^2) -> 1,000,000
  O(N^3) -> 1,000,000,000

📜 시간 복잡도 설계

시간 제한 1초로 가정

N의 범위가 500 -> O(N^3) 설계
N의 범위가 2,000 -> O(N^2) 설계
N의 범위가 100,000 -> O(NlogN) 설계
N의 범위가 10,000,000 -> O(N) 설계

📕 공간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미

• 코딩 테스트에서는 대부분 배열로 풀어야한다.
• 이유는 다수의 데이터에 대해서 효율적인 처리를 요구하기 때문이다.

📕 코딩 테스트 문제 푸는 순서

1. 지문읽기 및 컴퓨터 사고
2. 시간복잡도 분석(중요)
3. 아이디어 찾기
4. 코드 설계

📕 출제 유형

어떤 유형에 시간을 많이 투자해야하는지 알자

참조

https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/
.
https://www.hanbit.co.kr/media/channel/view.html?cms_code=CMS7793635735