대수는 지수 연산의 역 연산입니다. 지수화의 예는 각 단계에서 항목 수를 두 배로 늘리는 것입니다. 따라서 로그 알고리즘은 종종 각 단계에서 항목 수를 반으로 줄입니다. 예를 들어, 이진 검색은이 범주에 속합니다.
많은 알고리즘은 큰 단계의 로그 숫자가 필요하지만 각각의 큰 단계에는 O (n) 개의 작업 단위가 필요합니다. Mergesort가이 범주에 속합니다.
일반적으로 균형 이진 트리로 시각화하여 이러한 종류의 문제를 식별 할 수 있습니다. 예를 들어, 병합 정렬은 다음과 같습니다.
6 2 0 4 1 3 7 5
2 6 0 4 1 3 5 7
0 2 4 6 1 3 5 7
0 1 2 3 4 5 6 7
위쪽에는 트리의 잎이 입력됩니다. 알고리즘은 위의 두 노드를 정렬하여 새 노드를 만듭니다. 균형 이진 트리의 높이는 O (log n)이므로 O (log n) 큰 단계가 있습니다. 그러나 각각의 새로운 행을 만드는 데는 O (n) 작업이 필요합니다. O (log n) O (n)의 큰 단계는 각각 mergesort가 O (n log n)라는 것을 의미합니다.
일반적으로 O (log n) 알고리즘은 아래 함수와 같습니다. 그들은 각 단계에서 데이터의 절반을 폐기합니다.
def function(data, n):
if n <= constant:
return do_simple_case(data, n)
if some_condition():
function(data[:n/2], n/2) # Recurse on first half of data
else:
function(data[n/2:], n - n/2) # Recurse on second half of data
O (n log n) 알고리즘은 아래 기능과 유사합니다. 그들은 또한 데이터를 절반으로 나누었지만 두 가지 모두를 고려해야합니다.
def function(data, n):
if n <= constant:
return do_simple_case(data, n)
part1 = function(data[n/2:], n/2) # Recurse on first half of data
part2 = function(data[:n/2], n - n/2) # Recurse on second half of data
return combine(part1, part2)
여기서 do_simple_case()는 O (1) 시간이 소요되고 combine()는 O (n) 시간을 넘지 않습니다.
알고리즘은 데이터를 정확하게 반으로 분할 할 필요가 없습니다. 그들은 그것을 3 분의 1과 2/3로 나눌 수 있습니다. 그러면 괜찮을 것입니다. 평균 - 케이스 성능의 경우 평균으로 절반으로 분할하는 것으로 충분합니다 (예 : QuickSort). 재귀가 (n/무언가)와 (n - n/무언가)의 조각에 대해 수행되는 한, 괜찮습니다. 만약 그것을 (k)와 (n-k)로 나누면 트리의 높이는 O (n)이 될 것이고 O (log n)는 아닌 것입니다.
나는 당신의 설명이 정말 마음에 든다. 이유와 이해 방법을 쉽게 이해할 수있게 해준 덕분이다. –