기본 콘텐츠로 건너뛰기

추천 가젯

위키피디아를 통한 벤포드법칙 검증

왜 이런 짓을 하는가? 학교에서 벤포드 법칙과 관련하여 활동을 해서 소감문을 제출하라고 한다. 물론 학교에서는 통계청 에서 제공하는 데이터 차트 같은 한 만개에서 십만개 정도 데이터를 조사하라고 하긴 했는데, 마침 친구가 나무위키의 약 50만개 문서 (리다이렉트, 사용자문서 제외)의 5천만개 숫자를 가지고 분석을 돌렸길래 나는 좀더 크게 영문 위키피디아 에 있는 숫자들을 대상으로 조사하기로 했다. 벤포드 법칙이란? 우선 분석 글을 시작하기 전에 벤포드 법칙이 무엇인지부터 간단히 설명을 하고 시작을 하겠다. 벤포드 법칙이란 1938년에 물리학자 프랭크 벤포드가 자기 논문에서 제시한 법칙으로, 간단히 말하면 "수치를 나타내는 수" 에서 수의 첫자리가 낮을 확률이 높다 라는 간단하지만 신기한 법칙이다. 자세한 설명은 나무위키가 해줄 것이다. 1. 위키피디아 데이터베이스 덤프 다운로드 우선 분석을 하기 위해서는 당연하지만 위키피디아의 데이터베이스가 필요하다. (위키피디아 전체 를 크롤링하기에는 아주 오래걸릴 뿐더러, 위키피디아의 서버에 부하를 주기 때문에 가능성은 낮겠지만 크롤링하는 중간에 위키피디아에서 접속을 차단할 수도 있다.) 다행히도, 위키피디아는 우리 같이 위키피디아의 데이터베이스를 활용하려는 사람들을 위해서, (물론 위키피디아 서버를 백업하려는 목적도 있지만) 위키피디아 전체의 XML 덤프 를 제공한다. 여기 에서 위키피디아의 데이터베이스를 비트토렌트를 이용하여 다운로드 할 수 있다. 토렌트 말고 직접 다운로드 링크도 주어지지만... 속도가 처참하기 때문에 토렌트로 다운로드 하는 것을 권장한다. (약 2~3 MB/s의 속도로 다운로드가 되는데, 총 파일이 20GB가량 되기 때문에 서너시간 정도 걸린다. 물론 토렌트 특성상 더 빠를수도 느릴수도 있다.) 그리고 bz2 압축을 해제한다. 윈도우라면 위대하신 반디집 을 이용하여 압축을 해제할 수 있고, 리눅스면 bzip2를 이용하면 해제할 수 있다. 뭐 리눅스 유저면 알...
댓글 쓰기
Read more »
태그
Labels:

알고리즘 복잡도와 빅오표기법

알고리즘의 성능은 어떻게 비교할 수 있을까?

알고리즘은 어떠한 목적을 달성하기 위한 과정을 의미합니다.
정렬, 탐색과 같은 동작에 대해 이미 다양한 알고리즘이 존재하고, 각각의 알고리즘에 대한 장단점이 존재하지만, 알고리즘의 평가에서 가장 중요한 항목은 소요되는 시간과 사용되는 메모리라고 할 수 있겠죠.

이때 우리가 알고리즘의 소요시간과 사용되는 메모리를 정확하게 알 수 없으므로, 우리는 시간복잡도와 공간복잡도라는 개념을 이용하여 알고리즘을 평가하게 됩니다.

시간복잡도(Time Complexity)

시간복잡도는 자료의 수가 증가함에 따라 소요시간이 늘어나는 패턴을 나타낸 것입니다.
"소요시간이 늘어나는 패턴" 이라는 개념이 잘 이해 되지 않을 수 있으니 예시를 들어보겠습니다.
n과 n의 곱을 구하는 알고리즘을 세가지 생각해 볼 수 있습니다.
  1. n에 n을 곱한다.
  2. n을 n번 더한다.
  3. 1을 n번 더하는 것을 n번 반복한다.
각각의 의사코드는 아래와 같습니다.

만약 n=3이라고 하면, 각 알고리즘에 대한 연산 시간을 구해봅시다.
덧셈연산에 대한 시간복잡도는 O(n), 곱셉연산에 대해서는 O($n^{2}$)으로
일반적으로 두 연산에 대한 수행 시간이 다르지만, 설명을 위해 둘의 수행 시간이 같다고 가정하겠습니다.
  1. 번 알고리즘은 곱셈연산 한번, 대입연산 한번으로 연산이 끝납니다. 수행시간을 2라고 합시다.
  2. 번 알고리즘은 덧셈연산 3번, 대입연산 3번으로 곱셈이 이뤄집니다. 이때 수행시간은 6입니다.
  3. 번 알고리즘은 덧셈연산 3번, 대입연산 3번을 3번 반복하므로 총 18번의 연산이 이뤄집니다. 수행시간도 18.
