편집
1,162
번
"계산복잡도"의 두 판 사이의 차이
둘러보기로 가기
검색하러 가기
편집 요약 없음
| 3번째 줄: | 3번째 줄: | ||
순차 검색 알고리즘은 리스트의 첫 항목부터 차례로 목표값(찾고자 하는 학번)과 비교해 나가는 이해하기 쉬운 방법을 사용한다. 이 검색은 목표값에 따라 일찍 끝날 수도 늦게 끝날 수도 있지만, 최악의 경우 n개의 항목을, 평균적으로는 n/2개의 항목을 검사한 후에 종료될 것이다. 반면, 이진 검색 알고리즘은 리스트의 중앙 항목[n이 짝수면 n/2번째 항목, n이 홀수면 (n+1)/2번째 항목)]을 목표값과 비교하는 방식으로 진행된다. 그 항목이 목표값과 다르다면, 다음에는 목표값이 그 항목보다 큰지 작은지에 따라 그 항목의 우측 또는 좌측 리스트의 중앙 항목을 검사하기를 반복한다. 따라서 첫 단계에는 원래 길이(2<sup>k</sup>)의 리스트를, 두 번째 단계에는 원래의 반쪽 길이(2<sup>k-1</sup>)의 리스트를, 세 번째 단계에는 다시 그 반쪽 길이(2<sup>k-2</sup>)의 리스트를 검사하며, 최악의 경우 이 작업은 대략 k(=log<sub>2</sub>n)<ref>''n''=2<sup>''k''</sup>일 때, log<sub>2</sub>''n'' = ''k''.</ref>번의 검사만에 완료된다. 만약 리스트의 항목 수가 30,000(≒2<sup>15</sup>)개이고 하나의 항목을 검사하는 시간이 10밀리초<ref>1밀리초=0.001초</ref>로 동일하다면, 순차 검색은 평균 15,000개 정도의 항목을 검사하여 150초에 끝나지만, 이진 검색은 최대 15개 정도의 항목을 검사하여 0.15초만에 끝난다. | 순차 검색 알고리즘은 리스트의 첫 항목부터 차례로 목표값(찾고자 하는 학번)과 비교해 나가는 이해하기 쉬운 방법을 사용한다. 이 검색은 목표값에 따라 일찍 끝날 수도 늦게 끝날 수도 있지만, 최악의 경우 n개의 항목을, 평균적으로는 n/2개의 항목을 검사한 후에 종료될 것이다. 반면, 이진 검색 알고리즘은 리스트의 중앙 항목[n이 짝수면 n/2번째 항목, n이 홀수면 (n+1)/2번째 항목)]을 목표값과 비교하는 방식으로 진행된다. 그 항목이 목표값과 다르다면, 다음에는 목표값이 그 항목보다 큰지 작은지에 따라 그 항목의 우측 또는 좌측 리스트의 중앙 항목을 검사하기를 반복한다. 따라서 첫 단계에는 원래 길이(2<sup>k</sup>)의 리스트를, 두 번째 단계에는 원래의 반쪽 길이(2<sup>k-1</sup>)의 리스트를, 세 번째 단계에는 다시 그 반쪽 길이(2<sup>k-2</sup>)의 리스트를 검사하며, 최악의 경우 이 작업은 대략 k(=log<sub>2</sub>n)<ref>''n''=2<sup>''k''</sup>일 때, log<sub>2</sub>''n'' = ''k''.</ref>번의 검사만에 완료된다. 만약 리스트의 항목 수가 30,000(≒2<sup>15</sup>)개이고 하나의 항목을 검사하는 시간이 10밀리초<ref>1밀리초=0.001초</ref>로 동일하다면, 순차 검색은 평균 15,000개 정도의 항목을 검사하여 150초에 끝나지만, 이진 검색은 최대 15개 정도의 항목을 검사하여 0.15초만에 끝난다. | ||
알고리즘 수행에 걸리는 시간은 입력 자료의 항목 수 n에 대한 함수로 표현될 수 있는데, 그 함수는 컴퓨터의 성능에도 영향을 받는다. 그래서 n개의 항목으로 이루어진 자료를 처리하는 데 어떤 컴퓨터에서 n<sup>2</sup>초가 필요한 알고리즘이 다른 컴퓨터에서는 0.1n<sup>2</sup>초만에 수행될 수도 있다. 그러나 그 함수의 유형이 2차 다항식이라는 점은 바뀌지 않는다. 따라서 컴퓨터 이론에서는 그 함수의 유형을 통해 알고리즘의 효율성을 분류한다. 이러한 함수의 유형에는 계승식(n!)<ref>n! = n × (n-1) × … × 2 × 1</ref>, 지수식, 2차 다항식, 1차 다항식, 로그식 등이 있으며, 이러한 유형을 그것의 대표식으로 간단히 표기하는 것을 빅-세타(θ) 표기법이라고 부른다. 이 표기법에서는 알고리즘 수행 시간이 2n초든 100n+100초든 모두 1차 다항식에 해당하므로 두 알고리즘의 효율성은 1차 다항식의 대표식인 n을 이용하여 θ(n)으로 표기되고, 각각 2n<sup>2</sup>+5n초와 8n<sup>2</sup>초가 걸리는 두 알고리즘의 효율성은 모두 θ(n<sup>2</sup>)으로 표기된다. 그렇다면 순차 검색 알고리즘은 θ(n | 알고리즘 수행에 걸리는 시간은 입력 자료의 항목 수 n에 대한 함수로 표현될 수 있는데, 그 함수는 컴퓨터의 성능에도 영향을 받는다. 그래서 n개의 항목으로 이루어진 자료를 처리하는 데 어떤 컴퓨터에서 n<sup>2</sup>초가 필요한 알고리즘이 다른 컴퓨터에서는 0.1n<sup>2</sup>초만에 수행될 수도 있다. 그러나 그 함수의 유형이 2차 다항식이라는 점은 바뀌지 않는다. 따라서 컴퓨터 이론에서는 그 함수의 유형을 통해 알고리즘의 효율성을 분류한다. 이러한 함수의 유형에는 계승식(n!)<ref>n! = n × (n-1) × … × 2 × 1</ref>, 지수식, 2차 다항식, 1차 다항식, 로그식 등이 있으며, 이러한 유형을 그것의 대표식으로 간단히 표기하는 것을 빅-세타(θ) 표기법이라고 부른다. 이 표기법에서는 알고리즘 수행 시간이 2n초든 100n+100초든 모두 1차 다항식에 해당하므로 두 알고리즘의 효율성은 1차 다항식의 대표식인 n을 이용하여 θ(n)으로 표기되고, 각각 2n<sup>2</sup>+5n초와 8n<sup>2</sup>초가 걸리는 두 알고리즘의 효율성은 모두 θ(n<sup>2</sup>)으로 표기된다. 그렇다면 순차 검색 알고리즘은 θ(n), 이진 검색 알고리즘은 θ(log<sub>2</sub>n)에 속하며, θ(log<sub>2</sub>n)은 θ(n)보다, θ(n)은 θ(n<sup>2</sup>)보다 높은 효율성을 뜻한다. 이러한 알고리즘의 효율성은 알고리즘의 복잡도로 변환될 수 있는데, 이때 알고리즘의 복잡도가 높다는 것은 효율성이 낮다는 것을 의미한다. | ||
문제의 복잡도는 그 문제를 위한 최선의 알고리즘의 복잡도로 정의된다. 물론 문제의 어떤 해법이 그 문제를 위한 최선의 알고리즘이라는 것을 파악하는 일은 매우 어렵다. 이러한 상황에서 어떤 문제의 복잡도에 대해 현재까지 알려진 사항을 표현하기 위해 빅-오(O) 표기법이 사용된다. 어떤 문제가 θ(f(n))에 속하는 알고리즘으로 해결되고, 현재까지는 그것이 최선의 해법이라면, 그 문제는 O(f(n))에 속한다고 말한다. 예컨대 순차적으로 정렬된 n개의 항목을 가진 리스트를 검색하는 문제에 대한 최선의 해법은 이진 검색으로 알려져 있으며, 따라서 이러한 검색 문제는 O(log<sub>2</sub>n)에 속한다. | 문제의 복잡도는 그 문제를 위한 최선의 알고리즘의 복잡도로 정의된다. 물론 문제의 어떤 해법이 그 문제를 위한 최선의 알고리즘이라는 것을 파악하는 일은 매우 어렵다. 이러한 상황에서 어떤 문제의 복잡도에 대해 현재까지 알려진 사항을 표현하기 위해 빅-오(O) 표기법이 사용된다. 어떤 문제가 θ(f(n))에 속하는 알고리즘으로 해결되고, 현재까지는 그것이 최선의 해법이라면, 그 문제는 O(f(n))에 속한다고 말한다. 예컨대 순차적으로 정렬된 n개의 항목을 가진 리스트를 검색하는 문제에 대한 최선의 해법은 이진 검색으로 알려져 있으며, 따라서 이러한 검색 문제는 O(log<sub>2</sub>n)에 속한다. | ||