알고리즘 시간 복잡도, 공간 복잡도(Time Complexity, Space Complexity) + Big-O

알고리즘(Algorithm)

알고리즘이란 어떠한 문제를 해결하기 위한 방법이다.

예를 들어
회사에 출근하기 위해서는  "회사에 출근하기"라는 문제를 해결하기 위해 "집에서 회사까지 어떤 이동수단을 타고 어떤 루트로 갈 것이다" 라는 방법을 알고 있어야 한다.

방법은 여러 가지가 있을 것이다. 좋은(효율적인) 방법도 있고 나쁜(비효율적인) 방법도 있을 것이다.

좋은 방법과 나쁜 방법은 어떻게 정할 수 있을까?

예를 들어 회사에 출근하기 위한 좋은 방법을 찾고 있다면 기준을 정해야 한다.

가장 빨리 가는 것이 좋은 방법이라면 전용 헬기를 타고 가거나, 비행기를 타고 가면 될 것이다.

가장 저렴하게 가는 것이 좋은 방법이라면 걸어서 가거나, 대중교통을 이용해서 가면 될 것이다.

이렇게 알고리즘의 좋고, 나쁨을 판단하기 위해 시간과 돈(메모리)을 기준 삼아서 판단한 것을 각각 시간 복잡도와 공간 복잡도라고 한다.

"효율적인 알고리즘과 비효율적인 알고리즘을 판단은 어떻게 해야 할까?"라는 물음에 답하기 위해서 두 가지 측정 방법이 있다. 바로 시간 복잡도와 공간 복잡도이다.

시간 복잡도는 "얼마나 빠른가?"를 측정하는 것이고, 공간 복잡도는 "메모리를 얼마나 쓰는가?"를 측정하는 것이다.

요즘은 일반 유저들의 컴퓨터의 스펙이 많이 좋아져서 공간 복잡도보다는 시간 복잡도에 더 중요성을 많이 부여하는 경향이 있다.

즉, 돈은 많으니까 빠른게 최고다 라는 것이다.

 

시간 복잡도(Time Complexity)

어떤 알고리즘을 실행했을 때, 알고리즘이 처리되는 실행 시간을 측정하는 것이다.

단순히 우리가 아는 시간으로 계산한다면, 컴퓨터 스펙에 따라 결과는 천차만별일 것이다.

그래서 시간으로 계산하는 것이 아니라 실행 시간으로 측정하는 것이다.

실행 시간이란
알고리즘 수행에 필요한 스텝(step)의 수이다.

시간 복잡도는 알고리즘의 실행 시간을 점근적 분석을 통해 실행 시간을 단순하게 표현하며, 이때 점근적 표기법으로 표현하는 것을 말한다.

 

점근적 분석

void Func(int n)
{
    for(int i = 0; i < 1000*n; ++i) {} // 1000n
    for(int i = 0; i < n; ++i) // n
    {
        for (int j = 0; j < 2*n; ++j) {} // 2n
    }
}

위 코드에서 한줄 한줄씩 스텝의 수를 계산해 보면

for(int i = 0; i < 1000*n; ++i) {} // 1000n

 

func(int n)함수의 매개 값으로 n이 넘겨졌다면, n * 1000 = 1000n번의 스텝이 있다.

 for(int i = 0; i < n; ++i) // n
    {
        for (int j = 0; j < 2*n; ++j) {} // 2n
    }

i가 한 번 증가할 때마다 안쪽 for문이 실행된다. 따라서 바깥 for문의 스텝 수는 n이고, 안쪽 for문의 스텝 수는 2n이므로 총 스텝 수는 n*2n = 2n^2이다.

이 함수의 총 스텝의 수는 2n^2 + 1000n이다.

여기서 n의 크기가 작을 때는 의미가 없다. 왜냐하면 인간이 느끼지 못할 정도로 짧은 순간이 걸리기 때문에 측정할 가치가 없다.

우리가 주목해야 할 것은 n이 매우 클 때, 즉 n이 무한대로 커질 때이다.

 n이 무한대로 커질 때, 중요한 것은 최고차항이다. 2n^2 + 1000n에서 최고 차항은 2n^2이다.

최고 차항인 2n^2도 계수는 의미가 없다. 따라서 func(int n)함수의 스텝 수는 n^2 이다

위 과정을 점근적 분석이라고 한다.
점근적 표현은 알고리즘의 실행 시간(알고리즘 수행에 필요한 스텝(step)의 수)을 간단하게 나타낸 것
알고리즘의 인풋이 무한대로 증가할 때 계수를 모두 지우고, 최고차항만 남겨서 실행 시간을 단순히 표현한 것은 점근적 표현이다.

 

점근적 표기법(Big-O, Big-Omega, Big-Theta)

