대학교에서 알고리듬 과목을 수강하게 되면
자료구조 & 알고리즘 :
2007. 3. 14. 23:40
반응형
대학교에서 알고리듬 과목을 수강하게 되면
적어도 한학기 정도는 계산복잡도에 대해 배우게 됩니다.
그것도 상당히 대충대충 쉬운 부분만 다루는 것이고
깊이 파고들면 1년을 공부해도 부족합니다.
이곳에서 설명한다는것 자체가 어불성설이고,
자세한 내용은 관련서적을 찾아보기 바랍니다.
여기서는 대략적인 개념만 주도록 하겠습니다.
1. 계산하는데 얼마나 오랜시간이 걸리는가를 따지는것입니다. 어떻게 보면 알고리듬의 성능을 비교할때 계산복잡도를 비교하는 것입니다.
2. 단지 알고리듬의 성능을 비교하는 것이니
얼마나 빨리 계산 하는가를 비교할때 컴퓨터의 성능같은 것에 영향을 받으면 안되겠죠..
그래서 계산하는데 걸리는 시간을 재는게 아니라 계산할때 *연*산*을 몇번 했느냐로 따집니다.
연산의 기준은 계산복잡도를 다루는 분야에 따라 조금씩 다르게 정의하긴 하지만
수치해석쪽에는 대략 한번더하고 한번 곱하는걸 합쳐서 한번 연산으로 취급하고
컴터 하드웨어를 생각하는 사람은 기계어 명령 하나를 하나의 연산으로 취급하기도 합니다.
3. 그런데 생각해보면 입력데이터의 길이에 걸리는 시간이 달라지겠죠?
때문에 입력데이터의 길이(속편하게 byte 나 글자수 정도로 생각하세요)에 대한 함수로
계산복잡도를 정의합니다.
4. 예를들어 입력된 데이터의 길이가 n 이라하면 계산복잡도가 n^3 + 2n +10 뭐 이런식으로 표현할수 있겠습니다. 입력데이터가 10글자라면 10^3+20+10=1030번 연산을 해야 결과가 나온다는 뜻입니다.
5. 결국 계산복잡도를 비교한다는 것은 n 에관한 함수를 비교한다는 것과 마찬가지가 됩니다.
6. 그렇다면 어떤 함수가 더큰지 어떤 기준으로 비교하느냐?가 문제가 됩니다.
숫자사이에는 대소관계를 자연스럽게 비교할수 있지만 함수는 단순한 숫자가 아니니까요...
계산복잡도함수사이를 비교하는 방법으로 사용하는것이 몇가지 있습니다만
자세히 설명하려면 고등학교 범위를 넘어가고요..
쉽게생각해서 큰수를 넣었을때 어떤게 더 커지냐 즉..
즉 입력데이터의 크기에 비례해서 얼마나 더 빨리 커지느냐를 가지고 비교하는 것입니다.
7 계산복잡도 함수는 그 특성상 증가함수라는게 상식적입니다.
10n^2 과 n^3 을 비교한다면 처음 작은 데이터를 볼때는 10n^2 이 더 오래걸리겠지만
입력데이터가 커지면 10n^2 이 훨씬 빨리 계산합니다. n=10000 이라면 10n^2 이 천배빨리계산하겠죠.
때문에 계산복잡도 에서 중요한것은 최고차항의 차수입니다.
최고차항의 차수가 크면 무조건 나중에 가면 더 계산하는데 오래걸린다고 볼수있죠..
차수가 같으면 최고차항의 계수가 큰쪽이 더 계산복잡도가 큽니다.
8. 이론적으로 따질때는 차수가 같으면 같은 계산복잡도를 가진다고 말합니다.
계산복잡도를 비교할때 다른 요소는 사실 중요하지 않다는 뜻이죠...
계산복잡도함수에다가 상수로 몇배하는것은 그리 계산복잡도에 결정적인 영향을 안준다고 판단합니다.
차수를 0.1이라도 낮추는게 중요하죠.. (차수가 자연수가 아닌경우도 있습니다. 관련서적을 보세요)
9. 예를하나 들겠습니다. 일반적인 행렬곱셈은 n^3의 계산복잡도를 가집니다.
예를들어 백만x백만 행렬 을 곱한다고 했을때 데이터의 길이가 백만x백만 을 세제곱한것 만큼 연산을 해야 답이 나오겠죠? 이럴때는 사실 계산복잡도를 1/10으로 줄이는 것보다
차수를 조금이라도 낮추는게 훨씬 효과적입니다.
10. 계산복잡도가 다항식이 아닌경우도 있습니다. 이럴경우에는 현실적으로 계산불가능합니다
예를들어 계산복잡도가 2^n 일경우 데이터가 백개만 되도 천문학적인 숫자가 나옵니다.
얼마안되는 입력데이터가지고도 현존하는 가장빠른 슈퍼컴퓨터로 백만년을 계산해야한다는 결과도 쉽게 만들수 있습니다. 현실적으로 풀이방법(계산알고리듬)이 지수일경우는 풀수 없는 문제나 다름없습니다.
11. 아직까지는 지수적으로 밖에 해결알고리듬을 찾지 못했지만 답이 주어졌을때 맞는답인지 틀린답인지 다항식계산복잡도 이내로 확인할수 있는문제를 NP 문제라고 합니다. 여기서부터 P=NP문제가 시작되었습니다.
12. 계산복잡도를 줄이는 문제는 전산에서 아주아주 중요한 문제이기때문에 P=NP문제는 미해결 문제중에서 실제적으로도 아주 중요한 문제라고 할수있습니다.
13. 퀀텀컴퓨터는 기존컴퓨터에서 지수적으로밖에 풀수 없는 문제를 다항시간에 풀수 있다고 알려져 있습니다. 하지만 현재까진 이론적으로만 그리고 아주제한적으로 실험실에서만 성공했습니다.
아직까지 많은 학자들이 매달려 연구하고 있습니다.
14. 지금까지 아주 맛보기만 설명한것입니다.
괜찮은 참고 서적을 소개하겠습니다.
Introduction to algorithm
: 저자는 기억안나는데 원서이고 알고리듬에 관한 공부를 할때 바이블이라고 생각됩니다. 아주 잘 쓰여진 책입니다.
적어도 한학기 정도는 계산복잡도에 대해 배우게 됩니다.
그것도 상당히 대충대충 쉬운 부분만 다루는 것이고
깊이 파고들면 1년을 공부해도 부족합니다.
이곳에서 설명한다는것 자체가 어불성설이고,
자세한 내용은 관련서적을 찾아보기 바랍니다.
여기서는 대략적인 개념만 주도록 하겠습니다.
1. 계산하는데 얼마나 오랜시간이 걸리는가를 따지는것입니다. 어떻게 보면 알고리듬의 성능을 비교할때 계산복잡도를 비교하는 것입니다.
2. 단지 알고리듬의 성능을 비교하는 것이니
얼마나 빨리 계산 하는가를 비교할때 컴퓨터의 성능같은 것에 영향을 받으면 안되겠죠..
그래서 계산하는데 걸리는 시간을 재는게 아니라 계산할때 *연*산*을 몇번 했느냐로 따집니다.
연산의 기준은 계산복잡도를 다루는 분야에 따라 조금씩 다르게 정의하긴 하지만
수치해석쪽에는 대략 한번더하고 한번 곱하는걸 합쳐서 한번 연산으로 취급하고
컴터 하드웨어를 생각하는 사람은 기계어 명령 하나를 하나의 연산으로 취급하기도 합니다.
3. 그런데 생각해보면 입력데이터의 길이에 걸리는 시간이 달라지겠죠?
때문에 입력데이터의 길이(속편하게 byte 나 글자수 정도로 생각하세요)에 대한 함수로
계산복잡도를 정의합니다.
4. 예를들어 입력된 데이터의 길이가 n 이라하면 계산복잡도가 n^3 + 2n +10 뭐 이런식으로 표현할수 있겠습니다. 입력데이터가 10글자라면 10^3+20+10=1030번 연산을 해야 결과가 나온다는 뜻입니다.
5. 결국 계산복잡도를 비교한다는 것은 n 에관한 함수를 비교한다는 것과 마찬가지가 됩니다.
6. 그렇다면 어떤 함수가 더큰지 어떤 기준으로 비교하느냐?가 문제가 됩니다.
숫자사이에는 대소관계를 자연스럽게 비교할수 있지만 함수는 단순한 숫자가 아니니까요...
계산복잡도함수사이를 비교하는 방법으로 사용하는것이 몇가지 있습니다만
자세히 설명하려면 고등학교 범위를 넘어가고요..
쉽게생각해서 큰수를 넣었을때 어떤게 더 커지냐 즉..
즉 입력데이터의 크기에 비례해서 얼마나 더 빨리 커지느냐를 가지고 비교하는 것입니다.
7 계산복잡도 함수는 그 특성상 증가함수라는게 상식적입니다.
10n^2 과 n^3 을 비교한다면 처음 작은 데이터를 볼때는 10n^2 이 더 오래걸리겠지만
입력데이터가 커지면 10n^2 이 훨씬 빨리 계산합니다. n=10000 이라면 10n^2 이 천배빨리계산하겠죠.
때문에 계산복잡도 에서 중요한것은 최고차항의 차수입니다.
최고차항의 차수가 크면 무조건 나중에 가면 더 계산하는데 오래걸린다고 볼수있죠..
차수가 같으면 최고차항의 계수가 큰쪽이 더 계산복잡도가 큽니다.
8. 이론적으로 따질때는 차수가 같으면 같은 계산복잡도를 가진다고 말합니다.
계산복잡도를 비교할때 다른 요소는 사실 중요하지 않다는 뜻이죠...
계산복잡도함수에다가 상수로 몇배하는것은 그리 계산복잡도에 결정적인 영향을 안준다고 판단합니다.
차수를 0.1이라도 낮추는게 중요하죠.. (차수가 자연수가 아닌경우도 있습니다. 관련서적을 보세요)
9. 예를하나 들겠습니다. 일반적인 행렬곱셈은 n^3의 계산복잡도를 가집니다.
예를들어 백만x백만 행렬 을 곱한다고 했을때 데이터의 길이가 백만x백만 을 세제곱한것 만큼 연산을 해야 답이 나오겠죠? 이럴때는 사실 계산복잡도를 1/10으로 줄이는 것보다
차수를 조금이라도 낮추는게 훨씬 효과적입니다.
10. 계산복잡도가 다항식이 아닌경우도 있습니다. 이럴경우에는 현실적으로 계산불가능합니다
예를들어 계산복잡도가 2^n 일경우 데이터가 백개만 되도 천문학적인 숫자가 나옵니다.
얼마안되는 입력데이터가지고도 현존하는 가장빠른 슈퍼컴퓨터로 백만년을 계산해야한다는 결과도 쉽게 만들수 있습니다. 현실적으로 풀이방법(계산알고리듬)이 지수일경우는 풀수 없는 문제나 다름없습니다.
11. 아직까지는 지수적으로 밖에 해결알고리듬을 찾지 못했지만 답이 주어졌을때 맞는답인지 틀린답인지 다항식계산복잡도 이내로 확인할수 있는문제를 NP 문제라고 합니다. 여기서부터 P=NP문제가 시작되었습니다.
12. 계산복잡도를 줄이는 문제는 전산에서 아주아주 중요한 문제이기때문에 P=NP문제는 미해결 문제중에서 실제적으로도 아주 중요한 문제라고 할수있습니다.
13. 퀀텀컴퓨터는 기존컴퓨터에서 지수적으로밖에 풀수 없는 문제를 다항시간에 풀수 있다고 알려져 있습니다. 하지만 현재까진 이론적으로만 그리고 아주제한적으로 실험실에서만 성공했습니다.
아직까지 많은 학자들이 매달려 연구하고 있습니다.
14. 지금까지 아주 맛보기만 설명한것입니다.
괜찮은 참고 서적을 소개하겠습니다.
Introduction to algorithm
: 저자는 기억안나는데 원서이고 알고리듬에 관한 공부를 할때 바이블이라고 생각됩니다. 아주 잘 쓰여진 책입니다.
반응형
'자료구조 & 알고리즘' 카테고리의 다른 글
| 만약 다시 알고리즘 공부를 한다면? (0) | 2007.03.14 |
|---|---|
| 배열,포인터,링크드리스트,스택,큐 이해 (0) | 2007.03.14 |
| 그래프 알고리즘 연습. (0) | 2007.03.14 |
