알고리즘에 관하여.....
오늘 컴공과 선배를 만나 알고리즘에 관해 이야기를 나누었습니다....
아직 학부 2년생인 저는 이번에 알고리즘 과목을 처음 듣는 것이었지요...
이야기를 나누던중 한가지 부분에서 의견대립이 일어났습니다..
과제를 수행할때....선배의 경우 알고리즘을 구현하고, 수행시간을 구해서 제출을 한다고 합니다.
저의 경우는 시간 복잡도를 이론으로 구해서 제출을 했구요.
여기서 이야기가 시작되었습니다.
처음, 과제를 제출할 때 저도 수행시간을 구해서 과제를 제출을 했더랬지요...
하지만, 교수님께서 그 과제를 보시고 자신의 컴퓨터에서 수행한 수행시간이 무슨 의미가 있냐고 엄청 혼을 내셨습니다.
그래서 그 다음부터 과제를 제출할 때, 항상 이론의 시간복잡도를 함께 구하여 제출을 하였습니다.
그런데, 컴공과 선배가 수행시간을 찍어서 제출을 한다고 하길래...그건 별로 의미가 없다고 교수님께서 '카더라~'라고 했다고 전해주었습니다. 하지만, 선배의 이야기(즉, 컴공과 교수님)는 저희과 교수님과는 달랐습니다.
(n^2) 의 시간복잡도를 가지는 알고리즘과 (n^2 + n) 의 시간 복잡도를 가지는 알고리즘이 있을때...
두개의 알고리즘은 서로 빅O의 경우 같은 시간복잡도를 가진다. 하지만...실제로 프로그래밍을 하는 입장에 있다면 그것이 정말 같은 알고리즘으로 취급될 수 있을까...?
그리고, 과연 이론으로서의 시간복잡도와 실제 프로그래밍에서 확인한 수행시간중 어느것이 더 중요한가?
라는게 요지였습니다.
물론 간단하게 생각한다면 당연히 n^2 알고리즘이 더 효율적인 것이고, 이론보다야 실제로 확인한 것이 더 중요하겠지요..
하지만 제가 보았던 책들(Introduction to algorithms, foundation of algorithms)에서는 컴퓨팅에서의 시간은 그리 중요하지 않다고 이야기합니다....
뭔가 그것이 아니라는것은 알겠는데 막상 피부에 와 닿은것은 그게 또 아니네요...
무엇이 진실인가요..?
-----------------------------------------------------------------
참고로 저는 정통학부 정보통신전공(2), 선배는 컴퓨터공학과(3) 입니다.
물론 배우는 교수님은 서로 다릅니다.
조금있다가 학교에
조금있다가 학교에 가면 교수님께 확인을 해볼 생각이지만....
잠못드는 이밤....하도 생각이나서 글을 올려봅니다.
여러분들의 생각은 어떠하신가요..
---------------------------------
제일 왼쪽이 저입니다 :)
---------------------------------
제일 왼쪽이 저입니다 :)
제 생각에는
제 생각에는 이론적인 시간이 좀 더 중요하지 않을까 합니다...
실제 시스템에서 실행되는 시간은 잘 아시다시피, 천차만별이고 시스템의 종류와 상태에 따라서 모두 다릅니다...
(같은 알고리즘의 같은 프로그램이 비슷한 스팩의 x86과 Sun에서 몇 배의 차이를 보일 수도 있습니다...)
이론적인 시간이 중요한 것은 그것이 시스템의 상태나 종류에 무관한, 실제로 필요한 계산량만을 다루고 있기 때문입니다...
이론적인 시간 복잡도는 n 값의 절대적인 값보다는, n 값의 변화와 밀접한 관계가 있습니다... 즉, n^2 복잡도를 갖는 알고리즘의 경우에, 어떤 시스템에서 n 이 2배로 증가했을 때, 4배의 연산량이 필요하다는 것... 이것이 이론적인 시간 복잡도의 핵심이라고 봅니다...
이론적인 시간이 실제 시스템에서 어떻게 적용될 수 있느냐 하는 것은 각 시스템 implementation의 몫이고 그 차이점을 알고 있는 것이 프로그래밍의 Know-How라고 할 수 있는 것이겠지요...
그리고 위에서 예로 드신 O(n^2)와 O(n^2 + n)에 대해서는 그 우열을 가릴 수가 없습니다...
위에서도 말씀드렸다시피, 이론적인 시간 복잡도의 경우, n의 변화량에 핵심이 있기 때문에, n앞에 붙는 계수를 무시한 식입니다...
다시 말씀드려서, O(n^2)의 계수가 100이고 O(n^2 + n)의 계수가 10인 경우에는 O(n^2 + n)이 훨씬 수행 시간이 빠른 겁니다...
O(...) 식의 핵심은 n의 변화에 따라 연산량이 얼마나 변하느냐를 논하는 것이지 같은 O(...)를 가지는 알고리즘의 우열을 비교하는 것이 아닙니다...
분류의 목적과
분류의 목적과 측정의 목적은 다릅니다.
제 생각에 알고리듬 이론에 흔히 등장하는 O() 표기법은 측적용이라기보단
분류할 의도로 고안된겁니다.
무엇을 분류하냐? 당근빠다~ 알고리듬들을 분류하는거죠...
각 알고리듬들의 집합을 서로 다른 family로 묶어서
얘네들은 이런 유형이다...쟤네들은 저런 유형이다..
일단 이렇게 해 놓으면 서로 다른 family간의 일반화된 성능차이가 나오게 됩니다.
쉽게 얘기해서 이런걸 보려고 만든게 그 이론입니다.
따라서 O표기법은 알고리듬family간 비교에선 의미가 있지만
동일 family내의 서로 다른 알고리듬간 비교는 무의미하게(동일하다고)
만들어버립니다.
때문에 이 이론을 알고리듬의 성능 '측정용' 도구로 오인하지 않는게 중요하다고 생각합니다.
특정 알고리듬의 시간복잡도가 얼마다..라는건 그 알고리듬이 속한 집단의 일반화된
평균값이라고 보면 됩니다.(비록 실제로 평균개념이 들어가는건 아니지만)
다시 말해서 O표기법은 대체적인 가늠값은 될 수 있어도 정밀한 측정값은 될 수 없습니다.
이를 쉽게 이해하기 위해선 다음의 비유가 도움이 될겁니다.
치열한 비평준화 고등학교 A가 있고
그저그런 평준화 고교 B가 있다고 했을때
(1) A의 성적 > B의 성적
이라는 결론을 내리는건 아무 문제가 없는 일이지만
A에 속한 학생 a1, a2가 획득한 성적의 대소관계는
(1)로부터 아무것도 함축되어 나오지 않는다는겁니다.
오히려 O표기법은
(2) A의 성적 == a1의 성적 == a2의 성적
라는 비현실적인 가정만을 강요하죠..
그러나 누구든 (2)가 참이 아니라는걸 잘 압니다.
(2)를 확인하기 위해선 세부적인 변수를 따져보고
컴퓨터로 실제 돌려보는 수고를 해야 한다는겁니다.
그리고 여기서 (1), (2)의 개념차이가 확실하게 드러나게 되는걸 발견하죠...
(1)을 확인하는건 집단간 성능 분류의 문제입니다.
(2)를 확인하는건 집단내 성능 측정의 문제입니다.
결론적으로 그 선배는 (2)를 좀 더 신중하게 고려했던것이고
성태님은 (1)문제에 좀 더 초점을 맞춘것이죠..
저는 그것이 그런 차이라고 생각합니다.
둘 다
둘 다 중요합니다.
Big O notation은 n이 충분히 클 때 의미가 있는 것이지 아주 적을 때에는 큰 의미가 없습니다.
전산에서 알고리즘은 프로그램으로 특정 컴퓨터 위에서 구현될 수 있기 때문에 의미를 가지는 것이지 머리 속에서만 중요도를 따지는 것은 큰 의미가 없습니다. n이 적은 경우에는 이 알고리즘, n이 클 경우에는 저 알고리즘을 써서 구현하는게 적절합니다. if 문으로 구별하면 되겠지요.
또 병렬처리를 할 때에는 더 빠른 알고리즘이 달라지기도 합니다. 각 processing unit에 잘 나누어서 일거리를 배정할 수 있느냐가 더 중요해지지요.
단순히 Big O notation에 따라 공부한다면 승수가 높은 것은 아예 배울 필요도 없는 알고리즘이지만 실제는 상황에 따라 사용할 경우가 있기 때문에 배워둬야 합니다.
추가로 예를 더
추가로 예를 더 든다면 3D graphics card의 사례가 있습니다.
다른 알고리즘이 일반 PC 프로그램에서는 더 빠른 경우가 있지만 하드웨어의 제약이 있는 card에 구현하기 위해 계산하기 간단한 알고리즘을 채택을 한 경우입니다.
그리고 나중에 간단한 특성 때문에 pipeline, 병렬처리가 가능해져서 다른 알고리즘은 이제 책에서만 볼 수 밖에 없는 현재 상황이 되었지요.
단순한 PC 프로그램에 국한해서 본다면 Big O notation이 중요하고 실행 시간의 중요도는 전체적으로 봤을 때 점점 줄어드는 것은 맞습니다. GUI같은 상호 작용을 많이 하는 경우에 0.01초에 반응이 오나 0.05초에 반응이 오나 어느 임계점을 넘기만 하면 사용자는 느끼지 못하지요. CPU나 기타 장치들이 더 빨라질수록 실행시간의 중요도는 떨어집니다.
하지만 그것도 통계적인 의미일 뿐 자신이 실제 무엇을 만드느냐에 따라 실행시간이 더 중요할 수 있습니다.
또 학계에서는 논문을 쓰는 것이 중요(?)한 일이기 때문에 Big O notation이 중요하게 평가를 받는 경향이 있습니다.
두 분의 교수님
두 분의 교수님 모두(저희과 교수님, 컴공과 교수님) 같은 말씀을 주셨습니다.
n^2, n^2 + n 중, 어느 알고리즘을 사용해도 프로그램의 성능에 큰 영향을 주지 않는다.
왜냐하면..n^2 과 n^2 + n에서 n번을 수행할때 마다 걸리는 시간이 시스템마다 같다고 이야기 할 수 없기 때문이다...
라고 말씀을 주셨습니다.
즉, n을 수행하는 명령어가 시스템마다 다르기 때문에..(ex. i386, Sparc..등등) 시간으로 측정하는 것은 의미가 없다고 하셨습니다.
그렇다면..왜 시간을 측정하라고 하셨는냐...고 질문을 드리자, 프로그램을 만들어서 직접 피부로 느껴보라는 것이었답니다. n^2 과 n^2 + n 과 같은 동일한 O의 시간을 가지는 알고리즘이 아닌, 서로 다른 O를 가지는 알고리즘을 비교함으로써 어느 알고리즘이 더 효율적인 피부로 느껴보게하기 위해 그런 과제를 내라고 하셨다는 군요.
...이제야 맘놓고 시험공부를 할 수 있겠군요....월욜부터 시험인데...이런..;;;
---------------------------------
제일 왼쪽이 저입니다 :)
---------------------------------
제일 왼쪽이 저입니다 :)
n이 작을때 (10이나
n이 작을때 (10이나 100정도면) n^2알고리즘이나 n^2+n알고리즘이나 (어차피 컴퓨터는 빠르니)눈깜짝 할 사이에 답이 나옵니다. 그래서 이런경우는 두 알고리즘의 차이는 중요하지 않습니다. (물론 매우 빠른 응답속도를 요하는 특수한 경우는 제외..)
그리고 n이 1000정도만 되도 n^2 = 1000000, n^2+n = 1001000이니까 0.1%의 차이밖에 나지 않습니다.
n이 더 커지면 둘의 성능차이는 더욱더 구분하기 힘듭니다.
결국 n^2이나 n^2+n이나 구분하는거는 별 의미 없고 O(n^2)으로 표현합니다.
정보올림피아드나 ACM ICPC같은 대회에서 나오는 문제들을 풀어보면 시간복잡도가 얼마나 중요한지 알수 있습니다.
시간복잡도를 이용해서 자신이 짠 알고리즘이 제한시간안에 종료할지를 알수 있습니다.
예를들어 입력크기(n) 제한이 4000 ~ 5000 정도면 보통 O(n^2)의 알고리즘으로 풀 수 있습니다.
그보다 크면 O(n log n) 알고리즘을 써야되고
만약 n이 100만 이상이면 O(n)정도는 되야 됩니다.
반면 시간복잡도가 O(n!)이나 O(2^n)이면 n이 20정도만 되도 제한시간안에 나오기 힙듭니다.