Complexity(복잡도) #

Compuer Science에서 복잡도(Complexity)는 대상 프로그램 혹은 알고리즘의 성능을 평가 할 수 있는 주요한 지표중의 하나로 Computer Compexity Theory 이다. 복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)가 있으며 알고리즘마다 조금씩 다르지만 대체적으로 시간복잡도와 공간 복잡도는 어느정도 Trade off 관계를 가진다.

복잡도를 표현하는 방법 #

복잡도는 거의 대부분 데이터 개수에 따른 수행시간, 혹은 필요공간을 점근 표기법으로 표현한다. 점근 표기법은 5가지의 표기법이 있는데, 컴퓨터 알고리즘에서는 주로 대문자O표기법을 사용하며 가끔 대문자 \klzzwxh:0005 표기법을 사용하는 경우도 있다. Big O를 이용하여 데이터의 복잡도를 계산할때에는 데이터 n에 대한 최고차항의 수를 보통 표기한다.

점근표기법에 대한 더 자세한 내용은 아래 위키를 참조한다.

http://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95

복잡도의 계산 #

어떤 알고리즘의 복잡도는 입력되는 (혹은 수행하는) 데이터수를 이용하여 계산한다.

Time Complexity #

시간 복잡도는 알고리즘의 명령어 수행 횟수를 이용하여 계산한다. 즉, 명령어를 수행하는 횟수가 많을수록 알고리즘을 수행하는데 걸리는 시간은 증가하므로 이를 이용한다.

n개의 데이터를 가진 data 배열을 출력하는 프로그램을 예로 들어보자.

for(int i =0; i< n; i++)
    print(data[i]);

n 개의 데이터를 담고있는 데이터를 출력하는 소스코드에 대해 시간 복잡도는

i < n; *n 번
i++; * n번
print(data[n]); * n 번

\( 3n \) 번 수행 이므로 시간 복잡도는 최고 차항의 계수를 제외한 값인 \( O(n) \) 이 된다.

조금 복잡한 예로 기본 정렬 방법인 Bubble Sortting의 Source Code 및 시간 복잡도를 계산한 결과는 다음과 같다.

source code

for(int j = 0; j<n; j++)
    for(int i =0; i< n; i++){
        if (data[i]>data[j])
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }
}

시간 복잡도 : n (int j for 문) * n (int i for 문) = \( cn^2 \) ( 단 c= 상수) = \( O(n^2) \)

위와 같이 데이터의 양에 따라 얼마나 많은 양의 명령어를 실행하는지를 계산하면 알고리즘의 최악의 경우에서의 시간 복잡도를 계산 할 수 있다.

Space Compliexity #

공간 복잡도는 데이터가 (혹은 문제를 풀기 위해) 얼마나 많은 공간을 할당받는지를 계산하는 방법으로 보통 코드에 변수의 초기화 함수들을 찾으면 대부분 확인 할 수 있으므로 시간 복잡도에 비해 간단하게 계산 된다.

Computer Complexity Theorm #

Computer Science 에서의 복잡도는 알고리즘의 성능을 가늠하는 중요한 지표로 복잡도와 관련된 여러 연구들이 진행되고 있다.

대부분 해결책이 나와 있는 문제들은 P problem(polynomial time 안에 해결 가능한 문제) 이라 정의하며 Worst case에서의 시간복잡도가 다항식으로 표현되지만, 뚜렷한 해결책 없이 모든 경우의 수를 조사해야 하는 문제들인 NP(Non-Polynomial time) Problem 은 \( O(2^n) \)과 같이 지수형태의 복잡도를 가지며, 대표적으로 TSP(Travelling salesman Problem)이 있다.

이에 대한 자세한 내용은 아래 링크를 통해 확인 할 수 있다.

http://en.wikipedia.org/wiki/Computational_complexity_theory

Incoming Links #

Related Data Sciences (DataScience 0) #

• Algorithm

Suggested Pages #

• 1.000 Algorithm/Union-Find
• 0.000 삭제요청
• 0.000 SASS
• 0.000 바이오잉크
• 0.000 About
• 0.000 객체클레스
• 0.000 Q&A
• 0.000 Policy
• 0.000 Chained exceptions
• 0.000 글쓰기 지침
• More suggestions...