[Coding Test] inflearn(1)

1. 시간복잡도

• 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도
• 시간 복잡도란 크기 n의 모든 입력에 대해 걸리는 최대의 시간(최악의 경우)
• 시간 개념보다는 알고리즘이 실행될 때 동작하는 연산의 횟수가 몇번인지 세는것
• 성능평가 유형으로 best, average, worst 가 있는데 이 중 최악의 경우로 알고리즘 성능을 평가

2. 공간복잡도

• 알고리즘을 사용할 때 얼만큼의 메모리를 사용했느냐를 분석, 주로 배열의 크기로 결정

3. 시간복잡도의 표기법

• BigΩ(빅오메가) (Best case)
  - 빅오메가는 최선의 실행시간, 가장 빠른 케이스를 말한다.
  - 어떤 식의 최고 차수의 하한을 의미
• Big𝚯(빅세타) (Average case)
  - 빅세타는 최선과 최악의 평균 실행시간, 평균적인 케이스
  - 빅오와 빅오메가를 모두 만족하는 교집합이다.
• BigO(빅오) (Worst case)
  - 빅오 표기법은 인수가 특정 값이나 무한대로 향하는 경향이 있을 때 함수의 제한 동작을 설명하는 수학적 표기법
  - 컴퓨터과학에서 BigO는 입력 크기가 커짐에 따라 실행시간 또는 공간 요구사항이 어떻게 증가하는지에 따라 알고리즘을 분류하는데 사용
  - 최악의 실행시간, 가장 느린 케이스를 나타냄
  - 상한선을 기준으로 하여 모든 경우의 수를 포함
  - 영향력 없는 계수와 낮은 차수의 항은 무시 -> ex) O(2N^2 + N) = O(N^2)
  - 상수는 무시되거나 1로 통일 -> ex) O(7) = O(1)

4. 시간 표기법

성능비교 : (빠름) O(1)<O(logN)<O(N)<O(NlogN)<(N^2)O(2^N) (느림)

상수 시간 / O(1)

• 입력 자료의 수와 상관없이 언제나 일정한 실행시간을 갖는 알고리즘
• 문제를 해결하는데 오직 한 단계만 처리
  - index를 통한 탐색, key 값으로 value를 탐색하는 경우

로그 시간 / O(logN)

• 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
• O(log n)은 한 번 쪼갠 횟수만 계산하는 것, O(nlogn)은 쪼갠 횟수의 모든 그룹을 계산하는 것
  - O(logN) 이진 탐색으로 값을 찾을때
  - O(NlogN) 머지소트일때 모든 부분을 탐색해야함

선형 시간/ O(N)

• 입력값이 증가함에 따라 시간또한 같은 비율로 증가하는것
  - 배열을 for loop를 사용하여 탐색

2차 시간/O(N^2)

• N개의 값을 N번 대입해야 하는 수행시간을 의미
  - 입력N에 대한 이중 for문, 삽입정렬,거품정렬

지수 시간/ O(2^N)

• 기하급수적 복잡도라 부르며 상수의 n제곱만큼 늘어나는 수행시간
  - 피보나치수열, 재귀탐색
  

일반적으로 시간 복잡도가 작은 알고리즘일수록 실행 시간이 짧아지므로 효율적이다.
따라서, 시간 복잡도를 고려하여 알고리즘을 설계하고 최적화하는 것이 중요하다.