[자료구조] 복잡도(시간 복잡도, 공간 복잡도), 빅오 표기법

자료구조 Data structure

: 효율적으로 데이터를 관리, 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합

 

알고리즘 Algorithm

: 표현 및 저장된 데이터를 대상으로 하는 문제의 해결 방법

 

➡️ 자료구조가 결정되어야 효율적인 알고리즘을 결정할 수 있다.

---

복잡도 Complexity

어떤 알고리즘이 효율적인지를 판단하는 척도

 

1️⃣속도, 2️⃣메모리 사용량

• 속도에 해당하는 알고리즘 수행시간 분석결과 ➡️ 시간복잡도
• 메모리 사용량에 해당하는 분석결과 ➡️ 공간 복잡도

 

⏰시간 복잡도 Time Complexity

문제를 해결하는 데 걸리는 시간과 입력의 함수 관계

➡️ 어떠한 알고리즘 로직이 얼마나 오랜 시간이 걸리는지

 

💾 공간 복잡도 Space Complexity

프로그램의 실행과 완료에 필요한 자원 공간의 양

➡️ 얼마나 많은 공간(메모리)가 필요한지

 

• 알고리즘 실행에 필요한 공간
  
  • 고정 공간: 알고리즘과 무관한 공간
    - 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간
  • 가변 공간: 알고리즘과 밀접한 공간
    - 문제 해결을 위해 알고리즘이 필요로 하는 공간, 변수 저장 공간, 코드 실행 시 재귀 등으로 동적 생성되는 공간

---

빅오 표기법 Big-O

입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것

T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.

→ 가장 많이 영향을 끼치는 항의 상수 인자를 빼고 나머지 항을 없애는 것

 

➡️ 데이터 수의 증가에 따른 연산 횟수의 증가 형태를 표현한 것

데이터 수에 따른 시간복잡도 표현 - O(n^2) 보다 O(n), O(logn), O(1)을 지향해야 한다

 

• 대표적인 빅-오
  • O(1) : 상수형 빅-오 : 데이터 수에 상관없이 연산 횟수가 고정인 유형의 알고리즘
  • O(logN) : 로그형 빅-오 : 데이터 수의 증가율에 비해 연산 횟수의 증가율이 훨씬 낮은 알고리즘
  • O(N) : 선형 빅-오 : 데이터 수와 연산 횟수가 비례하는 알고리즘
  • O(NlogN) : 선형로그형 빅-오 : 데이터 수가 2배 증가할 때 연산 횟수는 2배를 조금 넘게 증가하는 알고리즘
  • O(N^2) : 데이터 수의 제곱에 해당하는 연산 횟수를 요구하는 알고리즘 → 데이터 수 多경우 사용하기 부적절
  • O(N^3) : 데이터 수의 세 제곱에 해당하는 연산 횟수를 요구하는 알고리즘 → 데이터 수 多경우 사용하기 부적절
  • O(2^N) : 지수형 빅-오 : 보통 알고리즘 문제에서 사용하기 매우 부적절

➡️ 성능(수행시간, 연산횟수)의 대소 O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(N^3) < O(2^N)