시간복잡도

시간복잡도란 무엇일까??

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

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

모르는 것들을 세가지로 정리해봤다.

1.컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다.

 내가 간단히 이해한 바로는 입력이 있는 어떤 로직(알고리즘)을 수행 할때 얼마나 시간이 걸리냐? 이다.

 어떤 로직이나 알고리즘은 똑같이 1을 넣어도 하나는 1초 하나는 2초가 걸릴 수 도 있고, 어떤 것들은 처음에는 실행 시간이 같았지만 

1이아닌 2, 10, 100, 1000 ... 이런식으로 입력 숫자를 늘려나갈수록 걸리는 시간의 차이가 분명해지는 것들도 있다.

요즘은 좋은 장비덕에 적당히 작은 숫자는 이러한 차이를 느끼기 힘들겠지만 숫자가 커질수록 차이는 피부에 와닿을 것이다.

따라서, 입력하는 데이터가 많아질 수록 얼마나 속도가 나빠지느냐? 로 바꿔 말할 수도 있겠다.

이를 정량화 해서 측정을 하여야 향후 문제해결에 도움이 될것이 분명한 것 같다.

 그렇다면 이걸 어떻게 측정하느냐??

2. 빅-오 표기법

 측정하는 방법에는 여러가지가 있다.

그 중 빅-오 표기법은 가장 대중적인 방법으로 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 

3. 낮은 차수의 항을 제외시키는 방법

 데이터의 입력값을 무한대까지 증가시킬때  제일 변동성이 큰 값만 보는 것이다.

예를 들어 만약 n^2 + n + 1 이라는 식이 있다고 했을때 상대적으로 n^2이 n보다 훨씬 크게 증가하므로 제일 큰 n^2으로 측정하는 것이다.(물론 데이터가 커져도 그대로인 상수 1은 논외다)

하지만, 그렇다고 위의 식에서 n과 1을 아예 무시할 수 있는 것은 아니다.

우리는 무한한 데이터를 '가정' 했으므로 현실에서는 괴리가 있을수 있을 수 있고 이를 줄이는 것도 꽤나 큰 문제라고 한다.

 

여러가지 시간복잡도

시간복잡도에는 정말 여러가지가있지만 그 중 가장 대중적인 것들 5가지를 살펴본다. 

 

1. 상수시간(Constant Time)

 어떤 알고리즘의 T(n) 값이 입력 크기에 구애받지 않는 값에 의해서 한정된다면, 이 알고리즘은 상수 시간(O(1) 시간이라고 쓰기도 함) 이라고 말할 수 있다.  - 위키백과

 데이터가 얼마나 들어오든지 말든간에 정해진 시간이 걸리는 시간복잡도이다.

예를 들어서 배열안에서 첫번째 값을 찾는 first라는 메소드를 사용할때에는 배열의 크기가 100이든 10000이든 상관없이 바로 찾을 수 있을 것이다. - 가장 이상적인 수치라고 할 수 있다.

 

2.선형시간(Linear time)

 만약 시간복잡도가 O(n)이면, 이 알고리즘은 O(n)시간 혹은 선형 시간을 갖는다고 말할 수 있다. - 위키백과

데이터가 들어오는 만큼 시간이 늘어나는 시간복잡도이다. (기울기가 1인 그래프를 생각하니 쉬웠다)

 예를 들어서 어떤 배열의 for루프를 돈다고 가정을 해보자.

배열의 요소가 n개 증가하면 루프를 도는 시간이 n만큼 증가할것이다.

 

3. 2차시간(Quadratic time)

만약 T(n) = o(n2)이면, 서브-이차 시간의 알고리즘이라고 말할 수 있다.

데이터가 들어오면 그것의 제곱만큼 시간이 늘어나는 시간 복잡도이다.(그래서 n의제곱)

 예를들어 for루프를 두번 돌리는 중첩문을 생각해보자.

for문을 두개쓰는 구구단을 생각하니 이해가 편했다.

데이터의 값에 따라 시간복잡도가 급속히 상승하는 그래프이므로 최대한 지양하는 것이 좋을 것이다.

 

4.로그 시간(Logarithmic time)

만약 T(n) = O(log n) 이라면, 이 알고리즘은 로그 시간이 걸린다고 말할 수 있다.(로그 밑은 대부분 2를 사용한다)

이 알고리즘은 데이터 전체를 계속 반으로 나누어서 원하는 값을 찾는 알고리즘이며 데이터가 크면 클수록 진가를 발휘한다.

예를 들어 1부터 100까지 수중에 30을 찾는다고 하면.. 계속해서 원하는 값이 속한 쪽으로 반으로 나눈다.1. 100 / 2   =      1 ~ 50 , 50 ~ 100 2. 50 / 2 = 25    1 ~ 25 , 25 ~ 503. 25 / 2 = 12.5    25 ~ 37.5 , 37.5 ~ 50...

 

5.유사 선형 시간(Quasilinear time)

 어떤 양의 상수 k 에 대해서 T(n) = O(n logkn) 이면, 이 알고리즘은 유사 선형 시간동안 실행된다고 말할 수 있다. 선형로그 시간은 k=1인 경우이다. 

이 알고리즘이 가장 난해했는데 위키 백과에 있는 퀵정렬을 보고 이해가 되었다.

 

 

자세한 표와 예시는 위키와 밑 사이트에서 확인이 가능했다!

출처 - www.raywenderlich.com

raywenderlich.com | High quality programming tutorials: iOS, Android, Swift, Kotlin, Flutter, Server Side Swift, Unity, and more

시간 복잡도 - 위키백과, 우리 모두의 백과사전