시간 복잡도

🔑Table of Contents

1. 알고리즘 분석
2. RAM
3. 시간복잡도
4. 공간복잡도
5. O(빅오),Ω(오메가),Θ(세타)
6. O,Ω,Θ 표기 연습
7.  시간 복잡도 분류

---

📌알고리즘 분석 

주어진 문제에 대한 알고리즘을 설계한 후 다음을 분석한다 

- 정확성 : 가능한 입력에 대해서 항상 옳은 답을 출력하는가?

- 자원 : 얼마나 많은 자원을 사용하는가? 

※ 가장 중요한 자원 = 알고리즘 실행시간, 알고리즘을 실행하는데 필요한 메모리 양 

 

📌 RAM (Random Access Machine)

명령어가 순차적으로 수행되는 보통의 컴퓨터에 기반을 두고 있음 

1. 간단한 명령어를 가짐(사칙연산, 비교, 치환)

2. 정수를 고정된 길이로 표현 (예 : 32비트) → 덧셈이면 크기 상관없이 다 똑같은 시간이 걸림(정수 보통 4바이트)

3. 무한한 양의 메모리를 가지며 단위시간에 메모리에 접근할 수 있다고 가정함

※알고리즘 실행시간 : RAM 모델 상에서 실행 시 필요한 기본 연산(명령어)의 개수 

 

📌시간복잡도

입력의 개수가 n개일때 알고리즘의 실행시간을 n에 대한 함수로 표현한다 

(입력의 크기가 n으로 같더라도 알고리즘의 실행시간이 다를 수 있음)

• 최악의 경우 시간 복잡도는 입력의 개수가 n인 모든 가능한 입력에 대한 최대 실행시간을 말한다 → 같거나 짧은시간
• 평균 시간 복잡도는 크기 n인 모든 입력에 대한 실행 시간의 평균을 말한다

즉, 시간 복잡도 = 최악의 경우 시간복잡도 

시간복잡도는 시간복잡도의 상계와 하계를 말하는것이 간결하다 → O(n²)빅오 : 최악의 경우 이정도는 보장한다  

                                                                                                       →Ω(n²) 빅오메가 : 최선의 경우

※ 버블정렬  : 서로 이웃한 데이터들을 비교하며 가장 큰 데이터들을 가장 뒤로 보내며 정렬하는 방식

 

📌공간복잡도

알고리즘이 사용하는 메모리 양을 입력 크기n에 대한 함수로 표현한다

• 최악의 경우 공간복잡도
• 평균 공간복잡도

 

📌 O(빅오),Ω,Θ(세타)

    • 상수 c와 n0가 존재하여 n ≥ n₀ 인 모든 n에 대하여 T(n) ≤ c · f(n)을 만족하면 T(n) = O(f(n)) 이라고 한다   

       → 걸리는 시간(실행횟수?)

    • 상수 c와 n0가 존재하여 n ≥ n₀ 인 모든 n에 대하여 T(n) ≥  c · f(n)을 만족하면 T(n) = Ω(f(n)) 이라고 한다  

    • T(n) = O(f(n)) 이고 T(n) = Ω(f(n))이면 T(n) = Θ(f(n))이라고 한다 

 

c: 어떤 상수 , n₀ : 충분히 큰 n

 

📌 O,Ω,Θ 표기 연습

T(n) = O(f(n))이라는 것은 정의에 의하면 n이 어떤 지점 n₀ 보다 커지면 T(n)은 항상 f(n)의 상수배보다 같거나 작다 

T(n) = 100n, f(n) = n²인 경우에 n₀ = 100, c = 1이라고 두면 n ≥ 100인 모든 n에 대해 100n ≤ n²이므로 T(n) = O(n²)이 된다 

 

• 3n² - 100n + 6 = O(n²)
• 3n² - 100n + 6 = O(n³)
• 3n² - 100n + 6 ≠ O(n)
• 3n² - 100n + 6 =  Ω (n²)
• 3n² - 100n + 6 ≠  Ω (n³ )
• 3n² - 100n + 6 =  Ω (n)
• 3n² - 100n + 6 =  Θ(n²)
• 3n² - 100n + 6 ≠  Θ(n³ )
• 3n² - 100n + 6 ≠  Θ(n)

📌 시간 복잡도 분류

• 다항시간
  • O(1)
  • O(log n)
  • O(루트 n)
  • O(n)
  • O(n 루트 n)
  • O(n²)
  • O(n³)
• 지수시간
  • O(2ⁿ), O(n2ⁿ), O(n!), ...