프로그래머 는 반드시 이 알고리즘 들 을 능숙 하 게 파악 해 야 한다.
4610 단어 기술 의 축적
http://dev.iforeach.com/blogs/2011-03-01/algorithm-for-programmers
프로그래머 에 게 는 이러한 알고리즘 을 능숙 하 게 파악 해 야 합 니 다 (숙련 된 것 으로 기억 하고 이해 하 는 것 이 아 닙 니 다). - 각종 정렬 알고리즘 (정렬, 거품 정렬, 정렬 선택, 빠 른 정렬, 정렬, 병합 정렬) - 선형 표 (일반적인 선형 표, 스 택, 대기 열) 의 삽입 과 삭제 - 이 진 트 리 의 옮 겨 다 니 기 (앞 순서, 중간 순서, 뒤 순서) - 그림 의 옮 겨 다 니 기(깊이 우선, 넓이 우선) - 이분법 찾기, 정렬 이 진 트 리, Hash 찾기 (충돌 처리 방법)
내부 정렬 과 외부 정렬
정렬 과정 에서 정렬 해 야 할 모든 수 는 메모리 에 있 고 메모리 에서 저장 순 서 를 조정 하 는 것 을 내 정렬 이 라 고 합 니 다. 정렬 과정 에서 일부 수 만 메모리 에 불 러 오고 메모리 조정 수 를 통 해 외 장 에 있 는 저장 순서 정렬 방법 을 외 정렬 이 라 고 합 니 다.
알고리즘 의 시간 복잡 도와 공간 복잡 도
알고리즘 의 시간 복잡 도 란 알고리즘 을 실행 하 는 데 필요 한 작업량 을 계산 하 는 것 을 말한다. 알고리즘 의 공간 복잡 도 는 일반적으로 이 알고리즘 을 실행 하 는 데 필요 한 메모리 공간 을 가리킨다.
거품 정렬 이란 컴퓨터 의 정렬 방법 을 말 합 니 다. 시간 복잡 도 는 O (n ^ 2) 입 니 다. 정렬, 빠 른 정렬 의 O (nlogn, 밑 수 는 2) 에 미 치지 못 하지만 두 가지 장점 이 있 습 니 다. 1. '프로 그래 밍 복잡 도'매우 낮 고 코드 를 쓰기 쉽다.빠 른 정렬. 거품 정렬 은 n - 1 번 하위 정렬 을 통 해 이 루어 집 니 다. i 번 하위 정렬 은 첫 번 째 숫자 에서 n - i 번 째 숫자 까지 입 니 다. i 번 째 숫자 가 뒤의 숫자 보다 크 면 (오름차, 작 으 면 내림차 순) 두 수 를 교환 합 니 다.
def tset(array)
(array.length-1).times do |i|
(array.length-1-i).times do |j|
if array[j].to_i > array[j+1].to_i
array[j], array[j+1] = array[j+1], array[j]
end
end
end
puts array.join(",")
end
빠 른 정렬 (Quicksort)거품 정렬 에 대한 개선 입 니 다. C. A. R. Hoare 는 1962 년 에 제 기 했 습 니 다. 기본 적 인 사상 은 정렬 을 통 해 정렬 할 데 이 터 를 독립 된 두 부분 으로 나 누 었 습 니 다. 그 중 일 부 는 모든 데이터 가 다른 부분의 모든 데이터 보다 작은 다음 에 이 방법 에 따라 이 두 부분의 데 이 터 를 각각 빠르게 정렬 하고 전체 정렬 과정 을 재 귀적 으로 진행 할 수 있 습 니 다.이 를 통 해 전체 데이터 가 질서 있 는 서열 로 바 뀌 었 다.
def test(array)
return array unless array.length > 0
flag = array.pop.to_i
# left, right = 0, array.length-1
left_array, right_array = [], []
array.each do |i|
if i.to_i < flag
left_array << i
else
right_array << i
end
end
left_array = test2(left_array)
right_array = test2(right_array)
return left_array + [flag] + right_array
end
빠 른 정렬 (Quicksort) 에는 몇 가지 변종 알고리즘 이 있 습 니 다. 여기 서 간략하게 소개 하 겠 습 니 다.
에 세이 화 빠 른 배열: 빠 른 정렬 의 최 악의 경 우 는 매번 주 원 에 대한 선택 을 바탕 으로 합 니 다. 기본 적 인 빠 른 정렬 은 첫 번 째 요 소 를 주 원 으로 선택 합 니 다. 이렇게 배열 이 질서 가 있 는 상황 에서 매번 구분 하면 최 악의 결 과 를 얻 을 수 있 습 니 다. 비교적 흔히 볼 수 있 는 최적화 방법 은 에 세이 화 알고리즘 입 니 다. 즉, 무 작위 로 원 소 를 주 원 으로 선택 하 는 것 입 니 다. 이런 상황 에서 최 악의 경우 에 도 불구 하고.여전히 O (n ^ 2) 이지 만 최 악의 경 우 는 입력 데이터 에 의존 하지 않 고 랜 덤 함수 의 수치 가 좋 지 않 기 때 문 입 니 다. 실제로 랜 덤 으로 빠 른 순 서 를 매 겨 이론 적 최 악의 상황 을 얻 을 가능성 은 1 / (2 ^ n) 에 불과 합 니 다. 따라서 랜 덤 으로 빠 른 순 서 를 매 기 는 것 은 절대 다수의 입력 수가 O (nlogn) 에 달 하 는 기대 시간 복잡 도 에 달 할 수 있 습 니 다. 한 선배 가 치밀 한 정 리 를 내 렸 습 니 다."랜 덤 화 빠 른 정렬 은 한 사람의 평생 인품 수 요 를 만족 시 킬 수 있다." 랜 덤 화 빠 른 정렬 의 유일한 단점 은 입력 데이터 에 같은 데이터 가 많 으 면 랜 덤 화 효 과 는 바로 줄어든다 는 것 이다. 극한 상황, 즉 n 개의 같은 배열 에 대해 랜 덤 화 빠 른 정렬 의 시간 복잡 도 는 O (n ^ 2) 로 떨 어 질 것 이다.. 해결 방법 은 교환 되 지 않 은 상태 에서 주 원 을 원래 위치 에 유지 하 는 방법 으로 스 캔 하 는 것 이다. - 밸 런 스 빠 른 배열 (Balanced Quicksort): 매번 가능 한 한 중간 값 을 대표 할 수 있 는 요 소 를 관건 적 인 데이터 로 선택 한 다음 에 일반 빠 른 배열 의 원칙 에 따라 비교, 교체 와 재 귀 를 한다. 일반적으로 이 데 이 터 를 선택 하 는 방법 은 시작, 끝, 중간 세 개의 데 이 터 를 비교 하여 그 중의 중간 값 을 선택 하 는 것 이다. 이 세 가지 값 을 취 하 는 장점 은 실제 문제 에 있다.(예 를 들 어 정보 학 경기...) 에서 유사 순서 데이터 나 역순 데이터 가 나타 날 확률 이 비교적 크다. 이때 중간 데 이 터 는 반드시 중간 값 이 되 고 사실상 의 유사 중간 값 이다. 만약 에 중간 에 큰 양쪽 이 작다 (또는 반대로).의 데 이 터 는 모두 최고치 에 가깝다. 그러면 적어도 두 부분 을 분리 할 수 있 기 때문에 실제 효율 도 2 배 정도 증가 할 뿐만 아니 라 데 이 터 를 약간 흐 트 러 뜨리 고 퇴화 된 구 조 를 파괴 하 는 데 유리 하 다. - 외부 빠 른 배열 (External Quicksort): 일반적인 빠 른 배열 과 달리 관건 적 인 데 이 터 는 buffer 입 니 다. 먼저 이전 과 그 후의 M / 2 요 소 를 buffer 에 읽 고 이 buffer 의 이러한 요 소 를 정렬 한 다음 정렬 된 배열 의 시작 (또는 끝)다음 요 소 를 읽 습 니 다. 만약 에 이 요소 가 buffer 에서 가장 작은 요소 보다 작다 면 맨 처음 빈 자리 에 기록 합 니 다. 만약 에 이 요소 가 buffer 에서 가장 큰 요소 보다 크다 면 마지막 빈 자리 에 기록 합 니 다. 그렇지 않 으 면 buffer 에서 가장 크 거나 가장 작은 요 소 를 배열 에 기록 하고 이 요 소 를 buffer 에 넣 습 니 다. 최대 치 는 이러한 관건 적 인 데이터 보다 낮 고 최소 치 는 이것 보다 높 습 니 다.일부 관건 적 인 데 이 터 는 질서 있 는 중간 데 이 터 를 다시 배열 하지 않도록 합 니 다. 완 료 된 후에 배열 의 중간 빈 자 리 는 반드시 비어 있 습 니 다. 이 buffer 를 배열 의 중간 빈 자 리 를 기록 한 다음 에 외부 더 작은 부분 을 재 귀적 으로 다른 부분 을 순환 적 으로 정렬 합 니 다. -- 3 번 기수 빠 른 배열 (Three - way Radix Quicksort, Multikey Quicksort, Multi - key Quicksort): 기수 정렬 (radix sort, 일반적인 문자열 과 비교 하여 정렬 하면 기수 정렬)빠 른 배열 의 특징 은 문자열 정렬 에서 비교적 효율 적 인 알고리즘 입 니 다. 이 알고리즘 은 정렬 된 배열 의 요 소 는 하나의 특징 을 가지 고 있 습 니 다. 예 를 들 어 하나의 문자열, 모든 자 모 는 하나의 key 로 볼 수 있 습 니 다. 알고리즘 은 정렬 된 배열 에서 하나의 요 소 를 임의로 선택 하여 관건 적 인 데이터 로 합 니 다. 우선 이 요소 의 첫 번 째 key (자모) 만 고려 합 니 다.그 다음 에 다른 요 소 를 key 의 비 교 를 통 해 관건 적 인 데이터 보다 작 고 같 으 며 큰 세 부분 으로 나 눈 다음 에 이 key 위 치 를 바탕 으로 '작 음' 과 '큰' 부분 을 정렬 하고 다음 key 를 바탕 으로 '같은' 부분 을 정렬 합 니 다.
좋은 웹페이지 즐겨찾기
