[ ALGORITHM ] 알고리즘 복잡도 ( Complexity )

[ ALGORITHM ] 알고리즘 복잡도 ( Complexity )

 

 

 

📚 Table of Contents

 

 

 

 

 

 

알고리즘의 효율성 / 성능

알고리즘 효율성은, 계산에 필요한 자원 소요량이 적을수록 좋다.

 

    - 시간과 공간 측면에서 적게 소요되는 것이 효율적이고 좋은 알고리즘 이다.

 

 

 

 

 

복잡도 ( Complexity )

알고리즘 성능을 나타내는 척도이다.

 

 

 

 

시간 복잡도 ( Time Complexity )

주로, 수행 시간 관점에서, 알고리즘이 사용 한 기본 연산의 수를 의미한다.

 

 

 

 

상수 시간 알고리즘 ( constant time algorithm )

O(c) 또는 O(1)

 

입력 크기(개수)에 관계없이, 항상 일정한 수행 속도를 갖는다.

 

가장 효율 적이다.

📒예시

배열에 있는 항목을 인덱스를 사용하여 접근할 때

집합 내 요소로의 접근

 

 

 

로그 시간 알고리즘 ( logarithmic time algorithm )

O(log n)

 

로그 함수 형태 알고리즘 ( 밑이 2인 로그함수 : log2 )
   - 데이터가 2배로 증가할 때, 연산수가 1단계식 늘어나는 형태

입력 개수가 증가하면서 포물선 곡선이 한쪽으로 수렴한다.
    - 데이터가 많아질 수록 좋다.

 

📒예시

이진 검색

 

 

 

선형 시간 알고리즘 ( linear time algorithm )

O(n)

 

선형 함수 형태 알고리즘

    - 입력 개수에 단순 비례적으로 수행 시간이 길어진다.

 

입력 개수 만큼 연산을 수행한다.

 

📒예시

중첩되지 않은 통상의 반복문

선형 검색

자연수의 거듭제곱

 

 

 

로그 선형 시간 알고리즘 ( nlogn time algorithm )

O(n log n)

📒예시

반복문 증가 스텝이 2의 배수로 하여 2, 4, 8, 16 처럼 증가하는 경우

병합정렬

 

 

 

평방 시간(2차 시간) 알고리즘 ( quadratic time algorithm )

O(n2)

 

문제 해결 단계의 수가 입력 값 n의 제곱으로 증가

- n이 적을 경우에만 사용해야 하는 느리고 비효율적인 알고리즘이다.

 

📒예시

2번 중첩된 반복문 (이중 for 문)

버블 정렬

삽입 정렬

선택 정렬

 

 

 

다항식 시간 알고리즘 ( polynomial time algorithm )

O(nk)

 

입력 크기에 대한 다항식으로 나타내는 알고리즘
    - 다항식 : 입력 n 과 nk ( n의 상수 거듭제곱 ) 들의 선형 결합으로 이루어진 식
    - O(n),O(n2),O(n3), ... O(nk) 모두를 가리킴

 

주로, 중첩된 반복문의 수행 횟수를, 입력 크기를 다항식으로 표현할 수 있는 알고리즘이다.

    - 다항 시간 내 풀 수 있으면, 다루기 쉬운 (tractable), P 문제라고 한다
    - 다항 시간 내 풀 수 없으면, 다루기 힘든 (intractable), NP 문제라고 한다.

 

 

 

지수 시간 알고리즘 ( exponential time algorithm )

O(2n) 또는 O(rn)

 

n이 하나 증가할 때 마다, 걸리는 시간이 그전보다 2배 또는 r배로 걸리는 매우 나쁜 알고리즘이다.

 

 

 

계승 시간 ( factorial time algorithm )

O(n!)

 

지수 시간 보다 더 많이 걸린다.

 

따라서, 초 지수 시간 이라고도 한다.

 

 

 

무한 루프

O(∞)

 

종료되지 않는 무한 루프이다.

 

 

 

 

 

공간 복잡도 ( Space Complexity )

알고리즘 계산에 소요되는 컴퓨터 메모리를 의미한다.

 

총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며

 

수식으로는 S(P)=c+SP(n) 으로 표기한다.

 

 

 

 

고정 공간

고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말한다.

 

 

 

 

가변 공간

가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간을 말한다.

 

오늘 날에는 공간복잡도는 덜 중요하게 되었다. 다만, 빅데이터 처리에는 공간 복잡도도 중요하다.

 

 

 

 

 

reference

시간복잡도와 공간복잡도(Time Complexity Space Complexity)

알고리즘 효율성