알고리즘 Orientation

Goal

• 알고리즘이란?
• 알고리즘 성능과 복잡도에 대한 이해
• 시간 복잡도와 Big-O 표기법에 대한 이해

---

알고리즘

어떤 문제를 해결하기 위한 일련의 절차나 방법을 표현한 것

 

알고리즘 성능 분석

일반적으로 효율적인 알고리즘이라고 하면 실행 시간이 짧고 컴퓨터 자원을 적게 사용하는 알고리즘이다.

=> 알고리즘 성능 측면에서 일반적으로 시간과 자원사용을 중요시하기 때문

 

복잡도(Complexity)

알고리즘을 직접 구현하지 않고 대략적인 효율성을 분석하는데 사용하는 방법

 

종류

- 시간 복잡도(Time Complexity)

- 공간 복잡도(Space Complexity)

 

복잡도 표현 방법 : 주로 점근적 표기법(Asymtotic Notation)을 사용 (주로 Big-O Notation이 사용됨)

=> 가장 좋은 분석법도, 유일한 분석법도 아니지만 실행 환경에 비의존적이기 때문에 객관적인 기준이 될 수 있음

 

복잡도 판단 기준의 예

1. 최악의 경우(worst case) - 가장 많이 사용됨
2. 최선의 경우(best case) - 잘 사용되지 않음
3. 평균적인 경우(average case)

복잡도 함수 : 입력에 따른 복잡도 관계를 표현한 함수

=> ex) 시간 복잡도 함수 : 입력이 주어졌을 때 문제를 해결하는데 까지 걸리는 시간을 함수 관계로 표현한 것

 

복잡도 표기법들의 예

• 빅 오 표기법(Big-O notation) - 상한적 접근 => 최악의 경우 판단
• 스몰 오 표기법
• 빅 오메가(Ω) 표기법 - 하한 접근 => 최선의 경우 판단
• 스몰 오메가(ω) 표기법
• 빅 세타(Θ) 표기법 - 상한/하한 접근 => 평균적인 경우 판단

---

Big-O 표기법과 시간복잡도 계산

Big-O표기법 (점근적 상한 - Asymptotic Upper Bound)

함수 f(n), g(n)이 있을 때, n > n0 를 만족하는 모든 n에 대해 | f(n) | <= c * | g(n) | 을 만족하는 양의 실수 c와 실수 n0가 존재하면 f(n) = O(g(n))이다.

 

Big-O 표기법으로 시간 복잡도 함수 표시

• 상수는 버린다 => ex) O(3N^2) = O(N^2) , O(5) = O(1)
• 같은 변수를 가진 항이 있을 때 큰 항을 뺀 나머지 항은 버린다. => ex) O(N^2 +NlgN) = O(N^2)
• 변수가 다른 항은 냅둔다 => ex) O(N^2 + M)

 

[설명]

일정 값(n0)을 넘어가면 항상 비교 함수보다 같거나 큰값을 가진다. => 비교 함수를 통해 최저 기준 판단 가능

아무리 못해도 ~보단 (같거나)크다.

 

참고)

흔히, Big-O Notation이 상한을 나타낸다는 사실을 통해 알고리즘의 최악의 수행 시간을 알아냈다고 착각하는 일이 있는데, 특별히 최악의 시간과는 상관이 없다.

즉, 최악을 나타낼 때도 쓸 수 있지만, Big-O표기법을 쓴다고 무조건 최악을 나타내는 것은 아니다.

 

한 예로, 퀵 정렬의 경우 평균적인 시간복잡도와 최악의 시간 복잡도를 둘 다 O표기법으로 표시할 수 있다.

평균 : O(nlgn)

최악 : O($n^2$)

 

예시)

[1] f(n) = 5 이면 O(1)이다
n0 = 1, c = 10일 때(c는 양의 실수, n0은 실수), n > 1 에 대하여 5 <= 10 * 1 이 되기 때문이다.

[2] f(n) = 3+100 이면 f(n) = O(𝑛^2)이다.

n0 = 2, c = 3 일 때, n >= 에 대해 2 * 2 + 1 < 3 * 2 가 되기 때문이다.

 

실행 시간 순서 : O(1) < O(log n) < O(n) < O(n log n) < O(𝑛^2) < O(2^𝑛) < O(n!)

---

빅오 표기법 이외의 표기법들 (참고만)

Big Omega(Ω) 표기법 (점근적 하한 - Asymptotic Lower Bound)

함수 f(n), g(n)이 있을 때, n > n0 를 만족하는 모든 n에 대해 | f(n) | >= c * | g(n) | 을 만족하는 양의 실수 c와 실수 n0가 존재하면 f(n) = Ω (g(n)) 이다.

 

[설명]

일정 값(n0)을 넘어가면 항상 비교 함수보다 같거나 작은값을 가진다. => 비교함수를 통해 최고 기준 판단 가능

잘하면 ~까지도 가능하다.

 

예시)

[1] f(n) = 2n + 1 이면 Ω(n)이다 
n0 = 1, c = 1일 때(c는 양의 실수, n0은 실수), n > 1 에 대하여 2n + 1 >= n 이 되기 때문이다.

 

 

Big Theta(Θ) 표기법 – 점근적 상한과 하한의 교집합 (Asymptotic Tighter Bound)

함수 f(n), g(n)이 있을 때, n > n0 를 만족하는 모든 n에 대해 c1 * | g(n) |  <= | f(n) | <= c2 * | g(n) | 을 만족하는 양의 실수 c1,c2와 실수 n0가 존재하면 f(n) = Θ (g(n)) 이다. => f(n) = O(g(n)) 이고 f(n) = Ω (g(n)) 인 경우를 f(n) = Θ (g(n)) 이라고 한다. (빅오, 빅 오메가 합친 것)

 

[설명]

빅오 표기법과 빅 오메가 공통 부분(교집합)

일정 값(n0)을 넘어가면 항상 두 비교 함수보다 사이값을 가진다. => 두 비교함수를 통해 최고, 최저 판단 가능

못해도 ~, 잘하면 ~ => 너는 내 함수 안에 존재해~

 

예시)

[1] f(n) = 2n + 1 이면 Θ (n)이다 
n0 = 1, c1 = 1, c2 = 3일 때(c는 양의 실수, n0은 실수), n > 1 에 대하여 n <= 2n + 1 <= 3n 이 되기 때문이다. 

 

[참고]

https://ratsgo.github.io/data%20structure&algorithm/2017/09/13/asymptotic/

https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95