자료구조와 알고리즘 개요, 시간 복잡도, 빅오(Big-O) 표기법

프로그램

• 프로그램은 자료구조와 알고리즘으로 구성됨
• 데이터를 어떻게 저장할지(자료구조), 어떻게 처리할지(알고리즘)를 정의함

 

 

 

자료구조

: 데이터가 어떤 구조로 저장되고, 어떻게 사용되는 지를 나타내는 형식

• 가장 단순한 자료구조: 변수
  • 숫자나 문자열 등 하나의 값을 저장
  • 변수명을 통해 접근
• 배열
  • 데이터를 연속적으로 저장
  • 각 값을 인덱스를 통해 접근

 

 

 

알고리즘

: 문제를 해결하는 명확한 방법

• 자료구조에 따라 알고리즘의 성능이 달라짐
• 같은 문제라도 어떤 자료구조를 사용하느냐에 따라 효율이 다름

 

 

 

---

시간 복잡도(Time Complexity)

: 알고리즘이 문제를 해결하는 데 걸리는 시간

• 알고리즘을 평가할 때는 시간을 측정하는 방식이 아닌 코드에서 성능에 영향을 많이 주는 부분을 찾아 실행 시간을 예측함
  → 코드에서 성능에 영향을 많이 주는 부분 = 반복문
  → 반복문이 많을수록 시간이 오래 걸림
  ⇒ 특정 알고리즘의 성능을 평가할 때는 해당 알고리즘의 반복문을 보고 성능을 평가함

 

 

시간 복잡도의 분류

• 찾는 데이터가 배열의 어디에 있는 지에 따라 성능이 달라짐
• 보통 최악의 경우인 Big-O를 기준으로 성능을 평가함

 

최선의 경우, 데이터를 한 번에 찾음 ⇒ Big-Ω (Ω(n))

• 찾는 데이터가 배열의 첫 번째 원소에 있다면(최선) 
  → 1번 만에 찾음

 

 

평균의 경우, 배열의 길이 중간 만큼 걸림 ⇒ Big-Θ (Θ(n))

• 찾는 데이터가 배열의 중간 위치에 있다면(평균)
  → 배열의 중간에서 찾을 수 있음

 

 

최악의 경우, 끝까지 다 찾아야 하는 경우 ⇒ Big-O (O(n))

• 찾는 데이터가 배열의 마지막 원소에 있다면(최악) 
  → 배열의 길이만큼 순회해야 찾을 수 있음

 

 

 

예시 - 배열에서 특정 값을 찾는 경우

 

배열 [1, 3, 5, 7]에서 숫자 5를 찾는다.

• 왼쪽부터 오른쪽으로 순차적으로 탐색한다.
• 5는 인덱스 2(세 번째 위치)에 있으므로 3번째 위치에서 찾는다.

 

시간 복잡도 분석

• 최악의 경우: 찾는 값이 배열의 마지막에 있을 때 → 배열 전체를 순회해야 함 → O(n)
• 최선의 경우: 찾는 값이 배열의 첫 번째 원소일 때 → Ω(1)
• 평균적인 경우: 값이 중간쯤에 있을 때 → Θ(n)

➡ 따라서 이 탐색 알고리즘의 시간 복잡도는 최악의 경우 O(n)이다.

 

 

 

---

빅오(Big-O) 표기법

: 해당 알고리즘의 입력이 늘어날 때, 계산량이 얼마나 늘어나는지 표현하는 방법

• 성능을 정확하게는 표현하지 못함
• 표기 원칙
  1. 가장 큰 영향을 미치는 항만 표기한다.
     
     • n² + 2n + 100 → O(n²)
  2. 상수는 제거한다
     
     • 3n² + 100n → O(n²)
       

       

       
       

 

선형 시간 알고리즘: O(n)

• 데이터가 많아지면, 그에 비례해서 계산량이 많아짐
• 예) 배열 전체를 순회하며 값을 찾는 경우
  

  

  
  
  

 

상수 시간 알고리즘: O(1)

• 데이터 양에 상관없이 처리 시간이 항상 일정함
• 입력 크기에 상관없이 1번만 계산하든 100번 계산하든 시간 복잡도는 O(1)
  → 핵심은 입력 크기에 따라 계산량이 달라지는가