대학을 시작했을 때 고등학교 졸업 후 여름 사무실에서 일했습니다. 나는 AP 컴퓨터 과학, 다른 것들 중에서 분류와 검색을 공부했습니다 .

이 지식을 기억할 수있는 여러 물리적 시스템에 적용했습니다.

시작하려면 자연스러운 병합 정렬…

시스템은 파일 카드 크기의 떼어 내기를 포함하여 여러 부분으로 된 양식을 인쇄했으며,이 양식은 서랍에 보관해야했습니다.

나는 그것들의 더미로 시작하여 더미를 분류했습니다. 첫 번째 단계는 손에 쉽게 배치 할 수있을 정도로 5 개 정도를 집는 것입니다. 정렬 된 패킷을 아래에 놓고 각 스택을 십자형으로 분리하여 보관하십시오.

그런 다음 각 스택 쌍을 병합 하여 더 큰 스택을 생성합니다. 스택이 하나만 될 때까지 반복합니다.

… 완료 할 삽입 정렬

다음 카드는 동일한 열린 서랍에서 조금 더 아래에 있기 때문에 분류 된 카드를 정리하는 것이 더 쉽습니다.

기수 정렬

이 사람은 반복적으로 가르치려고 했음에도 불구하고 내가 어떻게 그렇게 빨리했는지 이해하지 못했습니다.

큰 상자의 체크 스텁 (천공 카드 크기)을 분류해야합니다. 큰 테이블에서 솔리테어를하는 것처럼 보입니다. 거래하고, 쌓고, 반복하세요.

일반적으로

30 년 전, 나는 당신이 무엇에 대해 물어보고 있는지 알아 차 렸습니다. 비교 와 기록 처리에 상대적인 비용 과 캐싱 수준이 있기 때문에 아이디어가 물리적 시스템으로 매우 직접적으로 이전됩니다 .

잘 이해 된 등가물을 넘어서

나는 당신의 주제에 대한 에세이를 회상하고 그것은 스파게티 종류를 가져 왔습니다 . 키 값을 표시하기 위해 말린면의 길이를 다듬고 레코드 ID로 레이블을 지정합니다. 이것은 O (n)이며 각 항목을 한 번만 처리합니다.

그런 다음 번들을 잡고 테이블의 한쪽 끝을 탭합니다. 아래쪽 가장자리에 정렬되고 이제 정렬됩니다. 가장 긴 것을 사소하게 벗고 반복 할 수 있습니다. 판독 값도 O (n)입니다.

여기 “실제 세계”에서 알고리즘에 해당하지 않는 두 가지 일이 있습니다. 첫째, 가장자리 정렬은 병렬 작업입니다. 모든 데이터 항목은 프로세서이기도합니다 (물리 법칙이 적용됩니다). 따라서 일반적으로 사용 가능한 처리를 n으로 확장하여 기본적으로 고전적인 복잡성을 n의 요소로 나눕니다.

둘째, 가장자리를 정렬하면 정렬이 어떻게 이루어 집니까? 실제 정렬은, 비록 당신이 한 단계에서 가장 긴 발견 할 수있는 판독에 않은 가장 긴을 찾기 위해 그들 모두를 비교합니다. 다시, n의 계수로 나누면 가장 큰 것을 찾는 것은 이제 O (1)입니다.

또 다른 예는 아날로그 컴퓨팅을 사용하는 것입니다. 물리적 모델은 문제를 “즉시”해결하고 준비 작업은 O (n)입니다. 원칙적으로 계산은 준비된 항목 수가 아니라 상호 작용하는 구성 요소의 수에 따라 확장됩니다. 따라서 계산은 n²로 확장됩니다. 제가 생각하는 예는지도에 구멍을 뚫고 구멍을 통과하는 문자열에 가중치를 걸고 고리에 모든 문자열을 모아서 수행 된 가중 다중 요소 계산입니다.