python 을 활용한 자료구조와 알고리즘 공부 - (5)

이 필기내용은 프로그래머스 홈페이지의 어서와! 자료구조와 알고리즘은 처음이지? 강의를 들으면서 제가 필기한 내용입니다.

 

어서와! 자료구조와 알고리즘은 처음이지?  https://programmers.co.kr/learn/courses/57

어서와! 자료구조와 알고리즘은 처음이지? | 프로그래머스

---

알고리즘의 복잡도

 

> 알고리즘의 복잡도 라는 개념이 존재한다. 이 알고리즘의 효율성이 어느정도인지 측정하기 위한 도구로도 사용될 수 있는데, 시간 복잡도와 공간 복잡도로 나뉘어진다.

알고리즘의 복잡도는 이 알고리즘이 얼마나 복잡하게 짜여져 있냐를 따지는 것이 아니라, 

이 알고리즘은 문제해결에 있어서 얼마나 많은 자원을 요구하는가를 뜻한다.

시간 복잡도는 문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계를 뜻하며,

공간 복잡도는 문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계를 뜻한다.

여기서는 시간 복잡도를 중점으로 다룰것이다.

 

시간 복잡도

 

> 평균 시간 복잡도 : 임의의 입력을 했을때 소요되는 시간의 평균

> 최악 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

 

빅-오 표기법

 

이러한 시간 복잡도를 나타내는 표현으로 Big-O notation이 있다. 점근 표기법의 일종으로,

알고리즘의 시간 복잡도를 표현할때 많이 사용된다.

 

ex) 

O(logn) : 입력의 크기의 로그에 비례하는 시간이 소요

O(n) : 입력의 크기에 비례하는 시간이 소요

O(n^2) : 입력의 크기의 제곱에 비례하는 시간이 소요

O(2^n) : 입력의 크기의 2의 n승에 비례하는 시간이 소요

 

>이것들 말고도 다양한 크기의 시간 복잡도가 존재한다.

 

빅-오 표기법의 특징

 

> 빅-오 표기법에서 계수와 최고차항을 제외한 나머지 항들은 중요하지 않다. 

n의 수가 많이 증가했을때 사실 계수와 최고차항을 제외한 나머지 항들은 큰 영향력을 발휘하지 못하기 때문이다.

즉 다시말하여, O(n), O(2n), O(3n), O(4n) => 거기서 거기이다. 그래서 계수는 중요하지 않다. 계수는 제외하고 표기한다. 

> 또한 , 최고차항을 제외한 나머지 항들도 다 무시된다. 

> 즉, 연산 횟수가 2n^3+ 3n+1이라면, 시간 복잡도는 O(n^3)이다.

 

 

대표적인 시간 복잡도의 대표적인 예시들

 

 

1. 선형시간 알고리즘 : O(n)

ex) 선형탐색 알고리즘

> '무작위로 놓여있는' n개의 수에서 최댓값을 찾기 위해 처음부터 끝까지 모든 수를 다 탐색하는 방법! 

> 이런경우 Average case와 Worst case는 둘다 O(n)이다. 왜냐하면 어짜피 마지막 원소까지 항상 다 탐색해야 되기 때문이다.

 

2. 로그시간 알고리즘 : O(logn)

ex) 이진탐색 알고리즘

> '크기 순으로 정렬된' 알고리즘에서 최댓값을 찾기 위해 탐색하는 방법

> 이런 경우 시간 복잡도는 O(logn)이다.

 

3. 이차시간 알고리즘 : O(n^2)

ex) 삽입정렬(insertion sort)

> 이미 정렬된 부분에 정렬되지 않은 원소들을 하나씩 알맞은 위치에 삽입하는 정렬

> 이런 경우 Best Case는 '이미 모든 원소가 다 정렬'되어 있을때 이므로, 그때의 시간 복잡도는 O(n)이다.

> 또한,  Worst Case는 '모든 원소가 역순으로 정렬'되어있을떄 이므로, 그떄의 시간 복잡도는 O(n^2)이다.

 

4. 병합 정렬 (merge sort) : O(nlogn)

> divide & conquer 방법을 사용하는 정렬방법이다. 이떄의 시간복잡도는 최소 O(nlogn)이 나온다.

> 참고적으로, 정렬에 관련된 시간 복잡도에서 O(nlogn)보다 낮은 시간 복잡도는 존재하지 않는다는 사실이 수학적으로 증명되었다.