자료구조 - 시간복잡도

연결 리스트

스택 & 큐

체인 해시

트리

정렬

시간 복잡도

시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용합니다. 시간 복잡도에는 몇 가지 규칙이 있습니다.

• input  \geq≥  0
• functions do more work
  for more input
• drop all constants
• ignore lower order terms
• ignore the base of logs
  -  2n = O(n)2n=O(n) =>  2n \in O(n)2n∈O(n) 

규칙 1. 입력값(n)은 항상 0보다 크다.
입력값이 음수일 수는 없습니다. 그래서 복잡도는 항상 0보다 크다고 가정하고 계산

규칙 2. 함수는 많은 입력값이 있을 때 더 많은 작업.
더 많은 입력값이 주어지면 어떤 작업을 하는 데 필요한 계산이나 처리 시간이 길어진다

규칙 3. 시간 복잡도에서는 모든 상수를 삭제
만약 어떤 알고리즘의 복잡도가  3n3n 이라면 3은 고려하지 않고 복잡도는 nn  2n2n, 3n3n, 10n10n 모두 복잡도가  nn 인 알고리즘.

규칙 4. 낮은 차수의 항들은 무시.
시간 복잡도에서는  nn 과 n^2n​2​​를 비교할 때에는 항상 n^2n​2​​이 더 오래 걸리는 알고리즘이라고 판단. 그래프에서 (1,1)인 지점 전까지는  nn 이 더 오래 걸릴 수 있다는 것. 하지만 알고리즘에서는 입력값( nn )이 1보다 작은 값은 고려하지 않고 큰 값에 대해서만 생각을 하므로  nn 이 무한으로 커진 경우를 가정하고 비교.
시간 복잡도에서는 낮은 차수의 항들은 무시  n^3 + n^2 + nn​3​​+n​2​​+n 이라는 함수가 있을 때,  nn 과 n^2n​2​​은 알고리즘의 시간 복잡도에 영향을 미치지 않고, 입력값이 무한이 될 때 고려해야 할 부분은  n^3n​3​​ . 

규칙 5. 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시. 
모든 로그는 서로 배수 관계입니다. 그래서 복잡도에 관해서 이야기할 때는 로그의 밑에 대해서는 고려하지 않아도 됩니다. 로그의 밑은 무시하고 로그 ( lognlogn ) 알고리즘
복잡도가  loglog 인 알고리즘은 보통 무언가를 반으로 나누거나 2를 곱한 경우에 자주 사용
for 반복문을 사용해서 무언가를 탐색하면서 반으로 나누거나 2를 곱할 때 복잡도는 밑이 2인 로그.
10으로 나누거나 10을 곱하게 되면 밑이 10인 로그가된다.
하지만 시간 복잡도를 표시할 때에는 로그의 밑은 무시하고 그냥 log n 복잡도를 가진다고 표현

규칙 6. 등호를 사용하여 표현
다음 강의에서 더 자세히 다루겠지만  2n2n 은 O(n)O(n) 과 같다. 여기서  O(n)O(n) 은  2n2n 이 어떤 함수의 집합에 속한다그렇기 때문에 아래와 같은 등호를 활용하여 이 관계를 수학적으로 쓸 수 있다.
2n = O(n),  2n ∈ O(n)

이예를 들어, 상수 시간에 작동하는 알고리즘을 하나 생각해본다. 이 알고리즘의 시간 복잡도는 1 또는 문자 C를 사용하여 나타냅니다. 한 번의 계산만 하면 되는 경우로  nn 과는 독립적인 관계를 가진다. 또, 정렬이나 트리에서는  lognlogn  또는  n^2n​2​​ 복잡도인 알고리즘들을 많이 보게 될것이다

빅 오 표기법

빅 오 표기법은 알고리즘의 효율성을 표시하는 표기법입니다. 빅 오 표기법을 사용하면 어떤 알고리즘을 다른 알고리즘과 비교해서 표현하는 것이 가능

x축은 복잡도 n, y축은 필요한 일의 양이나 메모리

다른 알고리즘이 이 그래프의 어떤 위치에 있는지에 따라 복잡도  nn 인 알고리즘과 다른 알고리즘의 복잡도를 비교할 수 있다. 다른 알고리즘이 복잡도  nn 인 알고리즘의 아래에 있다면, 같은 일을 하는 데 시간이 덜 들기 때문에 더 빠른 알고리즘이라 한다. 반대로, 복잡도  nn 인 알고리즘의 위에 있다면, 더 느린 알고리즘이다.

빅 오 표기법에서는 이러한 알고리즘 간의 관계를 다음과 같이 표현한다
- O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다.
- θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.
- Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.
- o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.
- ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.

빅 오 표기법 예시

문제 1. 
n\textstyle ^4\textstyle ^/\textstyle ^3n​4​​​/​​​3​​  = O( nlognnlogn )

문제 2. 
3n^3+4n^2+5n+63n​3​​+4n​2​​+5n+6 = θ( n^3)n​3​​) 

문제 3.
n(n-1)/2 = O(n^2)n(n−1)/2=O(n​2​​) 

문제 4.
2^n = w(n)2​n​​=w(n)  

문제 5.
n^3 = O(n^2)n​3​​=O(n​2​​) 

문제 6.
n^2 = O(n^3)n​2​​=O(n​3​​)

풀이)

문제 1.
적당히 큰 수인 1000을 n에 대입하면, 좌변은  10000이고 우변은 log의 밑이 10일 때 O(3000)입니다. 그래프를 그리면 아래와 같고, 10000은 3000 이하가 아니기 때문에 이 식은 잘못되었습니다.

문제 2.
낮은 차수의 항들을 무시하면, 3n^33n​3​​ =θ( n^3n​3​​ )입니다. 그리고 모든 상수를 삭제하면 n^3n​3​​ =θ( n^3n​3​​ ). 따라서, 이 식은 참입니다.

문제 3.
낮은 차수의 항들을 무시하면, n^2/2n​2​​/2  =θ(  n^2n​2​​ )입니다. 그리고 모든 상수를 삭제하면 n^2n​2​​ =θ( n^2n​2​​ ). 따라서, 이 식은 참입니다.

문제 4.
적당히 큰 수인 1000을 n에 대입하면, 좌변은 2^1000이고 우변은 ω(1000)입니다. 그래프를 그리면 아래와 같고, 1000은 1000 이상이기 때문에 이 식은 참입니다.

문제 5, 6.
n^2n​2​​ 은  n^3n​3​​ 보다 느리게 증가합니다. 따라서, 문제 5는 거짓, 문제 6은 참입니다.

문제 1과 문제 3의 경우, 엄밀하게 풀기 위해서는 로피탈 규칙을 사용해야 합니다. 하지만 본 강의에서는 적당히 큰 수를 대입하는 방법으로도 풀 수 있는 문제들만 다룹니다.

참고-네이버 부스트코스