그럼 n=10일때는 어떻게 될까요?
  1. 번 알고리즘은 역시 곱셈연산 한번, 대입연산 한번으로 연산이 끝납니다. 수행시간은 2.
  2. 번 알고리즘은 덧셈연산, 대입연산이 20번 이뤄집니다. 수행시간은 20.
  3. 번 알고리즘은 덧셈연산, 대입연산 20번을 10번 반복합니다. 수행시간은 200이 됩니다.

이렇게 알고리즘에 따라서 데이터 양이 늘어날때 소요시간이 늘어나는 경향성이 다름을 볼 수 있습니다.
대략 1번 알고리즘은 2, 2번 알고리즘은 2n, 3번 알고리즘은 $2n^{2}$의 소요시간을 지닙니다.

점근적 표기법(Asymptotic notation)

위의 예시에서, 우리는 계산하는데 필요한 연산 수로 시간복잡도를 평가했습니다.
하지만 실제 프로그램에서, 알고리즘을 수행하는데 필요한 연산 수를 전부 세는 것은 거의 불가능할 뿐더러, 필요하지도 않습니다. 대신 우리는 시간복잡도의 입력 크기에 따른 함수의 증가율, 즉 성장률에 집중하여 시간복잡도를 표기하며,
이를 점근적 표기법이라고 부릅니다.

대표적인 복잡도의 점근적 표기법에는 아래의 세가지가 있습니다.
  • 빅오(O)표기법 : 최악의 경우
  • 빅세타(θ)표기법 : 평균의 경우
  • 빅오메가(Ω)표기법 : 최선의 경우
이외에도 스몰오(o)표기법, 스몰오메가(ω)표기법 등의 다양한 표기법이 있습니다. 수학적인 엄밀한 정의는 위키백과를 참조해주세요.

평균의 경우인 빅세타표기법으로 표기하면 좋겠지만 "평균의 경우"를 구하기가 여간 까다로운게 아니라 잘 사용하지 않고, 최선의 경우의 알고리즘 복잡도는 평균과 크게 동떨어진 경우가 많기 때문에 빅오메가표기법 또한 잘 사용하지 않습니다. 따라서 알고리즘의 시간복잡도를 표현할 때는 주로 빅오표기법을 이용합니다.

알고리즘의 복잡도를 빅오표기법으로 표현하는데는 아래의 두 과정을 거칩니다.
  1. 계수를 무시
    빅오표기법은 입력되는 데이터의 크기가 충분히 크다고 가정하고, 따라서 계수를 무시할 수 있습니다.
    O(2n)->O(n)
  2. 영향력이 적은 항을 무시
    입력되는 데이터의 크기가 충분히 크므로 낮은 차수의 항을 무시할 수 있습니다.
    극한을 배웠다면 이해하기 쉬울 것이라고 생각합니다.
    O($n^{3}+2n^{2}+3$)->O($n^{3}$)
아래는 주로 사용되는 빅오표기법의 그래프입니다.
image
당연하지만 문제의 종류에 따라 알고리즘의 평가 기준이 다릅니다.
정렬알고리즘에서 시간복잡도 O(n)의 알고리즘은 매우 빠른 알고리즘이지만 탐색알고리즘에서 시간복잡도 O(n)은 최악의 경우입니다.
O($2^{n}$)와 O($n!$)의 시간복잡도를 가진 알고리즘은 매우 비효율적인 알고리즘이며 쓰지 말아야 할 것 같지만,
문제에 따라 그러한 알고리즘을 쓸 수 밖에 없는 문제도 있습니다.

공간복잡도(Space Complexity)

공간복잡도는 프로그램을 실행시키고 완료하는데 필요한 메모리 공간의 양이 자료의 수에 따라 증가하는 패턴을 나타낸 것이며, 시간복잡도와 마찬가지로 점근적 표기법을 이용합니다.
일반적으로 알고리즘이 사용하는 메모리의 크기는 데이터의 양에 지수적으로 비례하지 않기 때문에 알고리즘의 평가에서 공간복잡도는 무시되는 경향을 띄지만, 동적계획법과 같은 알고리즘은 꽤 많은 메모리 자원을 소비하기 때문에 메모리가 적은 하드웨어(대표적으로 아두이노)에서는 사용할 수 없는 경우가 있고, 간혹 데이터 크기에 대한 다항공간크기의 메모리로 해결할 수 없는 문제도 있기 때문에 이럴 때는 공간복잡도도 중요하게 보게 됩니다.


이론적으로는 시간복잡도와 공간복잡도 모두 간단한 알고리즘이 최고의 알고리즘이라고 볼 수 잇지만, 일반적으로 소요시간과 메모리사용량은 반비례하는 경향을 띄기 때문에 둘 중 하나는 포기해야 하며, 상황에 따라 적절한 알고리즘을 선택해야 합니다.

댓글

댓글 쓰기