위에서도 나온 말이지만, 알고리즘의 복잡도는 시간(time)과 공간(space)에서 측정됩니다.
대부분의 경우 두 요소 간에는 trade-off가 있고요.
특정 문제 도메인에서만 아주 높은 성능을 내는 알고리즘들도 있습니다.
(입력 집합의 특성같은 조건에 영향을 받는 것들)
현실적인 계산 완료 시간을 척도로 하는 것에 관한 질문이신거같은데,
big O notation으로 표기된 이론적인 시간복잡도에 입력의 개수를 넣고 적정한 상수를 곱하면 현실적인 시간으로 간주될 수 있습니다. 바꾸어, 뒤집어 말하면 입력의 개수를 변경하면서 현실적인 시간을 측정하면 big O notation이 어찌 생겼을 지도 어느 정도 짐작가능합니다.
결론부터 말씀드리면 "몇번 비교했나"라는 표현보다
"몇 스텝을 돌아야하나"라고 하는 것이 알기 쉽지 않을까합니다. (스텝 : 라인수가 아니구 알고리즘 실행의 기본 단위)
스텝을 나누는 기준으로 비교문이 자주 기점이 되기 때문에
비교했냐라는 말이 나왔나 봅니다.
저두 학부때 "몇번 비교했나"로 강의를 들었기 때문에 이해불가~~ (@.@) 했었던 기억이 있네요.
여튼 알고리즘을 분석한다는 의미는 이렇습니다.
어떤 알고리즘에
1. n개의 입력이 있으면
2. 얼만큼의 컴퓨터 자원을 사용하느냐(실행시간, 메모리 사용)
를 도출하는 것입니다.
예를 들면 선택정렬(
1. 리스트에서 최소값을 찾는다
2. 리스트의 첫번 째 값과 1에서 찾은 값을 스왑한다.
3. 나머지 리스트의 요소들도 위의 처리를 반복한다.
) 에서는
첫번째에는 최소값을 찾기 위해 n-1스텝을 실행합니다.
두번째에는 위의 값을 제외한 최소값을 찾기 위해 n-2스텝을 실행합니다.
마찬가지로 n-3, n-4, n-5 ...2, 1까지의 스텝을 실행합니다.
결과적으로 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2스텝이 걸리게 됩니다.
n개 기준의 실행 스텝수로 계산함으로써 컴터 시스템, 언어, 구현에 관계없는 분석이 이루어지는 겁니다.
그래서 "비교한 수"라고 하는 것은 실제로는 "실행된 스텝수"를 의미하는 겁니다.
참고로... 각 알고리즘 별로 n에 대한 스텝수를 계산한 결과를 분류해서
Big-O로 표기하는 방법을 사용하고 있습니다.
(위의 예에서는 n의제곱에 비례해서 스텝수가 실행 되어야하므로(O(n*n)) 썩 좋은 성능은 기대하기 어렵습니다.)
먼저 단위연산이
먼저 단위연산이 무엇인지를 파악한 후 이것들이 입력의 크기에 따라 어떻게 비례하여 증가하는 지를 따져보게 됩니다...
이를 Time Complexity라고 하는데...보통 Big-O 표기(또는 Theta)로 많이 표현하죠...
위의 예에서처럼 배열에서 최대값찾는 경우엔 단위연산이 비교하는 작업이 될 수가 있는 거죠...
Big-O의 정의에 따라 차수가 높을수록 '일반적으로' 시간이 더 많이 걸리겠구나 하고 생각할 수 있는 것이죠...하지만 상수들(계수와 같은)이 숨겨져 있기에 특정 threshold를 경계로 그런 생각이 역전되기도 해요...
허접한 댓글 죄송...
알고리즘관련 책의 앞부분이나 계산이론책들을 보면...좀 더 잘 아실 수 있을 거예요...
알고리즘 수업을
알고리즘 수업을 들으면 그런게 나오는데요
언급하신 탐색문제는
주된 연산이 비교연산이고 그 비교연산이 일정횟수 반복되니까
비교연산의 비용을 상수로 생각하고
비교연산이 얼마나 반복되는지를 따지는 겁니다
또 다른 연산이 반복된다면 그것도 생각해야겠지요
이게 input의 조건에 따라서도 달라질 수 있는데
array를 적어 놓으셨으니
index를 가지고 상수시간만에 값에 접근할 수 있는데
linked list 였다면 그 값에 접근하는데도 비용이 필요하겠고
그렇다면 그 비용도 따져야겠지요
적어 놓으신 것 처럼 순차적인 값이라면
(사실 그렇다면 search할 필요 없겠죠;)
모든 수를 비교할 필요가 없지만
이게 임의의 값들의 집합이라면
모든 값들은 최소한 한번은 비교해봐야
최대값이 아니라는 걸 확인할 수 있으니까
n 개의 elements 중에 최대값을 찾으려면
n-1 번의 비교연산을 수행해야겠죠
이런식으로 증명하던데요;
complexity 측정대상은
complexity 측정대상은 time, storage 등이 될 수 있습니다.
성능이 무엇에 비례하느냐... 는 보통 input의 개수에 비례를 하지요.
그리고 위에서 지적했듯이, 가장 비싼 연산만 계산하면 됩니다. 알고리즘 책 초반에 보면 나옵니다~
위에서도 나온
위에서도 나온 말이지만, 알고리즘의 복잡도는 시간(time)과 공간(space)에서 측정됩니다.
대부분의 경우 두 요소 간에는 trade-off가 있고요.
특정 문제 도메인에서만 아주 높은 성능을 내는 알고리즘들도 있습니다.
(입력 집합의 특성같은 조건에 영향을 받는 것들)
현실적인 계산 완료 시간을 척도로 하는 것에 관한 질문이신거같은데,
big O notation으로 표기된 이론적인 시간복잡도에 입력의 개수를 넣고 적정한 상수를 곱하면 현실적인 시간으로 간주될 수 있습니다. 바꾸어, 뒤집어 말하면 입력의 개수를 변경하면서 현실적인 시간을 측정하면 big O notation이 어찌 생겼을 지도 어느 정도 짐작가능합니다.
-----
오늘 나의 취미는 끝없는, 끝없는 인내다. 1973 法頂
-----
오늘 나의 취미는 끝없는, 끝없는 인내다. 1973 法頂
input 갯수 - 걸린 시간
input 갯수 - 걸린 시간 그래프가 있으면 되겠네요
다른 사항이 필요가 없다면....
그래프와 실제 값... 가장 중요한 것 같습니다.
Regards,
merius
Regards,
merius
넘 늦게 답글 다는 것 같지만
결론부터 말씀드리면 "몇번 비교했나"라는 표현보다
"몇 스텝을 돌아야하나"라고 하는 것이 알기 쉽지 않을까합니다. (스텝 : 라인수가 아니구 알고리즘 실행의 기본 단위)
스텝을 나누는 기준으로 비교문이 자주 기점이 되기 때문에
비교했냐라는 말이 나왔나 봅니다.
저두 학부때 "몇번 비교했나"로 강의를 들었기 때문에 이해불가~~ (@.@) 했었던 기억이 있네요.
여튼 알고리즘을 분석한다는 의미는 이렇습니다.
어떤 알고리즘에
1. n개의 입력이 있으면
2. 얼만큼의 컴퓨터 자원을 사용하느냐(실행시간, 메모리 사용)
를 도출하는 것입니다.
예를 들면 선택정렬(
1. 리스트에서 최소값을 찾는다
2. 리스트의 첫번 째 값과 1에서 찾은 값을 스왑한다.
3. 나머지 리스트의 요소들도 위의 처리를 반복한다.
) 에서는
첫번째에는 최소값을 찾기 위해 n-1스텝을 실행합니다.
두번째에는 위의 값을 제외한 최소값을 찾기 위해 n-2스텝을 실행합니다.
마찬가지로 n-3, n-4, n-5 ...2, 1까지의 스텝을 실행합니다.
결과적으로 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2스텝이 걸리게 됩니다.
n개 기준의 실행 스텝수로 계산함으로써 컴터 시스템, 언어, 구현에 관계없는 분석이 이루어지는 겁니다.
그래서 "비교한 수"라고 하는 것은 실제로는 "실행된 스텝수"를 의미하는 겁니다.
참고로... 각 알고리즘 별로 n에 대한 스텝수를 계산한 결과를 분류해서
Big-O로 표기하는 방법을 사용하고 있습니다.
(위의 예에서는 n의제곱에 비례해서 스텝수가 실행 되어야하므로(O(n*n)) 썩 좋은 성능은 기대하기 어렵습니다.)
메모리는 스왑용 1개가 필요하겠군요. 마찬가지로 Big-O표기로 분류합니다.
아...
질문의 예에서는
A[0,1,2,3,4..........n]
정렬이 되어 있네요...;;
한 스텝에 찾을 수 있으므로 O(1)이 되겠습니다.
정렬이 안되어 있다면
n단계의 스텝을 거쳐야 하므로 O(n)이 되겠군요.
댓글 달기