시간복잡도

kich555·2021년 10월 31일
0

알고리즘에 대해 공부하다보면 가장 먼저 부딪히는 2가지가 있다.

바로 알고리즘과 시간복잡도인데 알고리즘이야 평소 우리가 많이 사용하는 단어 이다보니 대충 무슨 느낌인지는 다들 알 수 있을것이다

ex) youTube의 알고리즘이 나를 여기로 이끌었다... 등등

그럼 시간복잡도는 무엇일까?

이번 글에서는 시간복잡도에 대해 알아보고자 한다.

시간복잡도와 Big-O

시간복잡도란 어떠한 문제를 풀어맺기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다
위키피디아

당연히 들어도 무슨소리인지 모르겠으니 간단하게 말하자면

알고리즘을 푸는데 걸리는 시간을 의미한다.

즉 어느 한 문제 해결을 위한 알고리즘이 얼마나 간단한지, 복잡한지를 표시하는 지표라 할 수 있을것이다.

선택 정렬 Selection sort
첫번째 i에서 1 ~ n-1
두번째 i에서 2 ~ n-1
...
n(n-1)/2O(n²)의 시간복잡도를 가진다.

?

n(n-1)/2 이면 ½n²-½n 이지 왜 O(n²)라고 할까?

이는 시간복잡도를 계산하는데 있어서 가장 중요한 것은 핵심이 되는 연산을 찾는 것이기 때문이다.

½n²-½n에서 n이 커지면 커질수록 ½이나 -½n입장에서 무시해도 될 정도로 작은 수가 될 것이다. 때문에 핵심이 되는 이라고 쓰며 앞에 O를 붙혀 Big-O표기법이라 부른다.



시간복잡도 계산하는 법

시간복잡도와 Big-O에 대해서 이해하였으니, 이제 간단히 시간복잡도를 계산하는 법에 대해 알아보자,

for ( let i=0; i<n; i++ ) {
  for ( let j=0; i<m; j++ ) {
    
  }
}

위 식의 시간복잡도는 어떻게 될까?

정답은 바로 이다.
왜냐면 무한한 수인 nm을 반복하는 반복문 2개가 있기 때문이다.

for ( let i=0; i<n; i++ ) {
  for ( let j=0; j<m; j++ ) {
    for ( let k=0; k< 100000; k++ ) {
      
    }
  }
}

그럼 위 식의 시간복잡도는 어떻게 될까?

정답은 바로 이다.
왜냐면 k는 100000까지라는 유한한 수까지만의 반복이기 때문

우리 눈에 100000은 큰 수처럼 보이지만, 
무한한 수인 `n`과`m`입장에서 100000라는 수는 무시해도 될 만큼 
작은 수라는 것을 언제나 인지해야한다.
profile
const isInChallenge = true; const hasStrongWill = true; (() => { while (isInChallenge) { if(hasStrongWill) {return 'Success' } })();

0개의 댓글