[자료구조] 복잡성 : 자료구조 입문

https://www.youtube.com/playlist?list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk 

Data Structures

 

Rob Edwards 교수님의 CS310 Data Structures in Java를 공부하고 정리한 내용입니다.

 

부스트 코스 자바로 구현하고 배우는 자료구조에서도 학습할 수 있습니다.

---

복잡성 소개

시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용하는데, 다음과 같은 규칙이 있다.

 

규칙 1. input >= 0

input의 크기는 0이상이고, complexity는 0이상이다.

 

규칙 2. functions do more work for more input

 

규칙 3. drop all constants

예를 들어 3n의 시간이 걸린다고 하면 n의 시간과 같다. 5n, 10n, 50n 모두 n과 같다.

n이 infinity에 가까워질 때 복잡도에 관심이 있기 때문에 상수를 생략한다.

 

규칙 4. ignore lower order terms

n^3 + n^2 + n의 경우 n과 n^2는 n^3에 비해 complexity에 크게 기여하지 않는다. n이 infinity에 가까워질 때 관심 있다는 것을 다시 생각할 것

 

규칙 5. ignore the base of logs

예를 들어 math.log(2)의 경우 자바에서 base는 e다. 만약 base가 다른 로그와 비교한다면 단지 상수값을 곱해주는 것과 같기 때문에 규칙3과 같은 맥락으로 로그의 base는 무시한다.

 

규칙 6. 등호를 사용하여 표현한다.

 

생각해보기

1) 시간 복잡도가 1이거나 n인 것은 각각 무엇을 의미할까요?

시간복잡도가 1인것은 입력값과 관계없이 항상 같은 시간이 걸리는 것이고, 시간복잡도가 n인 것은 입력값에 비레하여 시간이 증가하는 것을 의미한다.

---

빅 오 표기법

출처 : YouTube Rob Edwards

Big Oh Notation을 가장 빈번하게 사용한다.

 

어떤 관심 있는 알고리즘이 그래프 상에서 비교하고자 하는 알고리즘보다 아래에 있다면, 같은 일을 하는데 더 빠른 알고리즘이고, 반대로 그래프 상에서 비교하고자 하는 알고리즘보다 위에 있다면, 더 느린 알고리즘이다.

 

Big O Complexity : same or faster ( N ≥ )

Theta Complexity : same rate ( N = )

Big Omega Complexity : same or slower ( N ≤ )

Little O Complexity : faster but not the same ( N > )

Little Omega Complexity : slower but not the same ( N < )

 

빅 오 표기법의 약자의 의미는

https://softwareengineering.stackexchange.com/questions/107976/what-is-o-in-big-o

What is O in Big O?

위 링크에서 찾아볼 수 있다.

 

생각해보기

1) 빅 오 표기법을 각각 부등호에 대응하면 어떤 것인가요? 위에 표기

2) 빅 오 표기법의 O는 무엇의 약자일까요?

위 링크에서 Order of complexity로 관습적으로 사용하지만, 어짜피 모두가 의미를 알고 있기 때문에 굳이 정확히 무엇의 약자인지 논하는 것이 이를 이해하는데 도움을 주지않는 다는 의견도 있었다.

---

빅 오 표기법 예시

 

문제 1)

n ^ (4/3) = O(nlogn)

 

원래는 로피탈의 규칙을 사용하지만 적당히 큰 수를 대입해서 비교할 수 있다. n이 작을 때는 고려하지 않고 무한에 가까울 때를 고려하는데 1000을 대입한다고 하면 1000 ^( 4/3 ) 은 대략 10000이고 1000log(1000)은 대략 3000이다.

 

답 : False

 

문제 2)

3n^3 + 4n^2 + 5n + 6 = theta(n^3)

 

계수와 lower term은 무시하고 같은 rate이므로 true다.

 

답 : true

 

문제 3)

n(n-1)/2 = O(n^2)

 

마찬가지로 lower term과 계수는 무시하므로 true다.

 

답 : true

 

문제 4)

2^n = omega(n)

 

2 ^ n이 n 보다 훨씬 시간이 많이 들고 느린 알고리즘이기 때문에 true이다.

 

답 : true

 

문제 5)

n^3 = O(n^2)

 

n^3이 n^2보다 느린 알고리즘이기 때문에 false이다.

 

답 : false

 

문제 6)

n^2 = O(n^3)

 

n^2이 n^3보다 빠른 알고리즘이기 때문에 true이다.

 

답 : true

 

 

생각해보기

1) 문제 1에서 n=1을 대입하면 어떻게 되나요? 적당히 큰 수를 대입해야 하는 이유는 무엇인가요?

알고리즘의 복잡도를 게산하는 이유는 많은 데이터를 처리할 때, 어떤 알고리즘이냐에 따라 데이터가 늘어날수록 시간 차이가 더 심해진다는 것이다. 작은 데이터에서는 굳이 고려할 필요가 없는 것이고 애초에 무한에 가까운 데이터를 처리하는데 시간이 얼마나 소요될지 관심있는 것이기 때문에 큰 수를 고려해야 의미있는 복잡도 계산을 할 수 있다.