시간복잡도 Big-O(빅 오) 표기법

PS 사이트에서 문제를 풀 때, 알고리즘을 공부할 때 우리는 특정 알고리즘의 시간복잡도를 나타낸다.

보편적인 문제를 풀 때 시간복잡도가 O(N^3)만 넘어가도 '비효율적'인 알고리즘을 사용한다고 지적하기도 한다.

 

시간 복잡도를 계산할 때, 단순히 for문이 몇 번 중첩되어 있는지? 재귀함수를 몇 번 호출했는지?에 따라 계산하기도 하지만

알고리즘이 복잡해질 경우에는 제대로 된 시간복잡도를 구하지 못할 수 있다

또는 코드가 아닌 정의만 보고 시간복잡도를 분석해야할 때도 있다

 

그렇기 때문에 시간복잡도를 나타내는 표준적인 방법인 Big-O Notation에 대해 알아본다

 

시간복잡도: 알고리즘의 수행 시간을 분석하는 방법

특정 문제를 해결하는 알고리즘은 여러 개가 존재할 수 있다.

해당 포스팅에서 다룬 것 처럼, 부분합을 구하는 데에도 여러 알고리즘이 존재할 수 있다-> 2jinishappy.tistory.com/120

 

우리는 다양한 알고리즘 중 어떤 알고리즘이 '공간을 적게 차지하고', '짧은 시간 안에 동작하는지'에 대해 주로 관심을 가진다

알고리즘의 성능을 분석하는 데에는 실제로 실행 시간을 측정하는 실험적 분석과 알고리즘의 정의에서 분석하는 이론적 분석이 존재한다.

실험적 분석은 직관적이고 실용적인 방법이지만, 알고리즘의 로직 외에도 다양한 외부 요인으로 인해 제대로 된 측정이 어려울 수 있다.

그렇기 때문에 대부분의 알고리즘의 성능을 분석할 때는 해당 알고리즘이 입력 사이즈에 따라 얼마나 소요되는 지를 증명하고 분석하는 이론적 분석 방식을 택한다.

 

알고리즘은 다양한 연산을 사용한다. 변수 대입, 함수 호출 및 반환, 배열 접근 등등 ...

하지만 특정 알고리즘이 입력이 1개 들어올 때와 10000000000개 들어올 때 시행하는 연산 횟수가 동일하다면, 그것은 분석의 범위 외다.

입력의 크기와 무관하기 때문이다.

연산을 1억번을 해도, 이러한 단일 연산 횟수는 입력의 크기와 무관하기 때문에 상수 시간이 소모된다고 표현한다.

 

가장 큰 관심사는, '입력 사이즈에 비례해서 시간이 증가하는 정도'이다.

int fibo(int x){	//피보나치 순열을 구하는 함수
	if(x<=1) return 1;
	return fibo(x-1) + fibo(x-2);
}

피보나치 숫자를 구할 때 단순 재귀함수로 위와 같이 구현할 수 있다.

실제로 사용자가 보기에도 직관적이고, 정상적인 값을 반환한다.

하지만 x의 크기가 커질수록 결과값이 도출되는 시간은 천문학적으로 증가한다.

fibo(x)를 구하면서 fibo 재귀 함수를 두 번 호출하기 때문에, x의 피보나치 값을 구하기 위해 함수 호출을 2^N번 해야하는 것이다.

당연히 이런 알고리즘을 사용하는 것은 매우매우매우 지양하는 바이고, 다른 알고리즘을 사용하면 훨씬 짧은 시간에도 피보나치 함수 값을 구할 수 있다.

 

그렇기 때문에 알고리즘의 시간 복잡도를 계산하는 것이다. 알고리즘의 입력 크기에 비례하는 성능을 분석하기 위해❗❗

 

위에서 언급한 것 처럼 시간복잡도를 표기하는 방법으로, Big-O Notation을 사용한다.

f(n)과 g(n)이 자연수에서 실수로의 함수이고, 만약 모든 n≥n0에 대해 f(n)≤c·g(n)를 만족하는 어떤 실수 c>0와 자연수 n0≥1이 존재하면 f(n) = O(g(n))이라 한다.

