Java | 점근적 표기법,시간 복잡도(Time Complexity), Big-O

BOZZANG·2022년 4월 17일
0
post-thumbnail

알고리즘은,

어떤 목적을 달성하거나 결과물을 도출하기 위해 거쳐야 하는 일련의 과정들을 말한다.

효율적인 알고리즘 ❔

알고리즘 문제를 풀 때, 해답을 찾기 위해 여러 방법을 사용한다.
알고리즘은 복잡도complexity가 낮을 수록 효율적이다.
즉 수행 시간이 짧거나, 기억 공간을 적게 사용하는 알고리즘이 효율적이라고 할 수 있다.
하지만 최근 하드웨어 기술의 발달로 기억 장치, 공간에 대한 비용이 줄어 수행 시간 단축이 더욱 중요시되고 있다.
그래서 일반적으로 복잡도는 시간 복잡도Time Complexity를 의미한다고 한다.


복잡도

프로그램이 동작하는 컴파일러나 하드웨어 등의 조건에 따라 프로그램의 실행 속도가 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다.

알고리즘 효율성을 분석하는 방법은 아래 두 가지가 있다.

  1. 시간 복잡도 time complexity
    실행에 필요한 시간을 평가한 것

  2. 공간 복잡도 space complexity
    기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

이 중에서 시간 복잡도 time complextiy에 대해서 알아보도록 하겠다.


🎇 점근적 분석

  • 시간 복잡도를 고려하기 위해서, 입력값의 변화에 따라서 실행되는 연산의 횟수와 시간을 비교한다.

  • 데이터 입력값이 작은 문제
    - 알고리즘의 효율성이 중요하지 않고, 비효율적이어도 무방하다.

  • 데이터 입력값이 충분히 큰 문제
    - 알고리즘의 효율성이 중요하고, 비효율적인 알고리즘은 치명적이다.

  • 입력값이 커짐에 따라서, 소요되는 시간을 최소화하는 것이 목적이다.

이러한 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라고 한다.
ex) 함수의 극한

어떠한 문제 해결을 위한 알고리즘의 성능분석을 할 때, 다양한 요소에 의해 비교 결과가 항상 일정하지 않을 수 있다. 이를 효과적으로 해결하는 방법이 점근적 분석이며, 이는 주어진 데이터의 크기를 기준으로 수행시간 혹은 사용공간이 얼마나 되는지를 객관적으로 비교할 수 있는 기준을 제시해준다.


🧷 점근적 표기법

Asymptotic Notation
점근적 표기법은 시간복잡도를 나타내는데 사용된다.

🤩 최상의 경우 : Big-Ω Notation (빅-오메가)

◼ 최상을 고려하는 Ω( g(n) ) : 하한 점근

적어도 g(n)의 비율로 증가하는 함수
f(n) = Ω(g(n))으로 보는 직관적 의미 : 
	f는 g보다 느리게 증가하지 않는다.
    
: 최선의 시나리오로 최소 이정도 시간이 걸린다.

ω Notation (스몰오메가)

◼ ω( g(n) ) : 여유 있는 하한 점근, o( g(n) )과 정확히 대조됨

f(n) = ω(g(n))으로 보는 직관적 의미 : 
	f는 g보다 빠르게 증가한다.
    
: 주어진 알고리즘이 아무리 좋아도 비교하는 함수보다 좋지 못하다. 

🙂 평균의 경우 : Big-θ Notation (빅-세타)

◼ 중간, 평균 정도의 θ( g(n) ) : 점근선 상한선과 점근적 하한선의 교집합

g(n)의 비율로 증가하는 함수
f(n) = θ(g(n))으로 보는 직관적 의미 : 
	f는 g와 같은 정도로 증가한다. 
    
: 주어진 알고리즘이 아무리 좋아지거나 나빠지더라도 비교하는 함수의 범위 안에 있다.

o Notation (스몰오)

◼ O( g(n) ) : 여유있는 상한 점근 

f(n) = o(g(n))으로 보는 직관적 의미 : 
	f는 g보다 느리게 증가한다.
    
: 주어진 알고리즘이 아무리 나빠도 비교하는 함수보다 좋다.

🙄 최악의 경우 : Big-O Notation (빅-오)

◼ 최악의 경우 O( g(n) ) : 상한 점근

