5. 알고리즘의 복잡도

알고리즘 복잡도란 해당 문제를 해결하는데 있어서 얼마나 많은 자원을 사용하는가를 나타낸다
이는 둘로 나뉜다

• 시간 복잡도 (Time Complexity)
  • 문제의 데이타 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
• 공간 복잡도 (Spzce Complexity)
  • 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계.

시간 복잡도를 알아 볼건데 이는 크게 둘로 나눈다.

• 평균 시간 복잡도 (Average Time Complexity)
  • 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
• 최악 시간 복잡도 (Worst-case Time Complexity)
  • 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

복잡도를 흔하게 쓰는 표기법이 있는데

Big-O Notation

점근 표기법 (asymptotic notation) 의 하나로 어떤함수의 증가 양상을 다른 함수와의 비교로 표현한다.
O(logn), O(n), O(n^2), O(2^n) 등으로 표기한다.

수학적인 정의로 잘 나타내져 있지만 프로그래밍 입장에서 바라본다면
-> 입력의 크기가 n 일 때
O(logn) - 입력의 크기의 로그에 비례하는 시간 소요한다는 뜻
O(n) - 입력의 크기에 비례하는 시간 소요한다는 뜻

선형 시간 알고리즘 - O(n)

n개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘을 적용

L = [3,8,2,7,10,9]가 있다고하면 최대값을 찾기위해서 끝까지 살펴봐야 알 수 있다.
따라서 Average case : O(n), Worst-case: O(n)으로 n에 비례하는 선형 시간 알고리즘임을 할 수있다.

로그 시간 알고리즘 - O(logn)

n 개의 크기 순으로 정렬된수에서 특정 값을 찾기 위해 이진 탐색 알고리즘을 적용 ( 선형 시간 알고리즘 보다 복잡도가 낮다 )

이차 시간 알고리즘 - O(n^2)

삽입 정렬(insertion sort)

회색은 이미 정렬되어 삽입된 것 흰색은 정렬되지 않고 삽입 예정인 주어진 리스트

Bast case : O(n) -> 모든 원소들이 이미 정렬되어 주어진 경우

Worst case : O(n^2) -> 모든 원소들이 정렬되지 않은 경우

 

보다 나은 (낮은) 복잡도를 가지는 정렬 알고리즘

병합 정렬(merge sort) - O(nlogn) 가 존재

 

알고리즘 순서

1. 정렬할 데이터를 반씩 나누어 각각 정렬시킨다. O(logn)

2. 정렬된 데이터를 두 묶음씩 한데 합친다 (작은 수를 앞 큰수를 뒤). 이과정을 반복하면 정렬 완료 O(n)

 -> O(nlogn)

 

참고 : 입력 패턴에 따라 정렬 속도에 차이가 잇지만 정렬 문제에 대해 O(nlogn) 보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명되어 있다.

 

복잡한 문제 - 배낭 문제 (Knapsack Problem)

배낭에는 15키로만 담을 수 있고 서로 다른 가치와 무게를 가진 아이템이 있다고 할때 어떤 물건들을 담아야 가장 높은 가치를 가지는지를 푸는 문제