이 때, f(n)의 시간복잡도는 O(g(n)) (Order g)라고 말할 수 있는 것이다 !! 🤔

물론 위와 같은 정의는 하나도 이해되지 않지만, 이해는 개인의 몫이고(^^) 중요한 것은 함수 f(n)과 g(n) 사이의 증가율을 비교하는 식이라는 것이다.

어떤 상수값이 붙던간에, 특정 입력 사이즈를 초과했을 때 증가율이 역전되는지 확인하는 공식이다.

 

예를 들어 f(x)가 6n+500이라면

g(n)을 n, c를 7로 했을 때 500보다 크거나 같은 n0에 대해 g(n)의 값이 f(n)의 값보다 크기 때문에, f(n)은 O(n)이다. 

물론 g(n)을 n^10000으로 해도 똑같이 성립하고, f(n)은 O(6n+500)이라고 할 수도 있다.

하지만 그렇게 표기할 경우 시간복잡도의 의미가 흐려진다.

명시적으로 g(n)은 계수를 1로 하고, 가장 증가율이 작은 함수 형태로 나타낸다.

 

출처: https://miro.medium.com/max/1080/1*m7hr0FJWhL9iN_WihJjeoQ.png, https://blog.chulgil.me/content/images/2019/02/Screen-Shot-2019-02-07-at-2.31.54-PM-1.png

식의 증가율 순으로 나타낸 그림이다.

아래로 갈 수록 증가율이 높아지고, 위로 갈 수록 낮아진다.

 

이 때, 함수간의 증가율 대소를 나타내는 특징이 몇 가지 있다

1️⃣ 지수함수에서는 밑이 클 수록 증가율이 높다.

2️⃣ 모든 다항함수는 어떠한 log 함수보다 증가율이 높다(dominate한다). 

3️⃣ 모든 지수함수는 어떠한 다항함수보다 증가율이 높다(dominate한다). 

 

f(n) = 10*2^n + 5*3^n + n^3이라면, 지수 함수는 다항함수를 dominate하고 밑이 큰 지수 함수가 작은 지수 함수를 domintae하면서, 계수는 1로 간소화 하기 때문에 f(n)의 시간복잡도는 O(3^n)으로 나타낼 수 있다.

 

추가로, n!의 시간복잡도는 O(n^n)으로 근사된다. (시간복잡도가 매우매우 크다)

 

Big-O의 표기는 위와 같고, 실제 코드나 알고리즘에서 Big-O를 계산할 때는 주로

1️⃣ 변수의 대입 횟수

2️⃣ 반복문(for, while, do-while) 횟수

3️⃣ 함수의 호출&반환 수

에 달려있다. 물론 입력 크기와 비례한다는 가정에서 !!

 

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, arr[1001][1001], dp[1001][1001], ans;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
			if (!i || !j || !arr[i][j])
				dp[i][j] = arr[i][j];
			else if (arr[i - 1][j] && arr[i][j - 1] && arr[i - 1][j - 1]) {
				dp[i][j] = min({ dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] }) + 1;
			}
			else {
				dp[i][j] = 1;
			}

			if (dp[i][j] > ans)ans = dp[i][j];
		}
	printf("%d", ans * ans);
	return 0;
}

위와 같은 코드에서는, 입력의 크기인 n과 m에 비례해서 반복 회수가 달라진다.

for문 내에 존재하는 if-else문은 단일 연산이기 때문에 O(1)이 소모되고, for문은 각각 N번, M번 시행된다.

따라서 해당 코드의 시간복잡도는 O(NM)이라고 말할 수 있다.

 

시간복잡도와 Big-O의 정의, 코드의 시간복잡도 계산법에 대해 알아봤다.

 

추가로 Divide and Conquer를 이용한 알고리즘에는 알고리즘의 시간 복잡도를 도출하는 점화식이 사용되는데, 해당 점화식에서 Big-O를 계산해내는 방법은 아래 포스팅과 같다 ⬇

(2jinishappy.tistory.com/96?category=903864)

 

끝 🤗