무차별 대입을 사용하여 선택 정렬 문제 해결

무차별 대입 방법은 문제를 해결하는 간단하고 직접적인 방법으로, 종종 문제에 대한 설명과 관련된 개념의 정의를 직접 기반으로 합니다.

선택 정렬 아이디어:

선택 정렬 시작 시 전체 목록을 스캔하여 가장 작은 요소를 찾은 다음 첫 번째 요소와 교환하고 순서가 지정된 목록의 마지막 위치에 가장 작은 요소를 배치합니다. 그런 다음 두 번째 요소부터 시작하여 목록을 스캔하고 마지막 (n-1) 요소의 최소값을 찾은 다음 두 번째 요소와 바꾸고 두 번째로 작은 요소를 목록의 최종 위치에 배치합니다. 일반적으로 i번째(i의 값 범위는 0에서 n-2까지) 목록을 스캔할 때 알고리즘은 마지막 (n-i) 요소 중에서 가장 작은 요소를 찾은 다음 이를 Ai와 교환합니다. (n-1)이 지나면 목록이 정렬됩니다.

다음은 내 코드 구현입니다. C++

으아악

알고리즘 분석:

입력의 크기는 요소 n개에 따라 결정됩니다. 기본 연산은 키 값 비교 Arr[minn]>Arr[j]입니다. 이 비교가 수행되는 횟수는 배열의 크기에만 따라 다릅니다.

C(n)=∑[i=0,i=N-2] ∑[j=i+1,j=N-1]=∑[i=0,i=N-2] ((N-1 )-(i+1)+1))=∑[i=0,i=N-2](N-i-1)=(n-1)*n/2

즉, 모든 입력에 대해 선택 정렬은 Θ(n2)의 시간 복잡도를 갖는 알고리즘입니다. 키 교환 횟수는 Θ(n)입니다. 이렇게 하면 선택 정렬 성능이 향상됩니다.

위 내용은 무차별 대입을 사용하여 선택 정렬 문제 해결의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!