시간복잡도(Time Complexity)

팀가이스트·2024년 4월 8일

알고리즘 자료구조

자료구조

목록 보기

1/3

어떤 함수를 실행한다고 가정해보자. 함수의 성능을 알고싶다. 함수의 성능을 측정하려면 어떻게 해야할까?

아쉽게도 컴퓨터 메모리, CPU 등 각각의 컴퓨터가 처한 상황에 따라 성능이 달라지기 때문에 정확한 성능을 측정하기란 어렵다.

그래서 성능을 조금 간단하게 표현해보기 위해서 실행시간을 다음과 같이 정의해보자.

실행 시간(running time)이란?
"함수/알고리즘 수행에 필요한 스텝(step) 수"
또 각 라인을 수행하기 위해 필요한 스텝 수는 상수(constant)라고 가정해보자.

예제로 살펴보자.

function multiply(inputs:number[], multiplier:number) {
 	 const nums = Array.from({ length: inputs.length }); // c1
	 for(let i = 0; i< inputs.length; i++) { // c2
      	nums[i] = inputs[i] * multiplier;  // c3
     }
     return nums; // c4
}

cost	times
c1	1
c2	N+1
c3	N
c4	1

각 라인의 cost를 매기고 각 라인이 몇번씩 실행되는지를 표로 나타내보았다.

c2의 경우에는 루프를 탈출하기 위한 검사를 한번 더 하기 때문에 N+1로 표현했다.

이를 수식으로 나타내면 다음과 같다.

여러가지 변수 때문에 위 수식보다 더 정확한 계산은 어렵다.

N이 작을 땐 실행 시간이 의미없다.
N -> ∞ 일 때 실행 시간이 궁금하다.

N-> ∞ 일 때 아래 규칙을 적용할 수 있다.

N이 커질수록 덜 중요한 것은 제거(곱,더하기..)
최고차항만 의미가 있다.
최고차항의 계수는 의미가 없다.

=> θ(N) - 점근적 표기법

위와 같이 N -> ∞ 일 때를 가정하여 분석하는 방식을 점근적 분석(Asymptotic analysis) 라고 한다.
임의의 함수가 N -> ∞ 일 때 어떤 함수 형태에 근접해지는지 분석하는 방법이다.

정리

시간복잡도란?
함수의 실행 시간을 표현하는 것이다.
주로 점근적 분석을 통해 실행 시간을 단순하게 표현하고 점근적 표기법으로 표현한다.

function exists(inputs:number[], target:number) {
  	for (let i = 0; i < input.length; i++) {
     	if(inputs[i] === target) {
         	return true; 
        }
    }
  	return false;
}