알고리즘 지식 – 시간복잡도란?

프로그램이 실행되는 데 걸리는 시간을 대략적으로 나타낸 것.
알고리즘의 효율을 나타내기 위해 사용된다.

왜 쓰는가?


더 품질이 좋은 코드를 만들기 위해서. 게임 개발과 같이 실행 시간이 매우 중요한 분야에서는 코드의 실행 시간을 대략적으로 측정해 쓸데없이 긴 시간을 소요하는 코드를 리팩토링하기 위해서 시간복잡도가  필수적으로 필요하다.

Big-O 표기법


프로그램에서 최악의 경우의 실행 시간을 구하는 표기법. O(x)의 형태로 나타낸다.

종류

n=1 n=2 n=4 n=8 n=16 n=32
O(1) 1 1 1 1 1 1
O(logn) 0 1 2 3 4 5
O(n) 1 2 4 8 16 32
O(nlogn) 0 2 8 24 64 160
O(n2) 1 4 16 64 256 1024

실행 시간 비교

Big_O_notation_graph.jpeg

위의 그래프를 보면 알 수 있듯이, O(nlogn)보다 실행 속도가 느린 경우, 코드 수정이 필수적으로 필요하다.

예시

아래의 코드는 주어진 문자열에서 가장 앞에 있는 특정 문자를 찾는 함수이다.

int find(const std::string str, const char target)
{
    for (int i = 0; i < str.length(); ++i) {
        if (str.at(i) == target)
            return i;
    }
    return 1;
}
cs

위의 코드의 경우, 운이 좋아 찾는 문자가 첫 번째에 있는 경우 실행 시간은 O(1)이 되지만, 최악의 경우 O(N)이 된다. big-O 표기법은 최악의 경우를 생각하는 표기법이므로 위 코드의 최종적인 실행 시간은 O(N)이다.

글쓴이: BakJH

Student of Daedeok SW Meister Highschool, in Korea.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중