>> DOUG 로이드 : 그래서 CS50에 우리는 약 배웠다 정렬 및 검색의 다양한
알고리즘.
그리고 때때로이 될 수 있습니다 유지하기 조금 까다로운
어떤 알고리즘의 트랙은 어떤 작업을 수행합니다.
우리는 정말 만했습니다 너무 표면을 미끄러 져
다른 많은 검색이 있습니다 및 정렬 알고리즘.
그래서이 비디오의하자 몇 분 정도 걸릴
시도하고 각 알고리즘을 증류 핵심 요소 아래로
그래서 당신은 대부분의 기억 그들에 대한 중요한 정보
및을 명확하게 설명 할 수 있어야한다 차이가 필요한 경우.
>> 첫 번째는 선택의 일종이다.
선택 정렬의 기본 개념 최소 정렬되지 않은 요소를 찾기
및 배열로 교체 그 배열의 첫 번째 정렬되지 않은 요소입니다.
우리는 최악의 경우라고 말했다 그것의 실행 시간은 N 제곱했다.
그리고 당신은 왜 기억하려는 경우, 취 선택 정렬 비디오를 봐주세요.
가장 좋은 경우의 실행 시간 또한 N 제곱된다.
>> 버블 정렬, 그 뒤에 생각 하나는 인접 쌍을 교환하는 것이다.
그래서 당신을 도와줍니다 키입니다 여기에 차이를 기억한다.
선택 일종이다, 지금까지, smallest-- 거품을 찾을 수
일종의 인접 쌍을 교환합니다.
우리는 인접 쌍을 교체 요소들은 경우
이는 효과적으로 순서가 오른쪽에 큰 요소 거품
동시에 또한 시작 왼쪽에 작은 요소를 이동합니다.
최악의 경우 런타임 거품 정렬의 N 제곱.
가장 좋은 경우의 실행 시간 거품의 종류는 N이다.
때문에 그 상황에서 우리는 ... 사실상 없습니다
우리는 필요하지 않을 수도 있습니다 전혀 스왑을합니다.
우리는 하나만을해야 모든 N 요소를 통해 전달합니다.
>> 삽입 정렬에서, 여기서 기본 개념은 시프트된다.
즉, 삽입 정렬의 키워드입니다.
우리는을 통해 한 번 단계거야 의 배열은 왼쪽에서 오른쪽으로.
우리가하는 것처럼, 우리는있어 요소를 이동하는 것
우리는 이미 공간을 만들어 봤어요 쯤에 해당 할 필요가 작은 것들
다시 그 정렬 된 부분.
그래서 우리는 정렬 된 배열을 구축 한 왼쪽에서 오른쪽으로 한 번에 요소,
우리는 공간을 마련하는 일을 이동.
의 최악의 실행 시간 삽입 정렬은 N 제곱된다.
가장 좋은 경우의 실행 시간은 N이다.
>> 키워드 sort-- 병합 여기 분할 및 병합된다.
우리는 여부, 전체 배열을 분할 그것은 여섯 요소, 여덟 요소이다,
10,000 elements-- 우리는 그것을 분할 아래로 반으로 반으로 반으로,
우리는 배열에서있을 때까지 N 개의 원소 어레이.
N 하나의 요소 배열의 집합입니다.
그래서 우리는 하나의 시작 1000 요소의 배열,
우리는 지점에 도착 우리가 어디 1000 한 요소 배열을 가지고있다.
그리고 우리는 그 하위 배열을 병합 시작 다시 함께 올바른 순서.
그래서 우리는이 하나의 요소 배열을 그리고 두 요소의 배열을 만들 수 있습니다.
우리는이 두 요소의 배열을 및 네 개의 소자 어레이를 만들
등등 등등 우리가 때까지 다시 한 N 소자 어레이를 재건.
>> 의 최악의 실행 시간 일종의 병합 N 시간은 N 로그인합니다.
우리는 N의 요소를 가지고 있지만 이 재결합 과정
로그인 걸립니다 N 단계를 얻기 위해 전체 배열에 백업합니다.
시간을 실행하는 가장 좋은 경우는 N 로그입니다 N이 과정은 정말하지 않기 때문에
배열 여부 관심 분류 여부와 함께 시작합니다.
프로세스는 거기, 동일 단락 회로 일 수있는 방법이 없습니다.
그래서 N 최악의 경우 N 로그 n은 최상의 경우에 로그 n.
>> 우리는 두 가지에 대해 이야기 알고리즘 찾고.
그래서 선형 검색을 반복하는에 관한 것입니다.
우리는 배열에 걸쳐 진행 한 번, 왼쪽에서 오른쪽으로,
수를 찾기 위해 노력 것을 우리는 찾고 있습니다.
최악의 실행 시간은 N의 큰 O입니다.
그것은 반복 우리가 걸릴 수 있습니다 모든 단일 요소를 통해
우리가 찾고있는 요소를 찾을 수 대, 중 마지막 위치에서,
또는 전혀.
그러나 우리는 때까지 확신 할 수 없습니다 우리는 모든 것을 살펴 보았다.
최선의 경우를 M, 우리는 즉시 찾을 수 있습니다.
가장 좋은 경우의 실행 시간 선형 검색 1의 오메가입니다.
>> 마지막으로, 이진 검색은 있었다 이는 모듬 배열이 필요합니다.
즉 아주의 기억 중요한 고려 사항
이진 검색 작업을 할 때.
그것은 그건 ...를 사용하는 전제 조건이다 당신을 찾고있는 배열
분류해야합니다.
그렇지 않으면, 키워드 분할 및 정복이다.
절반에 배열을 분할하고 요소의 절반을 제거
때마다 당신은을 통해 진행으로.
이 때문에 분할과 정복의 반 접근 방식에서 분할 것들
최악의 실행 시간 이진 검색입니다
실질적으로, 이는 N 로그 선형 검색의 n보다 더 나은.
가장 좋은 경우의 실행 시간은 여전히​​ 하나입니다.
>> 우리는 즉시 그것을 찾을 수 있습니다 처음으로 우리는 분열을 만들지 만,
다시, 그 기억 이진 검색은 있지만
선형 검색보다 훨씬 더 로그 인의 미덕에 의해 N N 대,
당신은 일을 통해 이동해야 할 수도 있습니다 먼저 배열을 정렬한다
따라서 덜 효과​​적 만들 수도 있습니다 분류 반복하는의 크기에.
>> 내가 더그 로이드 해요,이 CS50입니다.