[부스트캠프] - 시간복잡도 개념

www.youtube.com/watch?v=6Iq5iMCVsXA

유튜브 참고해서 시간복잡도를 배워보았습니다.

 

시간복잡도란?

시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

 

컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다. (출처 : 위키백과)

 

위키백과에서 언급한 점근적으로 묘사한다고 한것은, 

시간복잡도를 계산하는데 있어 실제시간을 계산하는것이 아니다.

 

그렇다면 무엇을 계산하기 위한 것일까?

시간복잡도 (Big-O)는 장기적으로 데이터가 증가함에따른 처리 시간의 증가율을 예측하기위한 표기법이다.

따라서 증가하지(변하지 않는) 않는 상수의 곱 혹은 덧셈은 신경쓰지 않는다! 

(증가하는 n만 신경쓰겠습니다! 그럼에도 바쁜 연산..!)

출처 : https://youtu.be/6Iq5iMCVsXA

 

Big - O 표기법이란?

1) 빅오는 알고리즘의 성능을 수학적으로 표현해주는 표기법이다.

2) 빅오를 통해 알고리즘의 시간과 공간 복잡도를 표현할 수 있다.

3) 빅오 표기법은 알고리즘의 실제 러닝타임을 표시하는거 라기보다는 데이터, 사용자의 증가율에 따른 
    알고리즘의 성능을 예측하는게 목표이다.

4) 따라서 위와같이 상수와 같은 숫자들은 모두 1회처리하여 생략한다.

 

또한 각 모형에따라 시간 복잡도는 다르다 ! 

 

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

1)

1) O(1) 알고리즘 : 입력 데이터의 크기와 상관없이

    언제나 일정한 시간이 걸리는 알고리즘

   -> O(1)의 시간 복잡도를 가진다.

 

 

 

 

 

 

 

 

2)

2) O(n) 알고리즘 : n개의 데이터를 받을때,

   n번 loof를 도는 알고리즘이다.

   따라서 n이 증가할때마다, 처리시간이 증가한다.

 

 

 

 

 

 

 

 

3,) 4)

3) O(N^2) 알고리즘 : n*n 번 실행 : 따라서 n이 1 증가할때마다 n^2 증가 

4) O(nM) 알고리즘 : n*m번 실행한다. ( n 혹은 M 증가할때마다 n or M만큼 증가)

 

 

5) 

5) O(n^3) 알고리즘 : 

   n^3이므로, 정육면체(cube)가 된다

  따라서 n 이 1증가할 때마다 n^3 씩 증가한다.

 O(n^2)보다 더 가파른 증가를 볼 수 있다.

 

 

 

 

 

 

 

 

6) 

6) O(2^n) 알고리즘 : 피보나치수열  n_k = n_k-1 + n_k-2 이다.

  O(n^3) 보다 더 가파른 시간의 증가를 보인다.

 

7) 

O(log n) : binary search 기법을 이용한다.

따라서 한번 함수가 호출될때마다 

절반을 나누고 한쪽은 제외시키므로 

순차검색에 비교해서 속도가 더 빠르다.

 

data가 증가해도 성능이 크게 차이가 나지 않는다.

 

 

 

 

 

 

 

8) 

8) O(sqrt(n)) 알고리즘

n의 제곱근 값으로 받는다!