점근적 표기법이란?
알고리즘의 성능을 나타내는 표기법
시간 / 공간 복잡도 예측시 사용
input의 증가에 따른 처리 시간 또는 필요 공간 계산
점근적 분석을 통해서 예측하는 것이기 때문에 모든 연산 횟수를 계산하는 것이 아닌 input의 증가에 따른 연산 처리시간의 증가율을 예측하는 척도이다.

 

Big-O(상한선, upper bound)

Big-O는 알고리즘의 실행 시간이 가장 길 때를 나타내는 것이다.(일반적으로 알고리즘의 성능을 표현할 때 많이 씀)

어떤 알고리즘의 스텝의 수가 N이면 N을 다 거치고 나서야 문제를 해결하거나 하지 못하는지 판별을 할 수 있으니까 실행시간이 가장 긴 것이다. 

예를 들어
1~10까지 수가 저장되어 있는 배열에서 중복을 허락하여 합해서 특정한 수를 찾는 알고리즘이 있다.

public class Test{
	public static void main(String[] args) {
		Func(arr,20);
	}
	static void Func(int[] arr, int number)
	{
		int count = 0;
		for(int i = 1; i <= arr.length; ++i) //n
		{
			for (int j = 1; j <= arr.length; ++j) // n
			{
				int result = i + j;
				
				if (result == number) 
				{
					++count;
					System.out.println("발견 : "+ i + "+"+ j +"="+ result);
					System.out.print("계산 횟수 : "+ count);
					return;
				}
				else
				{
					++count;
				}
			}
		}
		System.out.print("계산 횟수 : "+ count);
	}
}
/*
발견 : 10+10=20
계산 횟수 : 100
*/​

위 알고리즘의 스텝의 수는 n^2이다.
위 알고리즘의 실행 시간이 가장 길어질 때는 중복을 허락하여 합해서 특정한 수를 못찾는 경우(ex 매개값으로 21을 넘김)와, 매개값으로 20을 넘기는 경우이다.
이 알고리즘을 Big-O로 표기하면 O(N^2)이다.

즉, 알고리즘의 스텝의 수가 N이면 O(N)이라고 표기하고  "알고리즘의 실행 시간은 최악의 경우 N이다" 라고 해석 할 수있다.

 

 

Big-Omega(하한선, lower bound)

big-Omega는 알고리즘의 실행 시간이 가장 짧을 때를 나타내는 것이다.

이는 입력값에 따라 달라진다.

예를 들어
1~10까지 수가 저장되어 있는 배열에서 중복을 허락하여 합해서 특정한 수를 찾는 알고리즘이 있다.

public class Test{
	public static void main(String[] args) {
		Func(arr,2);
	}
	static void Func(int[] arr, int number)
	{
		int count = 0;
		for(int i = 1; i <= arr.length; ++i) //n
		{
			for (int j = 1; j <= arr.length; ++j) // n
			{
				int result = i + j;
				
				if (result == number) 
				{
					++count;
					System.out.println("발견 : "+ i + "+"+ j +"="+ result);
					System.out.print("계산 횟수 : "+ count);
					return;
				}
				else
				{
					++count;
				}
			}
		}
		System.out.print("계산 횟수 : "+ count);
	}
}
/*
발견 : 1+1=2
계산 횟수 : 1
*/​

위 알고리즘의 스텝의 수는 n^2이다
찾는 값이 2이므로 단 한번에 문제를 해결했다. 
위는 단 한 번에 목적을 달성했으므로 Ω(1)이다.

즉, 알고리즘의 실행시간이 가장 짧을 때 스텝수가 N이면 Ω(N)으로 표기한다.

 

Big-Theta(thght bound)

Big-Theta는 Big-O와 Big-Theta가 같은 경우를 말한다.

상한선과 하한선이 아주 가까이 있다고 해서 tight bound라고 한다.

예를 들어

static void Func(int number)
	{
		for(int i = 1; i <= number; ++i)
		{
			for(int j = 1; j <= number; ++j)
			{
				System.out.print(i*j + " ");
			}
			System.out.println();
		}
	}

위 알고리즘은 무조건 안쪽 루프와 바깥루프를 모두 돌아야한다.
실행 시간이 가장 길때 스텝 수는 n^2이고 실행 시간이 가장 짧을 때 스텝 수도 n^2이다.
이 경우 Big-O와 Big-Theta가 모두 N^2이므로 θ(N^2)라고 표기한다.

Big-O와 Big-Theta가 모두 N이면 θ(N)라고 표기한다.

Big-O와 Big-Theta가 모두 1이면 θ(1)라고 표기한다.

 

시간 복잡도, 점근적 표기법 정리

점근적 분석은 알고리즘의 실행 시간(알고리즘 수행에 필요한 스텝(step)의 수)을 간단하게 나타낸 것이며

점근적 표기법은 같은 알고리즘을 Big-O, Big-Omega로 표현하고 O와 Omega가 같은 경우에 Big-Theta로 표현할 수 있다.

