시간 복잡도

Beautify.log·2022년 1월 6일
0

알고, 모르고

목록 보기
1/1
post-thumbnail

약속 때문에 월평역에서 유성온천역까지 차를 타고 평소 다니던 길로 가고 있습니다.
평소 같았으면 15분이면 갈 거리를 출퇴근 시간대라는 것을 고려하지 못해 두배가 걸렸습니다.

실시간으로 교통흐름을 반영하는 네비게이션이 알려준대로 갔더라면 시간을 조금 더 절약할 수 있었을 것입니다.

만약 네비게이션 대로 갔다면 여유롭게 커피라도 한 잔 할 수 있었을텐데... 혼자서 씁쓸한 생각을 합니다.

이처럼 알고리즘도 시간을 단축하여 좀 더 효율적인 문제해결을 할 수 있다면 정말 좋을 것입니다.

알고리즘은 상황에 따라 다르게 작성되거나 적용되고 실행되는 시간은 컴퓨터가 알고리즘 코드를 컴파일하는 속도, 사용된 언어의 종류에 따라 다릅니다.

이 때 최대한 단시간에 많은 연산을 처리할 수 있는 것이 효율적이라 할 것입니다.

엄청 큰 숫자를 입력했을 때 그 숫자를 처리하는 시간은 각 알고리즘마다 다를 것입니다. 이처럼 입력 값에 따른 처리시간으로 알고리즘의 효율을 평가할 수 있습니다.

또한 앞에서 언급한 입력값의 크기에 따라 함수가 증가하는 양을 성장률이라 하고, 이 때 중요하지 않은 변수들을 비활성화하거나 제거하며 알고리즘의 실행 시간을 평가하는데 이것을 점근적 표기법이라 하며 Asymptotic notation이라고 합니다.

여기에서 말하는 점근적이란 가장 큰 영향을 주는 항(monomial)만을 계산한다는 의미입니다.


점근적 표기법


점근적 표기법에는 아래와 같이 세 가지가 존재합니다.

  1. 최상의 경우 : 오메가 표기법(Big-Ω Notation)
  2. 평균의 경우 : 세타 표기법(Big-Θ Notation)
  3. 최악의 경우 : 빅오 표기법 (Big-O Notation)

평균의 경우에 대해 평가하면 좋겠지만 세타 표기법은 평가하기가 매우 까다롭습니다.

그래서 최악의 경우인 Big-O Notation을 사용하는데, 알고리즘이 최악인 경우를 판단하면 평균의 경우와 근접한 성능을 예측할 수 있기 때문입니다.

빅오 표기법: Big-O Notation

빅오 표기법은 불필요한 연산과정을 제거하여 알고리즘을 간단하게 할 목적으로 사용합니다.

Big-O로 측정되는 복잡성 중에서 시간 복잡도와 공간 복잡도라는 개념이 있는데 각각은 다음과 같은 의미를 갖습니다.

시간 복잡도 : 입력된 NN의 크기에 따라 실행되는 조작의 수
공간 복잡도 : 알고리즘이 실행될때 사용하는 메모리의 양

최근에는 메모리 크기도 많이 커졌고 발전했기 때문에 공간 복잡도에 대한 중요도는 높지 않습니다.


시간 복잡도


시간 복잡도는 알고리즘의 성능을 설명하는 지표가 됩니다.

알고리즘을 처리하는데 있어 프로세스가 수행하는 연산을 수치화한 것입니다.

처리 속도를 판별하는데 시간으로 측정하지 않고 수치화된 데이터를 바탕으로 측정하는 것은 컴퓨터나 하드웨어, 프로그래밍 언어마다 명령어를 실행하는데 편차가 발생할 수 있기 때문입니다.

시간 복잡도에서 중요하게 생각하는 것은 바로 nn의 단위이며 이는 복잡도에 가장 큰 영향을 줍니다.

구분작성 예해설
11O(1)O(1)상수
2n+202n+20O(n)O(n)nn이 가장 큰 영향을 미침
3n23n^2O(n2)O(n^2)n2n^2이 가장 큰 영향을 미침.

다음은 입력받은 NN(또는 nn)에 대해 실행시간이 빠른 순으로 서로 다른 알고리즘의 시간복잡도를 나열한 것입니다.

복잡도정의
O(1)O(1)상수 시간 - 문제를 해결하는데 오직 한 단계만 처리함.
O(logN)O(logN)로그 시간 - 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(N)O(N)직선적 시간 - 문제를 해결하기 위한 단계의 수와 입력값 nn이 1:1 관계를 가짐.
O(nlogN)O(nlogN)선형 로그형 - 문제를 해결하기 위한 단계의 수가 N(log2N)N(log2N) 번만큼의 수행시간을 가진다.
O(N2)O(N^2)2차 시간 - 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(Cn)O(C^n)지수 시간 - 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.

상수 시간 O(1)O(1)

가장 단편적이고 간단합니다. 입력에 상관없이 동일한 복잡도를 보여줍니다.

function helloWorld() {

	console.log("Hello World!");

}

직선적 시간 O(N)O(N)

입력의 증가에 따라 처리 시간이나 메모리 사용이 선형적으로 증가합니다.

function printItem(li) {
	for(let i=0; i < li.length; i++) {
		console.log(li[i]);
	}
}

2차 시간 O(N2)O(N^2)

반복문이 두번 있는 경우입니다. 예를 들어서 2차원 배열 등을 처리할 때 사용하죠.

function arrayProcedure(li) {
	for(let i=0; i<li.length; i++) {
		for(let j=0; j<li.length; j++) {
			console.log(li[i]);
			console.log(li[j]);
		}
	}
}

시간 복잡도를 구하는 방법

육안으로도 빠르게 시간복잡도를 구할 수 있도록 다음과 같은 방법으로 접근할 수 있습니다.

구분해설
O(n)O(n)하나의 푸르를 사용해서 단일 요소 집합을 반복함
O(nm)O(n➗m)O(n)O(n)컬렉션의 절반 이상을 반복 하는 경우
O(n+m)O (n + m)O(n)O (n)두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복하는 경우
O(n2)O(n^2)두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우
O(n×m)O (n×m)O(n2)O (n^2)두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우
O(n×log(n))O(n×log(n))컬렉션 정렬을 사용하는 경우
profile
tried ? drinkCoffee : keepGoing;

0개의 댓글