기껏해야! g(n)의 비율로 증가하는 함수
f(n) = O(g(n))으로 보는 직관적 의미 : 
	f는 g보다 빠르게 증가하지 않는다. 
    (상수 비율의 차이는 무시)

: 주어진 알고리즘이 아무리 나빠도 비교하는 함수와 같거나 좋다.

Ω(g(n)) Tight or loose loswer bound
ω(g(n)) Loose upper bound
θ(g(n)) Tight bound
o(g(n)) Loose upper bound
O(g(n)) Tight or loose upper bound

빅오 표기법은 프로그램 실행 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 가장 자주 사용되는 표기법이다. 즉, 알고리즘 효율성을 상한선 기준으로 표기하기 때문에 자주 사용된다.
오메가는 의미 없는 평가이고, 평균인 세타 표기를 하면 가장 정확하고 좋겠지만, 평가하기가 까다롭다.
알고리즘 효율성은 값이 클수록, 그래프가 위로 향할수록 비효율적임을 의미한다.

  • 주의할 점은 Big-O 표기법이 상한선만 지정한 것이지, 상한선이 꼭 알고리즘 효율성의 최악의 경우가 아니라는 것

🧷 Big-O 표기법 특징

✔ 상수항 무시

✔ 영향력 없는 항 무시

데이터 입력값(n)이 크다는 가정 하에, 알고리즘 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 사소한 부분은 무시한다.

O(3n^2 + 2n + 1 ) ==> O(n^2)

🧷 Big-O 표기법 성능 비교


🧷 주로 사용되는 Big-O 표기법

✔ O(1)

상수 시간 : 문제 해결 시 오직 한 단계만 처리

일정한 복잡도 constant complexity 라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

  • 입력값 n이 크다고 가정했기 때문에, 앞에 계수가 3n, 5n이어도 O(n)으로 표기한다. (n이 커질수록 계수의 영향력이 사라지기 때문)
  • stack에서의 Push, Pop

✔ O(log n)

로그 시간 : 문제 해결 시 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦

로그 복잡도 logarithmic complexity 라고 부르며, O(1) 다음으로 빠른 시간 복잡도를 가진다.

  • 이진 검색

✔ O(n)

직선적 시간 : 문제 해결 시 필요한 단계의 수와 입력값 N이 1:1 관계

선형 복잡도 linear complexity 라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가한다.

  • 선형 검색
    (2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시한다.)
  • for문

✔ O(n log n)

선형로그형 : 문제 해결 시 필요한 단계의 수가 N*(log2N)번 만큼의 수행시간을 가짐
  • 퀵 정렬, 병합정렬, 힙 정렬

✔ O(n^2)

2차 시간 : 문제 해결 시 필요한 단계의 수는 입력값 N의 제곱

2차 복잡도 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 N의 제곱수의 비율로 증가한다.

  • 입력값 n이 크다고 가정했기 때문에, 3n, 5n을 O(n)으로 표기하는 것 처럼, n^3과 n^5도 O(n^2)라고 표기한다.
  • 이중 for문, 삽입정렬, 거품정렬, 선택정렬

✔ O(2^n)

지수 시간 : 문제 해결 시 필요한 단계의 수는 주어진 상수 값 C^N

기하급수적 복잡도 exponential complexity 라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

  • 재귀로 구현하는 fibonacci 수열

🧷 시간복잡도 구하기

연산의 횟수를 세고 처리해야 할 데이터의 수 n에 대하여 연산 횟수의 함수 T(n)을 구성

int sum = 0;
for(int i = 0; i < N; i++)
	for(int j = 0; j < i; j++)
    		sum += j;

바깥쪽 반복문 N번, 안쪽 반복문은 i번 반복한다.
i는 0부터 N-1까지 변하고, 안쪽 반복문은 해당하는 i만큼 반복하므로

0 + 1 + 2 + ... + (N - 1) = N*(N-1)/2

등차수열의 합 공식만큼 반복한다. 따라서 O(N^2)이 된다.


int sum = 0;
for(int i = N; i > 0; i /= 2)
	for(int j = 0; j < i; j++)
    		sum += j;
            

바깥쪽 반복문 log N번 반복(i /= 2 이므로)하고, 안쪽 반복문은 i번 반복한다.
i는 N부터 1까지 변하고, 안쪽 반복문은 i만큼 반복하므로

N + N/2 + N/4 + ... + 1 = 2N

따라서 O(N)이 된다.

0개의 댓글