정렬에 대한 질문

Question

버블 정렬은 O (n), O (n^2)는 최악이며 메모리 사용량은 O (1)입니다. 병합 정렬은 항상 O (n log n)이지만 메모리 사용량은 O (n)입니다.

정수의 배열을 취하여 컬렉션의 최대 정수를 반환하는 함수를 구현하는 데 사용할 알고리즘으로, 배열의 길이가 1000보다 작은 것으로 가정합니다. 배열 길이가 1000보다 큰 경우 어떻게 될까요?

Answer 1

최대 (O (n)) 시간 동안 O (1) 메모리 사용으로 데이터 세트의 순차 스캔을 수행 할 수 있습니다.

현재 최대 값을 첫 번째 요소로 설정 한 다음 다른 모든 요소를 ​​통해 현재 값을 최대 값으로 설정합니다. 의사 코드 : 거기 얼마나 많은 문제가되지 않도록

이

max = list[first_index] 
for index = first_index+1 to last_index: 
    if list[index] > max: 
     max = list[index] 

복잡성 목록에 관계없이 요소의 수를 변경하지 않습니다.

---

은 최대 빨리 찾는 것이 중요 경우 (알고리즘은 O는 (n)이 시간 이후) 그러나 변경하는 시간을 실행 가능성이 될 것입니다. 이 모든 것은 목록 이으로 변경 될 때마다 작업하는 것이 아니라 정보를 원할 때마다 작성되는 것이므로 작성된 것보다 자주 읽히는 목록에 더 적합하므로 비용을 상각 할 수 있습니다.

옵션 1은 마지막 요소를 가져올 수 있도록 목록을 정렬 된 상태로 유지하는 것입니다. 이것은 단지 최대 값을 기록하기 위해 이고 아마도 잔인합니다.

옵션 2는 목록에 삽입하거나 목록에서 삭제할 때 최대 값 (및이를 보유한 요소 수)을 다시 계산하는 것입니다. 초기에 max을 0으로, maxcount을 0으로 설정하여 빈 목록을 만듭니다. 을 삽입

:이 값보다 max 경우 maxcount이 0

• 경우 (목록이 비어있다)는,
• 달리 (1)에이 값 max 및 maxcount을 설정 max 세트 이 값으로 maxcount을 1로 설정하십시오.
• 이 값이 max 인 경우 maxcount에 1을 더하십시오. 삭제 옵션

:

• max이 값이 같으면
  는 maxcount에서 1을 뺀다.
• maxcount이 0이면 새로 검색하여 max 및 maxcount이되도록 다시 검색하십시오.

이렇게하면 언제든지 최대 값을 가질 수 있습니다 (최대 값을 갖는 요소가 둘 이상인 경우 알고리즘의 속도를 높이기 위해 단순히 "트릭"이 추가됩니다). 필자는 데이터 분석 응용 프로그램에서 이것을 한 번 사용했으며 재 분류보다 훨씬 빠르다고 판명되었습니다.이 경우 최소값과 최대 값을 모두 저장해야했지만 같은 생각입니다.

Answer 2

최대 값은 사전 정렬되지 않는 한 항상 O (n)입니다. 미리 정렬하면 덜합니다. 검색하기 전에 정렬은 항상 O (n)보다 나쁩니다 ... 일반적으로 1,000 개의 요소가 1,000 개의 비교를 취합니다 ... 문자 그대로 비교하십시오. 정렬 된 구조로 작업하는 경우 비용이 저렴합니다. 그렇지 않은 경우 비용이 많이 듭니다. 정렬 구조로 삽입하는 것이 더 비쌉니다. ... 이것이 왜 그런 문제가되는 이유입니다.