대용량 입력에 계산 형을 사용하지 않는 이유는 무엇입니까?

Question

카운팅 정렬은 O (n + K)의 평균 시간 복잡도를 갖는 정렬 알고리즘이며 카운팅 정렬은 각 입력 요소가 0에서 K 사이의 정수임을 전제로합니다.

왜 ' 우리는 정렬되지 않은 배열에서 최대 값을 선형 검색하고, K와 같으므로 그 위에 계수 형을 적용합니까?

Answer 1

입력 값이 maximum - minimum = O(n log n) 인 배열 (값의 범위가 합리적으로 제한됨) 인 경우 실제로 적용됩니다. 그렇지 않은 경우 표준 비교 기반 정렬 알고리즘 또는 기수 정렬과 같은 정수 정렬 알고리즘이 점근 적으로 좋습니다.

당신에게 예를하려면, 다음과 같은 알고리즘은 계산 정렬 런타임 복잡성 Θ(n^2)을 가지고있는 입력의 가족을 생성

def generate_input(n): 
    array = [] 
    for i := 1 to n: 
     array.append(i*i); 
    shuffle(array) 
    return array 

Answer 2

질문 귀하의 제목은 왜 일종의 카운트 큰 입력에 사용되지 ?

소트 카운팅에서는 무엇을합니까? 다른 배열 (b []를 가정)을 취하고 모든 원소를 0으로 초기화합니다. 그런 다음 해당 인덱스가 지정된 배열의 요소이면 인덱스를 증가시킵니다. 그런 다음 주어진 배열의 하한선에서 상한선까지 루프를 실행하고 가져온 배열 (b [])의 index 요소가 0인지 아닌지 확인하십시오. 0이 아니면 인덱스는 지정된 배열의 요소입니다.

자,이 두 (상한 & 하한)의 차이가 (10^9 이상과 같이) 매우 높으면 단일 루프로 PC를 죽일 수 있습니다. :) 우리 f(n) ∈ O(g(n)) 말할 경우

Answer 3

는 Big-O notation definition에 따르면, 그 값과 C > 0n = N 같은 CN 및가 상수 f(n) < C*g(n) 것을 존재한다는 것을 의미한다. C 값에 대해서는 아무 것도 언급되지 않았으며 그 중 부등호가 참인 n = N에 해당하지 않습니다.

모든 알고리즘 분석에서 튜링 기계의 각 작업 비용을 고려해야합니다 (비교, 이동, 합계 등). 이러한 비용의 값은 부등식을 true 또는 false로 바꾸기 위해 C 및 N의 값이 얼마나 크거나 작은지를 정의하는 요소입니다. 이 비용을 제거하는 것은 내가 알고리즘 분석 과정에서했던 익숙한 가정입니다.

문 "종류의 계산이다 O(n+k)"실제로 정렬이 C, N 및 K 상수 곳, n > K, n > N, C 주어진 다항식 및 선형 있음을 의미합니다. 따라서 주어진 조건이 참인 경우에만 부등식이 참이기 때문에 다른 알고리즘은 더 작은 입력에 대해 더 나은 성능을 가질 수 있습니다.