• Big-O는 최악의 경우를 점근적 표기법으로 나타낸 것
• Big-Omega는 최선의 경우를 점근적 표기법으로 나타낸 것
• Big-Theta는 O와 Omega가 같은 경우를 점근적 표기법으로 나타낸 것

시간 복잡도는 알고리즘의 실행 시간을 점근적 분석을 통해 실행 시간을 단순하게 표현하며, 이때 점근적 표기법으로 표현하는 것을 말한다.

알고리즘의 성능(시간 복잡도, 공간복잡도)을 나타낼 때 주로 Big-O를 많이 사용한다.

왜 Big-O를 많이 사용하는가?
우리가 꼭 해야 하는 작업이 있는데 친구가 만나자고 한다면, 현재 해야하는 작업을 마치고 친구를 만날 것이다.
가장 빨리 작업을 마치는 시간은 1시간이고,
가장 늦게 작업을 마치는 시간은 2시간이라면
이런 경우에 몇 시간 뒤에 친구와 약속을 잡을 것인가?
당연히 후자의 경우이다.

 

시간 복잡도별 성능

• O(1) : 인풋의 크기와 상관없이 항상 일정한 시간 소요 (가장 빠르고 이상적)
• O(log N) : 로그시간, 아주 효율적인 속도
• O(N) : 선형시간, 인풋의 증가 시 같은 비율로 증가 (기준)
• O(N^2) : 인풋 증가시 제곱 비율로 증가
• O(N!) : 팩토리얼 시간 복잡도, n이 증가할수록 실행 시간이 기하급수적으로 증가 (가장 느림)

보통 O(N)이 기준이며 O(N)보다 크면 느리다고 표현하고, 낮다면 빠르다고 표현한다.

 

O(1)

static void Func(int[] arr, int number)
	{
		System.out.print(arr[number]);
	}

인풋의 크기와 상관없이 항상 일정한 시간 소요

 

O(log N)

static void Func(int number)
	{
		int count = 0;
		for(int i = 2; i<=number; i*=2)
		{
			++count;
		}
		System.out.print(count);
	}

인풋이 16이면 step은 4, 인풋이 100이면 step은 6이 된다. 굉장히 효율적인 알고리즘이라고 할 수 있다.

 

O(N)

static void Func(int[] arr)
	{
		int count = 0;
		for(int i = 0; i<arr.length; ++i)
		{
			++count;
		}
		System.out.print(count);
	}

인풋에 비례하여 step도 증가한다.

 

O(N^2)

static void Func(int number)
	{
		int count = 0;
		for(int i = 0; i<number; ++i)
		{
			for(int j = 0; j<number; ++j)
			{
				++count;
			}
		}
		System.out.print(count);
	}

인풋을 3개 넣으면 step은 9, 인풋을 10개 넣으면 step은 100이다.

 

O(N!)

	static int Func(int number)
	{
		if(number==1)return 1;
		else return number * Func(number-1);
	}

인풋이 5면 step은 120, 인풋이 10이면 step은 3628800이다.

 

 

공간 복잡도

공간 복잡도는 "입력크기에 대해 어떤 알고리즘이 실행되는데 필요한 메모리 공간의 양"을 가리킨다.

즉, 공간복잡도 = 정적공간 + 동적공간이다.

동적공간은 동적으로 필요한 공간을 뜻한다.

정적 공간은 정적으로 선언한 변수, 배열 등 모든 크기가 변하지 않는 공간을 뜻한다.

int []arr = {1,2,3,4,5,6,7,8,9,10};
int a = 10;
String str = "abcd";
String []strarr = {"a","b","c","d"};

 

반면 동적 공간은 사용자의 입력에 따라 언제든지 크기가 변할 수 있다.

Scanner scanner = new Scanner(System.in);
System.out.print("생성할 배열의 개수(정수)를 입력하세요 : ");
int inputInt = scanner.nextInt();
int []arr = new int[inputInt];

위 코드는 사용자의 입력(input)에 따라 배열에 할당되는 공간이 달라진다.

int형 배열 1개의 메모리 차지 공간은 4byte이므로 n개의 인풋이 들어온다면 4n이다. 이를 점근적 표현으로 나타내면 n이다. 따라서 공간 복잡도는 O(N)이다.

 

static int Func(int number)
	{
		int i = 0;
		int result = 1;
		for(i = 1; i<=number; ++i)
		{
			result = result * i;
		}
		return result;
	}

위 코드의 공간 복잡도는 O(1)이다.

input이 없기 때문에 점근적 표기법으로 나타내면 O(1)이다.

 

	static int Func(int number)
	{
		if(number==1)return 1;
		else return number * Func(number-1);
	}

위 코드의 공간 복잡도는 O(N)이다.

input의 개수에 따라 재귀함수가 호출되므로 O(N)이다.

 

 

---

유튜브, 구글링을 통해 제가 이해한 내용을 바탕으로 정리하였습니다.

저도 정리하면서 이게 맞나? 싶네요.

틀린게 있다면 댓글남겨주세요.