시간 복잡도와 공간 복잡도

시간 복잡도와 공간 복잡도

 

복잡도란, 알고리즘의 성능, 효율성을 나타내는 척도를 말함

각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시함.

 

 

알고리즘을 평가할 때 주로 수행 시간과 메모리 사용량을 기준으로 두는데, 이 중 수행 시간에 해당하는 것이 시간 복잡도이고 메모리 사용량에 해당하는 것이 공간 복잡도이다.

 

 

시간 복잡도(Time Complexity)

특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타냄.

 

 

 

공간 복잡도(Space Complexity)

프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타냄

 

 

시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단함

 

---

어떻게 하면 더 효율적으로 해결할 수 있을까?

 

해결책을 비용으로 나눈 것을 퍼포먼스라고 하고, 이 퍼포먼스를 올리기 위함

 

Solution (대전제: No Solution, no performance)
알고리즘이고 뭐고 일단 문제를 해결할 수 있는 방법을 찾아야 한다.

퍼포먼스를 올리려면, 서버 비용을 낮춰야 됨

 

- Temporal Resource 시간 자원
CPU : 겁나 빠른 계산기(CPU가 열심히 계산해서 결과를 도출하는 게 시간과 연관이 있음)

 

- Spatial Resource 공간 자원
메모리를 얼만큼 쓰는가
주 저장장치(램=메모리), 보조 저장장치(SSD, USB)
램은 SSD에 비해 100배 이상 빠름

 

 

---

★Key point1: Performance of worst case is important(최악의 경우가 중요함)

CS에서의 비용이란?
공간 복잡도, 시간 복잡도 
공간의 기술이 좋아지면서, 공간 복잡도가 크게 중요하지 않게 됨.
(중요한 건 시간의 비용이다)

 

 

★Key point2: Performace of time is important(시간이 중요함)

내 프로그램이 최악일 때, f(n)이 어디로 향할까
worst case는 n이 엄청 커질 때임(n이 무한으로 갈 때)
최악의 경우가 어디까지 도달하냐

점근적 복잡도 : 알고리즘의 성능을 나타내는 척도
주로 입력(n)의 크기가 무한히 커질 때 알고리즘의 성능이 어떻게 변하는지를 분석
즉 알고리즘의 성능은 주어진 문제의 입력 크기에 따라 달라짐

 

입력이 n이라면 성능은 f(n)이라 할 수 있음
f(n)은 입력 크기 n에 대한 알고리즘의 시간(공간) 복잡도를 나타내는 함수

 

 

★Key point3: Performace is a function of input size(인풋 사이즈가 중요함)

우리의 목표는 알고리즘의 성능이 얼마나 좋은지 가늠하고 싶을 뿐(정확한 수치 도출이 아님)
즉, 비교를 통해 짐작을 하고 싶은 거

 

 

★Key point4: Some key functions are used for standards (여러 비교 대상의 기준이 필요함)

 

f(n)의 정확한 값이 필요한 게 아니라 어떤 값과 비교했을 때 더 빠른지, 느린지 비교가 하고 싶은 것.

즉, g(n) 설정해두면 g(n)가 f(n)을 비교하여 크기를 비교할 수 있음.

---

 

빅오 "표기법": 큰 동그라미 표기법

 

> 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도) 혹은 공간 요구사항(공간 복잡도)가 어떻게 증가하는지 '분류' 혹은 '비교'하는데 유용하게 사용되는 표기법
최고 차항만을 표기, 계수는 무시 (어차피 n은 무한대로 보내니까)

 

시간복잡도는 O(n^2) : 입력값(n)에 따른 알고리즘의 점근적 추이가 n^2 함수의 모양처럼 올라감
== 입력값(n)에 따른 알고리즘의 실행시간의 추이가 n^2처럼 생겼다

 

 

 

---

 

[★Key functions★]

 

O(1) 상수 시간 복잡도: 입력값이 아무리 커도 실행시간이 일정함 (가장 좋은 알고리즘)
>상수시간복잡도로 해시 테이블의 조회와 삽입 연산이 있음

 

O(log n)로그 시간 복잡도: 매우 큰 값에도 영향을 받지 않아서 큰 값을 다루는 학문에서 자주 쓰임 (이분 탐색)(점점 반으로 줄여서 찾음)
로그는 매우 큰 값에도 영향을 많이 받지 않음
+)배열에서 정렬이 된 경우라면 빅오는 O(log n)이 됨

 

O(n) 선형 시간 복잡도: 입력값만큼 비례해서 실행 시간에 영향을 받음(한 개의 for문 이에 해당)
> 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우
> 배열(array) 기본적으로 O(n)

 

O(n log n): 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당

-------------------------------------------------------- (▼inefficiency▼) ---------------------------------------------------------

O(n^2): 버블 정렬 같은 비효율적인 정렬 알고리즘 (중복 for문이 이에 해당)

 

O(2^n): 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당

 

O(n!): 굉장히 효율이 안 좋은 알고리즘

 

★빅오를 구할 때는, 로직 한 줄씩 모두 이해해야 구할 수 있음(즉 코드를 이해해야 됨)